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. SpringerVerlag, 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 takehome 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 nonempty (otherwise the correspondence between pointedness of Q and
fulldimensionality of proj_{J}(P_{I}) 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
∑_{i∈E(C)} x_{i} ≤ C1.
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
l ≤ x ≤ u. 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, y ≤ x
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 passwordprotected 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 nonempty.
 In Q2, it should be y^{T}A=c^{T} in the dual.
 In Q3(b), z is nonzero.
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 nonempty set is a face of a polyhedron
P = {x: Ax ≤ b} iff it can be written as
{x∈P: 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 oneone 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 c^{T}x
s.t. x∈P 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
{x∈R^{E}:
x(δ(v)) ≤ 1 for all v,
0 ≤ x_{e} ≤ 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
q_{v}, b_{v} respectively on the degree x(δ(v))
of each node v, and where l_{e} ≤ x_{e} ≤
u_{e} for every edge e (with l_{e}, u_{e}
integer), if nonempty has integral extreme points.
 Feb 4: Started with modeling and formulations. Proved that the knapsackpolytope is
fulldimensional and identified certain valid and facetdefining inequalities.
Started with the stableset problem, showed the stableset polytope is fulldimensional
and gave two formulations for it.
 Feb 6: Stableset contd. Showed that the formulation with clique inequalities is
stronger, and argued that the cliqueinequalities are facetdefining. Briefly considered
the formulation with oddcycle inequalities, and its relation to the formulation with
only edgeinequalities, 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 mn, where m=n(n1)/2
is the number of edges of an nnode complete graph.
 Feb 11: Proved that the subtourelimination constraints define facets of the TSP
polytope. Introduced network flow problems, defining the mincost flow problem.
 Feb 13: Defined fixedcharge flow problems. Defined the ≥, ≤, and = versions of
the singlenode fixedcharge (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 1620: 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 booleanlogic 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átalGomory (CG) procedure for automatically generating valid inequalities, and
gave some examples. Defined the notion of Chvátalrank of an inequality.
 Feb 27: Proved that starting with the feasible region P of an LPrelaxation of
a {0,1}IP, every valid inequality for P_{I} 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 mixedinteger cuts as an example. Described
the idea of how (valid) inequalities may be lifted to obtain facetdefining inequalities
by considering the stableset polytope and oddhole inequalities.
 Mar 6: Proved lemma about onevariable lifting showing that the
lifted inequality with the optimal lifting coefficient defines a face of higher
dimension. Started with liftandproject 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
st cut problem, where a description in R^{E} requires
exponentially many facets but there is a compact description in R^{E+V}.
 Mar 9: Described the BalasCeriaCournuéjols (BCC) liftandproject
method. Proved that given a [0,1]polyhedron K, if the method is applied to a
variable x_{j}, then the resulting polyhedron
P_{j}(K) is the convex hull of
{x∈K:
x_{j}∈{0,1}}. Proved that the result of lifting
multiple variables onebyone is sequenceindependent, and lifting all variables yields
K_{I}.
 Mar 11: Described the LovászSchrijver (LS), the LS positivesemidefinite, and
the SheraliAdams liftandproject 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 liftandproject operator. Gave
an overview of the simplex method. Showed how a Gomory cut and Gomory mixedinteger 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 branchandbound (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 mostcommonly 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
NPcomplete (and NPhard) problem. Stated that 3SAT is NPcomplete, and used this to
prove that the stableset problem is NPcomplete. 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 nondecision 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 volumereduction 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 enclosingball hold, by adhoc means if necessary. Considering the minimum
st cut, minimum Steiner tree LP relaxations, and the Maxcut
semidefiniteprogramming relaxation as examples.
 Apr 1: Showed how the assumption of boundedness can be removed for polyhedra. Proved
that if K is fulldimensional, then it contains a ball of radius r, where
ln(1/r) is polynomially bounded.
 Apr 3: Showed how the fulldimensionality assumption can be dropped for an
explicitlydescribed 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 selfreducibility.
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 submodularfunction 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.
 Cones, convexity, Farkas' lemma and its geometric interpretation.
 Polyhedral theory.
 Polytopes, faces, dimension of polyhedra
 Integral polyhedra: total unimodularity, totaldualintegrality
 Algebraic and optimization techniques for proving integrality of polyhedra
 Applications of polyhedral theory to combinatorial optimization
 Modeling and formulations, strengths of formulations.
 Valid inequalities and procedures for generating them.
 ChvátalGomory cuts
 Lift and project methods: the BalasCeriaCornuéjols, SheraliAdams, and
LovászSchrijver procedures
 Rank of a valid inequality
 Algorithms for solving integer linear programs.
 Cuttingplane algorithms
 Branch and bound
 Duality in integer optimization and its algorithmic consequences
 Complexity of integer programming
 Algorithms for special classes of problems
 Separation vs. optimization.
