Math 583, The Theory of Linear and Integer Polyhedra (3 credits), Spring 2008

• 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).

Course Information

• 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 :
  
  PORTA
  Polymake
  cdd
  
  

• Assignments

  • 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 the quarter.
    
    

  ---

  Lecture Notes (5/19)

  ---

  Homework Assignments

  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
    
    
    Applications
    
    
    • (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.