IBM Watson Research Center, Yorktown Heights, NY

**Organizers:****William Cook**, Rice University, bico@caam.rice.edu**William Pulleyblank**, IBM Watson Research Center, pblk@us.ibm.com

1. Integer Relaxations and Basis Reduction Karen Aardal Utrecht University For many integer and combinatorial optimization problems algorithms based on linear relaxations, such as branch-and-cut, have been very successful. In some cases though these methods fail. Here we present an approach for solving integer programming problems based on integer relaxations. To formulate the relaxations we use lattice basis reduction. We illustrate the approach on a few problem types and attempt to give an idea why integer relaxations may work better than linear relaxations for these problems. We also report on some computational results. This talk is based on joint work with Bob Bixby, Cor Hurkens, Arjen Lenstra, and Job Smeltink. 2. Disjunctive Programming Revisited Egon Balas Carnegie Mellon University Mathematical drama in two acts. Act I. Scene: the seventies. Intersection cuts, outer polars, disjunctive cuts. The convex hull of a union of polyhedra. Facial disjunctive sets, sequential convexification. Monoidal cut strengthening. Poor computational results. Act II. Scene: the nineties. Disjunctive programming rediscovered. Reformulation- linearization. Matrix cones. Lift-and-project. Cut lifting. Implementation: branch-and-cut; restrict to subspace, lift (reformulate), project back, lift and strengthen cuts. Major computational success, at long last. 3. On the volume algorithm and some combinatorial linear programs Francisco Barahona IBM T.J. Watson Research Center We present an extension to the subgradient algorithm to produce primal as well as dual solutions. It can be seen as a fast way to carry out an approximation of Dantzig-Wolfe decomposition. This gives a fast method for producing approximations for large scale linear programs. It is based on a new theorem in linear programming duality. We present successful experience with large linear programs coming from set partitioning, airline schedule planning, facility location, Steiner tree problems, and max-cut. 4. Approximately Solving some Large-Scale Linear Programs Dan Bienstock Columbia University We present computational experience with an implementation of the Grigoriadis-Khachiyan-Plotkin-Shmoys-Tardos exponential penalty method for block-structured linear programs. Together with a procedure for strengthening Lagrangian relaxations, this yields a fast approximation algorithm that yields very promising results when applied to relaxations of large-scale mixed-integer programs arising in network design. 5. Finiteness Proofs as of 1999 Charles Blair University of Illinois Ralph Gomory's paper on cutting-plane methods for integer programs contains the intriguing remark: ``...in all problems done so far, ANY method involving the reduced inequalities has worked. It would be desirable to know whether or not this is true in general.'' We investigate various aspects of this problem. 6. Gomory Cuts, Revisited Sebastian Ceria Columbia University In this talk we discuss several computational experiments with Gomory cuts on a wide range of general mixed-integer programs. We show that a branch-and-cut system that incorporates these cuts can be used effectively to solve problems that are not easily solvable without cutting planes. Our results challenge the widely-held belief that Gomory cuts are numerically unstable, and that they cannot be used effectively within commercial software. This work was first presented in a meeting in Giens, France, in 1993. 7. Gomory Cuts and Combinatorial Reasoning Vasek Chvatal Department of Computer Science Rutgers University Gomory's cutting-plane algorithms for integer linear programming problems provide a framework for formalizing combinatorial proofs. I will survey a few aspects of these cutting-plane proof systems. 8. Decomposition of Balanced Matrices Gerard Cornuejols Carnegie Mellon University A 0,1 matrix is balanced if it does not contain a square submatrix of odd order with two ones per row and per column. In this talk, I will present a result obtained in collaboration with M. Conforti and M. R. Rao. We show that a balanced 0,1 matrix is totally unimodular or its bipartite representation has a cutset consisting of two adjacent nodes and some of their neighbors. This result yields a polytime recognition algorithm for balancedness. 9. Optimal 3-terminal Cuts and Linear Programming William H. Cunningham University of Waterloo Given an undirected graph and three specified terminal nodes, a 3-terminal cut is a subset of edges whose deletion leaves the terminals in different components. The optimal 3-terminal cut problem is the problem of finding such a set having minimum weight. It is NP-hard, and in fact, is max-SNP-hard. Calinescu, Karloff, and Rabani (1998) analyzed a certain integer linear programming formulation, and showed that the ILP optimal value is at most 6/5 times the LP optimal value. We improve this bound to 12/11, and show that this is best possible. As a consequence, we can find efficiently a feasible solution to the ILP of value at most 12/11 times the optimal value. This is joint work with Lawrence Tang, University of British Columbia. 10. Using a Parallel Branch Cut and Column Generation Framework to Solve Some Difficult MIPLIB Problems. John Forrest IBM T.J. Watson Research Center IBM Research has developed a Parallel Branch and Cut and/or Column generation framework. In order to stress it, and test cut generators and column generators, three of the miplib test set which have no published optimal solutions were tackled. These were mkc, swath and seymour. In addition a larger more realistic version of mkc (which comes from an IBM solution for Steel Mills) was also attempted. The Parallel framework will be described and the results achieved on the test set will be given. 11. Linear Programming Relaxations Arising from Cooperative Game Theory Michel X. Goemans MIT We consider combinatorial optimization problems from a cooperative game theory standpoint. The goal is to assign the total cost of a project between the different participants, in such a way that no group of participants, or coalition, is charged more than the cost of the sub-project they induce on their own. We show that a canonical LP relaxation plays a very special role. All the concepts are illustrated on TSP games and facility location games. 12. Corner Polyhedra and their Connection with Cutting Planes. Ralph Gomory Alfred P. Sloan Foundation This talk will review the theory of Corner Polyhedra, point out some of their properties and sructure, and show how knowledge of Corner Polyhedra can be used to generate cutting planes for integer programming. The connection iof Corner Polyhedra with cutting planes is through using the fractional elements that appear in Gomory cuts not directly as cutting planes but rather as group characters. 13. Boolean Optimization Peter L. Hammer RUTCOR, Rutgers University A Boolean Optimization problem is defined as the problem of maximizing a real-valued linear function f(X), subject to g(X) = 0, where X is a 0-1 vector, and g(X) is a Boolean function, assumed to be given in disjunctive normal form. Typical problems of this type include the weighted versions of the set covering, graph stability, maximum satisfiability, and many other problems. Also, a wide class of problems, including those of linear 0-1 programming, have readily available relaxations in this class. The paper will present classes of polynomially solvable problems, preprocessing methods, and heuristic and exact algorithms for the solution of Boolean optimization problems, along with some preliminary results obtained in ongoing computational experiments, carried out jointly with Bela Vizvari and Thomas Davoine. 14. Minimum Cuts in Networks T.C. Hu University of California at San Diego We study the problem of getting minimum cuts without obtaining maximum flows. We give various formulations for defining the Gomory-Hu cut tree and random approximation algorithms. 15. Facets for Cycic Group Polyhedra and Knapsack Polytopes Ellis Johnson Georgia Institute of Technology Some theorems and examples from Gomory's group development and extensions to knapsack problems will be presented. Connections between problems and constructive ways to get facets will be emphasized. 16. ABACUS - A Branch-And-CUt System Michael Junger Universitat Koln In 1958, Ralph Gomory presented an elegant algorithmic solution to the integer linear programming problem. He not only invented the cutting plane method and proved its finiteness and correctness, but he also implemented it on an E101 computer in order to see how it performs. Today, branch-and-cut-and-price algorithms belong to the most successful techniques for solving mixed integer linear programs and combinatorial optimization problems to optimality (or, at least, with certified quality). However, in the early eighties there were only few computational studies due to the fact that implementing a branch-and-cut-and-price algorithm from scratch requires a lot of work, even with an LP-solver available. Since then, software systems have been developed that facilitate the development of such software by allowing the implementor to concentrate on the problem specific parts only. The ever growing knowledge about algorithmic techniques calls for much more convenient systems if we want to maintain the good tradition in mathematical programming that new methods should be demonstrated to actually solve the problems that led to their development, in the spirit of George B. Dantzig, Ralph E. Gomory and other pioneers in mathematical programming. We observed that existing systems are strong for the solution of general (mixed) integer optimization problems, but not as convenient for the solution of hard combinatorial optimization problems as we would like them to be. This was the ``algorithmic motivation'' for the development of ABACUS, a software framework for the implementation of branch-and-cut-and-price algorithms. We also recognized that the realization of such a system in a non-object-oriented programming language is difficult in its implementation, and---even worse---inconvenient and unsafe in its application. The ``software motivation'' for our work on ABACUS was that many of these problems evaporate if object oriented design principles and programming languages are used. We briefly sketch the design criteria, the basic design ideas, and the implementation of ABACUS in C++. Then we point out some features of combinatorial optimization problems and show how they are handled by ABACUS. Finally, we report on a variety of successful applications of ABACUS. 17. Maximum Mean Weight Cycle and Cycle Optimization of Gigahertz Processors Bernhard Korte University of Bonn We consider the problem of finding an optimal clock schedule, i.e. optimal arrival time for clock signal at latches of VLSI-chips. We show how to optimize the cycle time and optimally balance slacks on datapaths and on clock tree paths. We give a combinatorial algorithm, which solves this problem optimally. This algorithm is an extension and modification of the algorithm for the maximum mean weight cycle problem. 18. Designing Restorable Telecommunication Networks: A Variant of Gomory-Hu Network Synthesis Thomas L. Magnanti MIT In a classical 1961 paper, Gomory and Hu described a procedure for designing a network with the least possible total capacity to meet prescribed point-to-point demand between nodes of a potential network. We consider a variant with an apparently modest twist: the demand between two nodes cannot flow directly on an edge joining these nodes. This problem arises in designing restorable telecommunication networks where the demand corresponds to current flow and we wish to install spare capacity to redirect flow, using alternative edges, when an edge fails. We examine the polyhedral structure of an integer programming formulation of this problem and report on computational experience in solving real world problems. This talk is based on joint work with Yi Wang, I2 Technologies. 19. Large-scale Integer Programming in Airline Scheduling George L. Nemhauser Georgia Tech Nearly 40 years ago, Paul Gilmore and Ralph Gomory did pioneering work on delayed column generation techniques for solving the linear programming relaxation of the cutting stock problem, which contains an astronomical number of variables. Airline crew scheduling problems also lead to models with an astronomical number (millions or billions) of columns. Millions of dollars can be saved annually by obtaining very high quality solutions to these models. We present recently developed techniques for solving the linear programming relaxation and 0-1 integer programming model of these problems. 20. Small Polytopes and Branch & Cut Gerhard Reinelt University of Heidelberg Essential for the success of branch-and-cut algorithms for solving combinatorial optimization problems are the availability of reasonable tight relaxations and effective routines for solving the associated separation problems. In this talk we discuss the concept of small instance relaxations which can be particularly useful for problems with symmetric structure. Small instance relaxations base on the facets of polytopes associated with small instances of the combinatorial optimization problem to be solved and can be generated automatically by facet enumeration. For a certain class of symmetric problems, we describe a general approach to the separation problem. Algorithmic aspects of using small instance relaxations effectively (parallel separation, facet selection, cutting plane selection) are discussed in detail. Computational results are presented for the linear ordering problem and a certain betweenness problem. 21. Gomory Cuts and Commercial Software Martin W.P. Savelsbergh Georgia Institute of Technology For a long time, Gomory's seminal work on cutting planes has been considered to be only of theoretical interest. However, this view has changed in the last couple of years when implementations of branch-and-cut algorithms based on Gomory cuts were shown to be able to successfully solve various difficult integer programs. XPRESS-MP is among the few commercially available mixed integer optimizers that has incorporated Gomory cuts in its default branch-and-cut solver. In this talk, we present the results of a series of computational experiments with XPRESS-MP's branch-and-cut solver and analyze the value of Gomory cuts in the solution of difficult integer programs. 22. On Empty Lattice-Simplices Andras Sebo IMAG, Grenoble We study the complexity of deciding when given lattice-simplices are empty, that is, do not contain lattice-points besides the vertices. We show how some particular Gomory-Chv\'atal cuts provide good certificates for this property in small dimensions. The problem is embedded into a more general context of linear inequalities satisfied by the so called `parallelepiped coefficients', and the `Lonely Runner Problem' is formulated as a first application of these. An improved lower bound for the maximum width of $n$-dimensional empty simplices will also be shown. 23. Stable Set Polytopes and Rank One Constraints Bruce Shepherd Lucent Technologies We discuss two questions. How can one recognize if the stable set polytope of a graph is not given by the rank-one constraints - starting from from the clique inequalities? How can one recognize the infamous class of paritionable graphs? Both questions appear to require a better understanding of the theory of Gomory cuts. 24. Commutative Algebra and Integer Programming Bernd Sturmfels University of California at Berkeley Abstract: During the past five years surprising interactions emerged between integer programming theory and commutative algebra. Grobner bases have been used to study and solve integer programs, Gomory's group approach has been reexamined in terms of localizations of toric ideals, and Scarf's work on test sets has inspired significant developments on minimal free resolutions. The purpose of this lecture is to present two specific new results, which are important for the algebraic theory of integer programming: (1) The six-dimensional counterexample found by Bruns and Gubeladze for the Integer Caratheodory Property of Hilbert bases. (2) The Chain Theorem proved by Hosten and Thomas for the optimal points of a family of integer programs. 25. Adventures in Sports Scheduling Michael Trick Carnegie Mellon University The need to create quality sports schedules quickly in practice leads to a number of interesting research directions. Work on schedules for Major League Baseball and a number of college basketball leagues has led to work in integer programming, including column generation techniques based on the pioneering work of Gilmour and Gomory. Other techniques used include network flows, matching, and constraint programming. 26. New Separation Procedures for Vehicle Routing Les Trotter Cornell University We consider the capacitated vehicle routing problem (VRP): a fixed fleet of delivery vehicles of uniform capacity must service at minimal transit cost from a common depot known customer demand for a single commodity. This problem is modeled as a side-constrained traveling salesman problem (TSP). Among the additional constraints are the vehicle capacity restrictions, analogous to TSP subtour elimination constraints. We present several variants of a branch-and-cut algorithm for this VRP model, with separation methodology for the capacity restrictions based on the TSP polyhedral relaxation. Specifically, when standard procedures fail to separate a candidate point, we attempt to separate it via decomposition into a convex combination of TSP tours; if successful, the tours present in this decomposition are examined for violated capacity restrictions, and if not, the Farkas Theorem provides a hyperplane separating the point from the TSP polytope. Computational results are given for an implementation the platform is the IBM SP2 of the Cornell Theory Center. Our results include the first reported solution to optimality of two large-scale VRP models taken from the standard literature for this problem. 27. Hilbert bases in Integer Programming Robert Weismantel Otto-von-Guericke Universit"at Magdeburg It is known for many years that Hilbert bases play a central role in Integer Programming. Their applications range from totally dual integral systems of inequalities over estimates of distances between lattice points to simultaneous diophantine approximation of rationals and the design of augmentation algorithms. It is the latter application that will be central for the talk. More precisely, we will analyze the geometry, complexity issues and the combinatorics of augmentation algorithms. Our analysis will show an analogy to cutting plane methods. It will also provide a link to the fundamental work of Ralph Gomory. 28. Two-dimensional Gantt charts and a scheduling algorithm of Lawler David P. Williamson IBM T.J. Watson Research Center In this talk I will give an alternate proof that a scheduling algorithm of Lawler finds the optimal solution for scheduling a single machine to minimize the weighted sum of completion time when the jobs have precedence constraints that are series-parallel. To do this I will use a linear programming formulation of this problem introduced by Queyranne and Wang, and geometrical arguments based on what might be called "two-dimensional Gantt charts". Queyranne and Wang proved that their formulation completely describes the scheduling polyhedron in the case of series-parallel constraints; a by-product of our proof of correctness of Lawler's algorithm is an alternate proof of this fact. It seems likely that these 2D Gantt charts may find independent use, and to illustrate this I will show that some recent work in the area becomes transparent using 2D Gantt charts. 29. Aggregation and Mixed Integer Rounding to solve MIPs Laurence A. Wolsey CORE Mixed integer rounding (MIR) inequalities are essentially Gomory mixed integer cuts. However it is important that MIR inequalities be generated from constraints or aggregation of a small number of constraints of the original problem in an attempt to use problem structure. This viewpoint is strengthened by the observation that a variety of strong valid inequalities derived earlier using structure are just such MIR inequalities. Results are presented showing that a branch-and-cut approach, based on a row aggregation heuristic to generate a knapsack constraint with continuous variables, followed by generation of an MIR inequality on the aggregate constraint, is effective in tacking a variety of mixed integer programming problems. 30. Many ``facets of complexity' of 0/1-polytopes and 0/1-programs Gunter M. Ziegler TU Berlin This will be a survey lecture about the geometry of 0/1-polytopes and 0/1-programs. These are complicated and complex in many different ways: for example, the number of facets can be huge, the coefficients in their defining inequalities may turn out to be huge, and the Chv\'atal-Gomory ranks may be large. I also will try to explain why some of this complexity cannot be detected in ``small examples.''Other Workshops

DIMACS Homepage

Contacting the Center

Document last modified on July 20, 1999.