Math-7490

**Textbook** (useful but not required):
Combinatorial Optimization, by W. Cook, W. Cunningham, W. Pulleyblank, and A.
Schrijver.

**Time**: TuTh: 1:40 – 3:00

In this course, students will be motivated by real world problems. They will learn how to solve fundamental problems in discrete optimization. They will also be introduced to advance techniques to deal with computationally hard problems.

- Introduction –
*the world of discrete optimization*

a)
Examples
from the real world

b)
Graph
Theory

c)
Linear
Programming

d)
Linear
Integer Programming

e)
The
theory of NP-completeness

- Network Problems –
*the common domain of all problems in discrete optimization*

a)
Minimum
Spanning Tree

b)
Shortest
Path

c)
Assignment
and Transportation Problems

d)
Max
Flow and Min Cut

e)
Min
Cost Flow

f)
Unimodular
Matrices

g)
Multicommodity
Flows

- Linear Integer
Programming –
*your problem is a special case*

a)
Polyhedron:
Convex Hull and Facet

b)
Cutting
Planes

c)
Separation
and Optimization

- Exploring Structures –
*take a closer look at your problem*

- Branch-and-Bound –
*if your problem is not too big*

- Approximation
Algorithms –
*getting the second best solution*

- Randomized Algorithms –
*it pays to take a chance*

Problems that will be studied in the last four
chapters include:

a)
Knapsack
Problem;

b)
Traveling
Salesman Problem;

c)
Set
Covering Problem;

d)
Set
Packing problem;

e)
Set
Partitioning Problem;

f)
Other
related problems.