CO 759: Topics in Discrete Optimization

Topic for Winter 2016: Topics in Integer Programming

Instructor: Ricardo Fukasawa

Class time: 10:30am -11:50am Tuesday/Thursday, Mathematics and Computer Building (MC) 6486

Course outline:
Integer Programming consists in nding an optimal solution to a system of linear inequalities such that some (or all) of the variables satisfy a given integrality requirement. It is a widely applicable area of research and is intimately linked to the solution of many different optimization problems.

The purpose of this course is to complement the regular integer programming course (CO652) and study integer programming methods and theory not covered in that course.
We will survey several different approaches to integer programming.
Even though this course will be related to CO652, I will not require the CO652 material as background. Whatever results that are usually seen in CO652 that I require I will either state completely without proof or informally give the basic idea so that you can follow the material along.

Topics to be covered will include a signi cant subset of the following:

1. Cutting planes

(a) Some basic polyhedral theory, and usual results seen in CO652.

(b) Introduction (review): Gomory cuts, MIR cuts, split cuts, disjunctive cuts, inter-section cuts

(d) Rank and Closures: Polyhedrality and relationship

(e) Cutting planes from simple structures: mixing, mingling, two-step MIR.

(f) Gomory's Group and Corner Polyhedra (finite and infinite)

(g) Multi-row Gomory cuts

2. Reformulation

(a) Basis reduction and LLL

(b) Solving IP in fixed dimension

3. Primal methods