Math 583, The Theory of Linear and Integer Polyhedra (3 credits), Spring 2008
Instructor : Rekha Thomas
- Office : Padelford C-438
- Phone : (206) 616 9374
- E-mail : rrthomas (at) u (dot) washington (dot) edu
- Office hours : by appointment (in PDL C-438).
- Description : Linear and integer polyhedra play a
fundamental role in many parts of mathematics such as discrete
geometry, optimization and combinatorics and appear in many more areas
of math where they are not usually expected such as algebraic
geometry, mirror symmetry, symplectic geometry and others. They are
the fundamental objects behind linear and integer programming and
other types of optimization problems. This course will develop the
basic theory behind these geometric objects with a view toward
optimization. The meat of the course will be on integer polyhedra that
arise as the convex hull of all lattice points in a rational
polyhedron. This takes one from linear algebra into the much more
complicated world of integer arithmetic which involves number theory,
geometry of numbers and other sophisticated techniques to deal with
arithmetic content. We will develop the basic mathematical theory
behind these objects and spend almost an equal amount of time on the
computational complexity and algorithmic side of the theory.
Main topics to be covered: :
- Basic polyhedral theory
- Basic computational complexity
- Integer linear algebra
- Integer hulls of rational polyhedra
- Applications to linear and integer programming
- Lecture : Padelford C-401, MWF 12:30-1:20
- Textbook : The main part of the course will be based on
the book "Theory of Linear and Integer Programming" by Alexander
Schrijver and some unpublished notes by Les Trotter at Cornell
University. I intend to write lecture notes that will be available
below on this website. Additional, more modern topics will come
from research papers. References will be provided as we proceed.
- Useful Software Packages :
- Homeworks (50% of overall
grade): There will be four sets of homework problems, due
roughly every other week. I will grade about half these problems in
detail. There will be points for completing the each homework set.
- Presentation & Summary Paper (50% of overall grade):
Below, I suggest six broad topics that are related to the material in
this class. Each topic comes with a brief description and a list of
relevant papers. Students (either alone or in an appropriately sized
group) will be expected to pick one of these topics and prepare a
50-minute lecture for the class on this topic. Each lecture should be
accompanied by a summary paper that digests the material in the
various papers into a coherent description of the topic. Think of this
summary paper as the notes for your lecture or a book chapter on this
topic. These notes should be ready for distribution to the class a
week before the lecture and submitted to me for comments a week
earlier than that. These six lectures will be in the last two weeks of
4/25/08: Here is the new policy for homework problems: Please do one
problem (of your choice) per chapter from the lecture notes from among
the problems marked ( HW ).
Due dates for homework problems:
- Chapters 1 & 2: April 25
- Chapters 3,4,5,6: May 7
- 3 problems from Chapters 7-14: by the end of the quarter.
Topics for Presentations
Counting Lattice Points in Polyhedra
Paper from the group
These papers are concerned with the computational complexity of counting lattice points in polyhedra
and related problems. The main results are that these computations can be done in polynomial time if the
dimension is fixed.
- Barvinok, Alexander; "A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed",
Math. Oper. Res. 19 (1994), 769--779.
- (Survey) Barvinok, Alexander and Pommersheim, James E; "An algorithmic theory of lattice points in polyhedra",
New Perspectives in Algebraic Combinatorics (Berkeley, CA, 1996--97), Math. Sci. Res. Inst. Publ., vol. 38,
Cambridge Univ. Press, Cambridge, 1999, pp. 91--147.
- Barvinok, Alexander and Woods, Kevin; "Short rational generating functions for lattice point problems",
J. Amer. Math. Soc. 16 (2003), no. 4, 957--979
- (Representation Theory) Berenstein, Arkady and Zelevinsky, Andrei; "Tensor product multiplicities,
canonical bases and totally positive varieties", Invent. Math. 143 (2001), no. 1, 77--128.
The arithmetic and combinatorics of 0/1 Polytopes
Paper from the group
These papers examine the properties of general 0/1 -polytopes. Again, these polytopes play a fundamental role in
discrete optimization and appear to be simple at first sight. But they have surprising complications and many
interesting and unexpected behaviour. Many open questions remain for 0/1-polytopes.
- (Survey) Ziegler, Guenter M.; "Lectures on $0/1$-polytopes", Polytopes---combinatorics and computation--
--(Oberwolfach, 1997), 1--41, DMV Sem., 29, Birkh Barany, Imre and Por, Attila; "On 0-1 polytopes with many facets", Adv. Math. 161 (2001), no. 2, 209--228.
Convexification processes for 0/1-polytopes
When the integer hull of a rational polytope is a 0/1-polytope there are special methods for
obtaining the integer hull using non-linear methods and semidefinite programming.
Such integer hulls are the bread and butter of combinatorial optimization and underlie numerous applications in
discrete math. These papers outline some of these modern techniques. The paper by Laurent compares all these methods.
- Sherali, Hanif D. and Adams, Warren P; "A hierarchy of relaxations between the continuous and convex hull representations
for zero-one programming problems", SIAM J. Discrete Math. 3 (1990), no. 3, 411--430.
- Lovasz, Laszlo and Schrijver, Alexander; "Cones of matrices and set-functions and $0$-$1$ optimization",
SIAM J. Optim. 1 (1991), no. 2, 166--190.
- Lasserre, Jean B.; "An explicit exact SDP relaxation for nonlinear 0-1 programs", Integer programming and combinatorial
optimization (Utrecht, 2001), 293--303, Lecture Notes in Comput. Sci., 2081, Springer, Berlin, 2001.
- (Survey-like) Laurent, Monique; "A comparison of the Sherali-Adams, Lovasz-Schrijver, and Lasserre relaxations
for 0-1 programming", Math. Oper. Res. 28 (2003), no. 3, 470--496.
The Traveling Salesman Problem
The Traveling Salesman Problem has become a benchmark problem for
testing polyhedral methods in optimization. The convex hull of all
feasible tours is not explicitly known and much effort has gone into
finding facet defining inequalities of the integer hull. The reference
below is to an edited book on this problem. The chapters most relevant to
us will be Chapters 8, 9 & 10 although others might be useful as well.
- (Book) The traveling salesman problem. A guided tour of combinatorial optimization. Edited by E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan and D. B. Shmoys. Reprint of the 1985 original. Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. John Wiley & Sons, Ltd., Chichester, 1990.
The Perfect Graph Theorem
Paper from the group
The perfect graph theorem
was proved by Lovasz in 1972 and says that a graph is perfect if and
only if its complement is perfect. This was the first of the two
"perfect graph conjectures" of Berge from the 1960s. The second, known
now as the "Strong Perfect Graph Theorem" was proved in 2002 by
Seymour et. al. These conjectures have propelled a large part of graph
theory in the last 50 years. Lovasz's proof was built on earlier developments by
Fulkerson who had discovered a polyhedral approach to Berge's
conjecture. These papers examine the main ideas behind the proof.
- Fulkerson, D. R.; "Anti-blocking polyhedra", J. Combinatorial Theory Ser. B 12 1972 50--71.
- Lovasz Laszlo; "Normal hypergraphs and the perfect graph conjecture", Discrete Math. 2 (1972), no. 3, 253--267.
- (Survey) Fulkerson, D. R.; "On the perfect graph
theorem", Mathematical progamming (Proc. Advanced Sem.,
Univ. Wisconsin, Madison, Wis., 1972), 69--76. Math. Res. Center---Publ., No. 30, Academic Press,-- New York, 1973.
Geometry of Numbers and Integer Programming
The geometry of numbers is a fascinating area of number theory that connects the arithmetic of lattice points
to convex geometry. It became a central tool in discrete optimization when Hendrik Lenstra showed that you can use results
from the geometry of numbers to prove that integer programs can be solved in polynomial time when the dimension is
fixed. It has several other offshots in integer programming. These are some of the main papers that apply geometry of
numbers to optimization.
- Lenstra, H. W., Jr. Integer programming with a fixed number of variables. Math. Oper. Res. 8 (1983), no. 4, 538--548.
- Kannan, Ravi and Lovasz, Laszlo; "Covering minima and lattice-point-free convex bodies", Ann. of Math. (2) 128 (1988), no. 3, 577--602
- (Survey) Kannan, Ravi; "Algorithmic geometry of numbers", Annual review of computer science, Vol. 2, 231--267, Annual Reviews, Palo Alto, CA, 1987.
- (Survey) Lovasz, Laszlo, "Geometry of numbers and integer programming"; Mathematical programming (Tokyo, 1988), 177--201,
Math. Appl. (Japanese Ser.), 6, SCIPRESS, Tokyo, 1989.
- Lenstra, A. K. and Lenstra, H. W., Jr. and Lovasz, Laszlo; "Factoring polynomials with rational coefficients", Math. Ann.
261 (1982), no. 4, 515--534.
The Lovasz Theta Number of a Graph
The Lovasz theta number of an undirected graph is an upper bound on the
stability number of the graph. It is the optimal value of a
semidefinite program whose feasible region approximates, from outside,
the stable set polytope of the graph. This work initiated the
mini-industry in optimization that uses semidefinite programming to
approximate problems in discrete optimization. The Goemans-Williamson
approximation to max-cut is another famous example of this technique.
The following papers examine the basic ideas involved here with the
theta number as the main example.
- (Survey) Laurent, Monique and Rendl, Franz;
"Semidefinite Programming and Integer Programming", In Handbook on
Discrete Optimization, K. Aardal, G. Nemhauser, R. Weismantel (eds.),
pages 393-514, Elsevier 2005.
- Lovasz, L; "On the Shannon capacity of a graph", IEEE
Trans. Inform. Theory 25 (1979)
- Lovasz, L and Schrijver; "Cones of matrices and set-functions and 0-1
optimization", SIAM J. Optim. 1 (1991), no. 2, 166--190.