On the development of cut-generating functions
Embargo until
Date
2016-12-28
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Johns Hopkins University
Abstract
Cut-generating functions are tools for producing cutting planes for generic mixed-integer sets. Historically, cutting planes have advanced the progress of algorithms for solving mixed- integer programs. When used alone, cutting-planes provide a finite time algorithm for solving a large family of integer programs [12, 70]. Used in tandem with other algorithmic techniques, cutting planes play a large role in popular commercial solvers for mixed-integer programs [9, 34, 35].
Considering the benefit that cutting planes bring, it becomes important to understand how to construct good cutting planes. Sometimes information about the motivating prob- lem can be used to construct problem-specific cutting planes. One prominent example is the history of the Traveling Salesman Problem [43]. However, it is unclear how much insight into the particular problem is required for these types of cutting-planes. In contrast, cut- generating functions (a term coined by Cornu ́ejols et al. [40]) provide a way to construct cutting planes without using inherent structure that a problem may have. Some of the earliest examples of cut-generating functions are due to Gomory [70] and these have been very successful in practice [34]. Moreover, cut-generating functions produce the strongest cutting planes for some commonly used mixed-integer sets such as Gomory’s corner poly- hedron [66, 95].
In this thesis, we examine the theory of cut-generating functions. Due to the success of the cut-generating function created by Gomory, there has been a proliferation of research in this direction with one end goal being the further advancement of algorithms for mixed- integer programs [78, 40, 28]. We contribute to the theory by assessing the usefulness of certain cut-generating functions and developing methods for constructing new ones.
Primary Reader: Amitabh Basu Secondary Reader: Daniel Robinson
Description
Keywords
Integer programming, Cutting planes