# CO452/652: Integer Programming

## Instructor: Chaitanya Swamy

MC 4033 ext. 33600
cswamy AT math DOT uwaterloo DOT ca

Time: MWF 12:30-1:20pm
Location: MC 2034

Office Hours: Fridays after class till 3pm.

## Announcements (assignments etc.)

• Apr 12: For more information about the Ellipsoid method and its applications to combinatorial optimization, you may want to consult the following book, which is the definitive source of information on this topic:
• Geometric Algorithms and Combinatorial Optimization, M. Grötschel, L. Lovász, and A. Schrijver. Springer-Verlag, 1988.
• Apr 8: Solutions to Assignment 4 have been posted. (There was an error in the bonus question Q6(c).)
• Apr 6: The final exam will be a take-home exam. You may pick up the exam any time between Monday, April 6, 12 noon and Wednesday, April 8, 12 noon, and you have one week to work on it.
You are not allowed to collaborate with others or discuss your work with anyone. You may only consult your notes and assignment solutions (i.e., no books, Google, or other external sources).
• Apr 6: Here are the slides (ppt) that were used to illustrate the ellipsoid method in class.
• Apr 2: Solutions to Assignment 3 have been posted.
• Mar 29: Important clarification/addition about Q3 on assignment 4: assume that S is non-empty (otherwise the correspondence between pointedness of Q and full-dimensionality of projJ(PI) does not hold). The assignment has been updated. (And the hint for Q6(a) has been corrected, as mentioned in a previous email.)
• Mar 23: There was a slight error in Q6(b) in assignment 4, which has now been corrected.
• Mar 21: There is a typo in Q1(a) in assignment 4. The inequality should read ∑iE(C) xi|C|-1. The assignment has been updated.
• Mar 17: Assignment 4 is available (updated Apr 10). Due on April 3, 2009. Here are the Solutions.
• Mar 3: Solutions to Assignment 2 have been posted.
• Feb 24: Assignment 3 is available. Due on March 9, 2009. Here are the Solutions and the AMPL model file crossing.mod.
• Feb 9: There was an error in Q5(b) in assignment 2. The second part "Argue that …." asked you to prove something that is incorrect. The assignment has been updated below, and the second part of Q5(b) now asks you to prove something slightly different. Please make sure you have the latest version.
• Feb 6: A clarification about Q3(b) in assignment 2: the vectors l and u should not depend on c, i.e., you are supposed to prove that there exist l and u such that for any c for which (IP) is not unbounded, its optimal value remains unchanged if we restrict x so that lxu. The assignment has been updated.
• Feb 2: A couple of typos in assignment 2:
• In Q1(c), it should be "where Q is a polytope".
• In Q5, in the definition of a polyhedron of antiblocking type, yx should be nonnegative.
• In Q5(b), notice that P is a polyhedron of antiblocking type.
The assignment has been updated.
• Jan 30: Solutions to Assignment 1 have been posted. The solutions are in a password-protected area; the username and password will be announced in class on Monday, February 2, 2009.
• Jan 30: Assignment 2 is available (updated Feb 9). Due on February 13, 2009. Here are the Solutions.
• Jan 16: A few typos/clarifications in assignment 1:
• In Q1, assume that {x: Ax ≤ b} is non-empty.
• In Q2, it should be yTA=cT in the dual.
• In Q3(b), z is non-zero.
The version posted below is the updated version.
• Jan 16: Assignment 1 is available. Due on January 30, 2009. Here are the Solutions.
• Jan 9: No office hours today.
• Jan 5: Welcome to CO452/652.

## Course Outline

Integer programs are optimization models that provide a great deal of flexibility and modeling power, but are are often notoriously hard to solve and are much less understood compared to linear programs in terms of solution methods. This course will cover the theory of integer programming, which has its roots in elegant polyhedral theory and duality, its applicability in modeling optimization problems, and algorithms for solving integer programs.

See here for a tentative list of topics, and here for a pdf version of the course outline containing a list of topics.

## Topics Covered

• Jan 5: Course introduction. Definition of linear and integer programs, convexity and convex hull.
• Jan 7: Showed the equivalence of optimization (of a linear function) over a set of integer points and optimization over their convex hull.
• Jan 9: Proved separating hyperplane theorem. Definition of a cone. Proved Farkas' Lemma using the separating hyperplane theorem.
• Jan 12: Stated LP duality theorem. Proved stronger form of Farkas' lemma using a lemma showing the existence of a feasible solution in a polyhedron where rank of active constraints = rank of constraint matrix.
• Jan 14: Proved the above lemma about polyhedra. Proved the equivalence of finitely generated cones and polyhedral cones.
• Jan 16: Started with the proof of the representation theorem about polyhedra showing that a set is a polyhedron iff it can be written as the sum of a polytope and a polyhedral cone.
• Jan 19: Finished the above proof. Stated the corollary that a rational polyhedron can be written as the sum of a rational polytope and a polyhedral cone generated by rational/integral vectors (and vice versa). Started with the proof showing that the convex hull of integer points of a rational polyhedron is a rational polyhedron.
• Jan 21: Finished the above proof. Started with polyhedral theory. Defined face of a polyhedron, and proved that a non-empty set is a face of a polyhedron P = {x: Ax ≤ b} iff it can be written as {xP: A'x=b'} where A'x ≤ b' is a subsystem of Ax ≤ b.
• Jan 23: Defined facets. Proved a lemma showing that if a polyhedron is described by an irredundant system Ax ≤ b, then there is a one-one correspondence between its facets and the inequalities in A<x ≤ b<, where A<x ≤ b< represents the inequalities of Ax ≤ b that are not implicit equalities.
• Jan 26: Facets contd. Proved corollaries of the above lemma showing that a polyhedron has an essentially unique irredundant description.
• Jan 28: Defined characteristic cone, lineality space, extreme points. Proved that a polyhedron P is pointed iff each of its minimal faces is a singleton consisting of an extreme point. Hence, if P is pointed, then if max cTx s.t. xP has an optimal solution, it has an optimum solution that is an extreme point of P. Defined affine independence, dimension of a set.
• Jan 30: Proved lemma relating the dimension of a polyhedron P to the rank of the subsystem consisting of its implicit equalities, and characterized the facets of P as its faces of dimension dim(P)-1.
• Feb 2: Used polyhedral theory to show that the polyhedron {xR|E|: x(δ(v)) ≤ 1 for all v, 0xe ≤ 1 for all e} describes the convex hull of matchings in a bipartite graph. Hence, argued that for a bipartite graph, the polyhedron where there are integer lower and upper bounds qv, bv respectively on the degree x(δ(v)) of each node v, and where lexeue for every edge e (with le, ue integer), if non-empty has integral extreme points.
• Feb 4: Started with modeling and formulations. Proved that the knapsack-polytope is full-dimensional and identified certain valid and facet-defining inequalities. Started with the stable-set problem, showed the stable-set polytope is full-dimensional and gave two formulations for it.
• Feb 6: Stable-set contd. Showed that the formulation with clique inequalities is stronger, and argued that the clique-inequalities are facet-defining. Briefly considered the formulation with odd-cycle inequalities, and its relation to the formulation with only edge-inequalities, and the one with clique inequalities. Started with the traveling salesman problem (TSP), and gave a valid formulation using degree constraints and subtour inequalities.
• Feb 9: Proved that the TSP polytope has dimension m-n, where m=n(n-1)/2 is the number of edges of an n-node complete graph.
• Feb 11: Proved that the subtour-elimination constraints define facets of the TSP polytope. Introduced network flow problems, defining the min-cost flow problem.
• Feb 13: Defined fixed-charge flow problems. Defined the ≥, ≤, and = versions of the single-node fixed-charge (SNFC) flow problem, where, respectively, at least D, at most D, and exactly D units of flow must be routed. Defined the covering knapsack problem, and showed that valid inequalities for the covering knapsack problem yield valid inequalities for the ≥-SNFC problem. Showed how valid inequalities (e.g., the cover and extended cover inequalities) for the knapsack problem translate to valid inequalities for covering knapsack.
• Feb 16-20: NO CLASSES due to Reading Week.
• Feb 23: Considered the ≤-SNFC problem and derived the flow cover inequalities. Showed how these inequalities can be used to obtain valid inequalities for the capacitated facility location problem by aggregating clients and facilities. Described how basic boolean logical statements can be modeled with constraints involving binary variables, which can then be combined to encode complex boolean-logic statements.
• Feb 25: Described how one can introduce binary variables to encode whether a constraint is satisfied. This, along with the ability to encode logical statements using binary variables, gives rise to the tremendous modeling power of IPs. Described the Chvátal-Gomory (CG) procedure for automatically generating valid inequalities, and gave some examples. Defined the notion of Chvátal-rank of an inequality.
• Feb 27: Proved that starting with the feasible region P of an LP-relaxation of a {0,1}-IP, every valid inequality for PI can be generated via a finite number of applications of the CG procedure, that is, it has finite Chvátal rank.
• Mar 2: Defined superadditive functions and showed how they can be used to generate valid inequalities that subsume the CG inequalities and may be stronger than the CG inequalities.
• Mar 4: Showed how superadditive functions can be used to obtain valid inequalities for mixed integer programs (MIPs). Derived Gomory mixed-integer cuts as an example. Described the idea of how (valid) inequalities may be lifted to obtain facet-defining inequalities by considering the stable-set polytope and odd-hole inequalities.
• Mar 6: Proved lemma about one-variable lifting showing that the lifted inequality with the optimal lifting coefficient defines a face of higher dimension. Started with lift-and-project operators. Defined the projection of a polyhedron and showed how to obtain an inequality representation for the projection. Showed that projection may dramatically increase the complexity of description by considering the min s-t cut problem, where a description in RE requires exponentially many facets but there is a compact description in RE+V.
• Mar 9: Described the Balas-Ceria-Cournuéjols (BCC) lift-and-project method. Proved that given a [0,1]-polyhedron K, if the method is applied to a variable xj, then the resulting polyhedron Pj(K) is the convex hull of {xK: xj{0,1}}. Proved that the result of lifting multiple variables one-by-one is sequence-independent, and lifting all variables yields KI.
• Mar 11: Described the Lovász-Schrijver (LS), the LS positive-semidefinite, and the Sherali-Adams lift-and-project operators, and showed how they relate to the BCC operator.
• Mar 13: Started with solution methods for integer programming. Described the generic cutting plane algorithm. Showed that given a procedure for generating cuts described as an operator, if the resulting polyhedron has a "compact" description, then one can determine if the current fractional point belongs to this polyhedron and separate it if it doesn't.
• Mar 16: Showed how the above can be applied to the BCC lift-and-project operator. Gave an overview of the simplex method. Showed how a Gomory cut and Gomory mixed-integer cut can be generated from the final simplex tableaux. Stated that the cutting plane method with Gomory cuts has finite convergence.
• Mar 18: Described the generic branch-and-bound (BnB) approach. Showed how maintaining lower and upper bounds in the BnB method can enable one to prune portions of the BnB tree and avoid complete enumeration. Briefly discussed the questions of (1) how one obtains and maintains such bounds, (2) the BnB tree exploration strategy, and (3) the branching/division strategy.
• Mar 20: Described a few most-commonly used branching strategies. Started with computational complexity. Defined a decision problem, the classes P and NP, and gave some examples.
• Mar 23: Defined the notion of a polytime reduction. Gave the definition of an NP-complete (and NP-hard) problem. Stated that 3-SAT is NP-complete, and used this to prove that the stable-set problem is NP-complete. Started the topic of separation vs. optimization. Stated the three basic problems of optimization, feasibility, and separation, and stated that all three are polytime equivalent.
• Mar 25: Briefly sketched how the (approximate) optimization problem can be reduced to (the non-decision version of) the feasibility problem via binary search. Started with the ellipsoid method that shows how the feasibility problem can be reduced to the separation problem. Defined separation oracle, ellipsoid, affine transformation, and the notion of volume.
• Mar 27: Stated the volume-reduction property of ellipsoids. Described and analyzed the Ellipsoid method assuming the underlying set K is closed, convex, contained in a bounding ball, and contains a ball. Mentioned how the Ellipsoid method can be modified for linear optimization.
• Mar 30: Mentioned the issue of precision that arises in the Ellipsoid method. Described applications of the Ellipsoid method to combinatorial optimization, where it is often "easy" to obtain a separation oracle, and ensure that the assumptions of boundedness and enclosing-ball hold, by adhoc means if necessary. Considering the minimum s-t cut, minimum Steiner tree LP relaxations, and the Maxcut semidefinite-programming relaxation as examples.
• Apr 1: Showed how the assumption of boundedness can be removed for polyhedra. Proved that if K is full-dimensional, then it contains a ball of radius r, where ln(1/r) is polynomially bounded.
• Apr 3: Showed how the full-dimensionality assumption can be dropped for an explicitly-described polyhedron K by perturbing the RHS of the constraints. Described how the resulting decision procedure for the feasibility problem can also be used to find a feasible solution via self-reducibility. Showed how the separation problem can be reduced to the optimization problem, by noting that it can be cast as a feasibility problem for a polyhedron with a separation oracle whose inequalities have a compact description. Gave submodular-function minimization as an example.

## Prerequisites

Knowledge of linear programming at the level of CO350 or higher. If you would like to take the course but are unsure about the prerequisites, come and talk to me.

## Collaboration and Cheating Policy

You are allowed to collaborate on assignments (unless otherwise indicated), but instances of collaboration should be within reason. You are urged to attempt solving the assignment questions yourself before seeking external help.
You must write up the solutions individually and acknowledge all sources of external help (collaborators, books/papers consulted etc.). Failure to do so constitutes cheating and will be dealt with severely.

## Books and Supplementary Material

There is no prescribed textbook for this course. The following books may be used as reference books. The first two books cover many of the topics that we will cover in class, however the treatment in these books is often at a more advanced level.

• Integer and Combinatorial Optimization, G. Nemhauser and L. Wolsey. Wiley Interscience, 1988.
• Theory of Integer and Linear Programming, A. Schrijver. Wiley Interscience, 1998.
• Combinatorial Optimization, B. Cook, B. Cunningham, B. Pulleyblank, and A. Schrijver. Wiley Interscience, 1998.

Some of these books will be placed on reserve at the library.

## Tentative list of topics

Some subset of the following topics will be covered. If you would really like some topic that is not here to be covered, come and talk to me.

1. Cones, convexity, Farkas' lemma and its geometric interpretation.

2. Polyhedral theory.
• Polytopes, faces, dimension of polyhedra
• Integral polyhedra: total unimodularity, total-dual-integrality
• Algebraic and optimization techniques for proving integrality of polyhedra
• Applications of polyhedral theory to combinatorial optimization

3. Modeling and formulations, strengths of formulations.

4. Valid inequalities and procedures for generating them.
• Chvátal-Gomory cuts
• Lift and project methods: the Balas-Ceria-Cornuéjols, Sherali-Adams, and Lovász-Schrijver procedures
• Rank of a valid inequality

5. Algorithms for solving integer linear programs.
• Cutting-plane algorithms
• Branch and bound
• Duality in integer optimization and its algorithmic consequences
• Complexity of integer programming
• Algorithms for special classes of problems

6. Separation vs. optimization.