Cutting planes for a mixed-integer program are linear inequalities which are satisfied by all feasible solutions of the latter. These are fundamental objects in mixed-integer programming that are critical for solving large-scale problems in practice. One of the main challenge in employing them is that there are limitless possibilities for generating cutting planes; the selection of the strongest ones is crucial for their effective use. In this thesis, we provide a principled study of the strength of generalpurpose cutting planes, giving a better understanding of the relationship between the different families of cuts available and analyzing the properties and limitations of our current methods for deriving cuts.
We start by analyzing the strength of disjunctive cuts that generalize the ubiquitous split cuts. We first provide a complete picture of the containment relationship of the split closure, second split closure, cross closure, crooked cross closure and tbranch split closure. In particular, we show that rank-2 split cuts and crooked cross cuts are neither implied by cross cuts, which points out the limitations of the latter; these results answer questions left open in [56, 65]. Moreover, given the prominent role of relaxations and their computational advantages, we explore how strong are cross cuts obtained from basic and 2-row relaxations. Unfortunately we show that not all cross cuts can be obtained as cuts based on these relaxation, answering a question left open in [56]. One positive message from this result, though, is that cross cuts do not suffer from the limitations of these relaxations.
Our second contribution is the introduction of a probabilistic model for comparing the strength of families of cuts for the continuous relaxation. We employ this model to compare the important split and triangle cuts, obtaining results that provide improved information about their behavior. More precisely, while previous works indicated that triangle cuts should be much stronger than split cuts, we provide the first theoretical support for the effect that is observed in practice: for most instances, these cuts have the same strength.
In our third contribution, we study the multi-dimensional infinite relaxation introduced by Gomory and Johnson in the late 60’s, which has been an important tool for analyzing and obtaining insights on cutting planes. The celebrated Gomory- Johnson’s 2-Slope Theorem gives a sufficient condition for a cut to be facet defining from the 1-row infinite relaxation. We provide an extension of this result for the k-row case, for arbitrary k, which we call the (k + 1)-Slope Theorem. Despite increasing interest in understanding the multi-row case, no such extension was known prior to our work. This result, together with the relevance of 2-slope functions for the 1-dimensional case, indicates that (k + 1)-slope functions might lead to strong cuts in practice.
In our fourth contribution, we consider cuts that generalize Gomory fractional cuts but take into account upper bounds imposed on the variables. More specifically, we revisit the lopsided cuts obtained recently by Balas and Qualizza via a disjunctive procedure. We give a geometric interpretation of these cuts, viewing them as cuts for the infinite relaxation that are strengthened by a geometric lifting procedure. Using this perspective, we are able to generalize these cuts to obtain a family of cuts which has on one end the GMI cut, and on the other end the lopsided cuts. We show that all these cuts are “new”, namely they are all facets of the infinite relaxation with upper bounded basic variable. We conclude by presenting preliminary experimental results, which unfortunately shows that these cuts decrease in importance as they move away from the GMI inequality, complementing the experimental results from Balas and Qualizza.
In our final contribution, we further explore properties and characterizations of split cuts, focusing on a general model of mixed-integer corner relaxation. The backbone of this work is a description of the split cuts for this relaxation from the perspective of cut-generating functions; this essentially establishes the equivalence of split cuts and (a generalization of) the k-cuts [50]. As our previous result, this characterization is obtained using the geometric lifting idea, illustrating its flexibility as a tool for analyzing cuts. As a consequence, we show that every split cut for a corner relaxation is the restriction of a split cut for the mixed-integer infinite relaxation, which further indicates the universality of the latter. As another consequence, we construct a pure-integer set with arbitrarily weak split closure, giving a pure-integer counterpart of the mixed-integer construction from [27].
| Identifer | oai:union.ndltd.org:cmu.edu/oai:repository.cmu.edu:dissertations-1254 |
| Date | 01 January 2013 |
| Creators | Molinaro, Marco |
| Publisher | Research Showcase @ CMU |
| Source Sets | Carnegie Mellon University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Dissertations |
Page generated in 0.0165 seconds