Carnegie Mellon University
Browse

Non-Recursive Cut Generation

Download (9.42 MB)
thesis
posted on 2018-04-01, 00:00 authored by Aleksandr KazachkovAleksandr Kazachkov

There has recently been reinvigorated interest in finding new general-purpose cutting planes (cuts) for mixed-integer programs, particularly ones that can be derived from valid general disjunctions. This dissertation focuses on the theoretical and computational development of new disjunctive cuts. The motivation is primarily practical: cuts are a critical component of modern integer programming solvers, but the families of cuts that are currently implemented are relatively simple and suffer from numerical instability and the “tailing off” effect when used recursively. We introduce three techniques for efficiently generating a large number of strong cuts without recursion, prove useful theoretical properties of the cuts, and perform computational testing of their performance through implementations in the open source COIN-OR framework. Our evaluation criteria are strength (compared to Gomory cuts) and time (via branch-and-bound tests). In our first contribution, we investigate generalized intersection cuts, a relatively recent approach with attractive theoretical properties. We first observe that a key hyperplane activation procedure embedded in this previously computationally unexplored paradigm is not computationally viable. We overcome this issue by a novel technique called partial hyperplane activation (PHA), introduce a variant of PHA based on a notion of hyperplane tilting, and prove the validity of both algorithms. We propose several implementation strategies and parameter choices for our PHA algorithms and provide supporting theoretical results. The accompanying computational findings shed light on the strengths of the PHA approach and identify properties related to strong cuts that we subsequently use. The next chapter examines a notion of tilting that can be used to produce cutting planes from split disjunctions starting from any given valid inequality. Geometrically, this tilting involves changing the angle of the given inequality until it becomes supporting for both sides of the disjunction. We provide computational experience with the strength and practicality of this procedure and make connections with existing literature for which tilting offers a unifying perspective. We then introduce V-polyhedral cuts for generating valid inequalities from general disjunctions. We show how to efficiently obtain points and rays from which we build a linear program whose feasible solutions correspond to valid disjunctive cuts. This linear program is much smaller than the one from the alternative approach, lift-and-project, enabling us to test larger disjunctions that arise from the leaf nodes of a partial branch-and-bound tree. We show that the cuts from one strong disjunction significantly improve the gap closed compared to cuts produced from a union of many shallow disjunctive sets. Our cuts also decrease Gurobi solving time. However, this hinges on choosing the best partial tree size per instance, which remains an open problem and motivates future work on better understanding the interaction between branch-and-bound and cuts. Finally, the last chapter builds a correspondence between lift-and-project and V-polyhedral cuts. The motivation is finding the necessary ingredients to apply standard cut strengthening techniques such as modularization to the more efficiently generated V-polyhedral cuts.

History

Date

2018-04-01

Degree Type

  • Dissertation

Department

  • Tepper School of Business

Degree Name

  • Doctor of Philosophy (PhD)

Advisor(s)

Egon Balas

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC