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
∑i∈E(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
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 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
{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 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. 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 ≤ xe ≤ 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 le ≤ xe ≤
ue 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
{x∈K:
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.
- Cones, convexity, Farkas' lemma and its geometric interpretation.
- 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
- Modeling and formulations, strengths of formulations.
- 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
- 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
- Separation vs. optimization.
|