Contact Name: Prof. Paolo Toth
Abstract
We discuss the relationship between standard intersection cuts (SIC's), generalized intersection cuts (GIC's) and lift-and-project (L&P) cuts. It is known that (L&P) cuts from split disjunctions are equivalent to (SIC's) and (GIC's). We show that this equivalence does not hold for L&P cuts from other types of disjunctions (multiple-term or non-split). Our main findings are as follows.
GIC's and L&P cuts. The family of GIC's from a given lattice-free polyhedron S is equivalent to the family of L&P cuts from a Cut Generating Linear Program (CGLP) based on a disjunction whose terms are the weak complements of the inequalities defining S. The family of L&P cuts from a disjunction D with multiple inequalities per term is equivalent to the family of GIC's from the lattice-free polyhedra obtained from the disjunction D by combining the inequalities of each term of D, and taking the weak complements of the resulting inequalities to obtain the polyhedra.
SIC's and L&P cuts from multiple-term or non-split disjunctions. Each SIC is equivalent to a L&P cut from a CGLP solution with a certain property P. The property P of the CGLP solution is necessary and sufficient for the resulting L&P cut to be equivalent to a SIC. CGLP solutions with property P (and associated L&P cuts) are called regular, those without the property are called irregular. If the CGLP solution that maximizes the depth of the L&P cut relative to the LP optimum is irregular, then the associated L&P cut cuts off the LP optimum by more than any intersection cut from the same lattice-free set, and is not dominated by any such intersection cut.
L&P cuts and corner polyhedra. It has recently been established that all the facets of corner polyhedra are defined by SIC's. We show that, by contrast, GICs that are L&P cuts from irregular CGLP solutions may cut off integer points of corner polyhedra. Irregular CGLP solutions are not exceptional, their frequency is comparable with that of regular solutions, and increases with the number of terms in the disjunction underlying the CGLP.
About the speaker
Egon Balas is University Professor of Industrial Administration and Applied Mathematics, as well as the Thomas Lord Professor of Operations Research, at Carnegie Mellon University. He has a doctorate in Economic Science from the University of Brussels and a doctorate in Mathematics from the University of Paris.
Dr. Balas’ research interests are in mathematical programming, primarily integer and combinatorial optimization. He has played a central role in the development of enumerative and cutting plane techniques for 0-1 programming. In the mid-sixties he wrote a pioneering paper on implicit enumeration, which later became a Citation Classic as the most frequently cited paper of the journal Operations Research between 1954 and 1982.
In the 70’s he developed a theory for optimization over unions of polyhedra, known as disjunctive programming, which has formed the basis of numerous subsequent developments in cutting plane theory for integer and combinatorial optimization. In particular, the lift-and-project approach developed in the 90's by Balas and his coworkers has played a crucial role in the revolution in the state of the art in Integer Programming that occurred during that decade.
Balas also contributed theory and algorithms for various combinatorial optimization problems, like set packing and covering, traveling salesman and its generalizations, knapsack, three dimensional assignment, vertex separator, etc. On the practical side, he has developed various scheduling algorithms and software.
Dr. Balas has taught a variety of courses at different levels, and has acted as thesis advisor to 31 doctoral students. He has served or is serving on the editorial boards of numerous professional journals.
In 1980 Balas received the US Senior Scientist Award of the Alexander von Humboldt Foundation. In 1995 he was awarded the John von Neumann Theory Prize of INFORMS, and in 2001 he received the EURO Gold Medal of the European Association of Operational Research Societies. In 2002 Balas became a Fellow of INFORMS; in 2004 he was elected an external member of the Hungarian Academy of Sciences; in 2006 he was inducted into the National Academy of Engineering and into the IFORS (International Federation of Operational Research Societies) Hall of Fame. In 2011 he became a member of the Academy of Science of Bologna.
Balas has honorary doctorates in Mathematics from the University of Elche, Spain (2002), the University of Waterloo, Canada (2005), and the University of Liege, Belgium (2008). Egon Balas has published over 230 articles and studies in the professional literature. He is the author of Will to Freedom: A Perilous Journey Through Fascism and Communism. Syracuse University Press, 2000 (paperback edition 2008), a memoir of his life before migrating to the US, also published in Hungarian (2002), Romanian (2002), French(2003), Italian (2004) and German (2012, paperback edition 2014).