Math-7490

Discrete Optimization

 

Prerequisite: Linear Algebra

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.

 

  1. 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

 

  1. 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

 

  1. Linear Integer Programming –your problem is a special case

a)      Polyhedron: Convex Hull and Facet

b)      Cutting Planes

c)      Separation and Optimization

 

  1. Exploring Structures –take a closer look at your problem

 

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

 

  1. Approximation Algorithms –getting the second best solution

 

  1. 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.