Prerequisite:

MATH 308 and MATH 343. MATH 345 is recommended.

Textbook:

Integer Programming by Laurence A. Wolsey, John Wiley and Sons, 1998.

Calendar Description

Model building using integer variables, computer solutions, relaxations and lower bounds, heuristics and upper bounds, branch and bound algorithms, cutting plane algorithms, valid inequalities and facets, branch and cut algorithms, Lagrangian duality and column generation.

Outline:

Model building using integer, binary and mixed integer variables. Computer solution of integer programming models, linear programming relaxations, Lagrangian relations, duality, simple upper bounds using greedy algorithms, Branch and bound algorithms, implicit enumeration, LP based branch and bound.

Valid inequalities, Gomory’s fractional cut, mixed integer cuts, strong valid inequalities, simple facets for 0-1 knapsack polytope and the traveling salesman polytope, branch and cut algorithms.

Lagrangian relaxation, strength of the Lagrangian dual, Lagrangian heuristics.

Column generation algorithm, solving symmetric traveling salesman problem using column generation.

Greedy and local search algorithms, construction heuristics, worst case analysis of heuristics.

Grading Scheme:

Homework – 20%

Midterm – 20%

Presentation – 20%

Final – 40%

Students will make a 40-minute in-class presentation of a classic research paper at the end of the term.

THE INSTRUCTOR RESERVES THE RIGHT TO CHANGE ANY OF THE ABOVE INFORMATION