| Bert Gerards |
| CWI and Technische Universiteit Eindhoven |
| On Gomory cuts and on Gomory-Hu trees. |
|
We discuss Gomory cutting planes as well as the cutting plane depth
of polyhedra and of matrices. The cutting plane depth of a matrix is
the maximum of the cutting plane depths of all polyhedra with the
matrix as constraint matrix. Cook, Gerards, Tardos and Schrijver,
proved that this depth of matrices is well defined. If time allows we
will present a relatively straightforward proof for this from the fact
that polyhedra have bounded cutting plane depth. In the second part of the talk we discuss finding minimum weight bases in exponentially sized matroids, like the cycle space of a graph. The greedy algorithm by itself does not work as already ordening the elements with respect to the weights takes exponential time. However by a slightly broader perspective on the greedy algorithm it becomes potentially applicable to exponentially sized matroids as well. The approach does not always work, but it does for cycle spaces and cocycle spaces of graphs. The application to cocycle spaces establishes the algorithm for finding Gomory-Hu trees as the greedy algorithm in this exponential matroid. (This comes out of the PhD-thesis of Coelho de Pina.) |
| Laurence A. Wolsey |
| CORE and INMA, Universite Catholique de Louvain |
| Deriving Mixed Integer Cuts and Reformulations from very simple MIPs. |
| By studying valid inequalities for simple mixed integer sets, we show how strong valid inequalities can be obtained for more complex structured MIPs. Examples include problems with variable lower bounds, convex integer programs and lot-sizing problems. Where possible both complete convex hull descriptions and compact extended formulations are derived. The starting point for this approach is the mixed integer rounding inequality for two variable set {(x,y): x+y >=b, x >=0, y integer} which is nothing but the Gomory mixed integer cut from a different viewpoint. |
| Lex Schrijver |
| CWI and Universiteit van Amsterdam |
| Gomory cuts, Gomory-Hu trees, and the traveling salesman problem. |
| Ralph E. Gomory |
| Sloan Foundation |
| T-Space and Cutting Planes |
| This talk describes work done jointly with Ellis Johnson. This talk will explain the basic idea of T-Space and explain how the facets of the Master Polyhedron in T-Space give rise to cutting planes for integer programming and mixed integer programming problems. Ways to actually prove that inequalitiesa are facets will be described and examples of acets and families of facets will also be described. Since this approach gives rise to many families of cutting planes, methods for measuring their likely strength and relation to each other will also be given The challenges of exploring and describing T-Space will be discussed. |