Jointly Optimal Cutting Planes
Abstract
We propose to develop theory and algorithms for the advancement of general purpose cutting planes for solving mixed integer programs. We will study a measure of "strength" that incorporates multiple cutting planes at a time - a group of cutting planes that maximize this strength will call jointly optimal. Our objective is to determine formulas and algorithms to eciently computing jointly optimal cutting planes and demonstrate their eectiveness in commercial and open source software. Cutting planes are fundamental tools used optimization solvers that help make solving large scale optimization problems possible. Specically, a cutting plane (or cut) is an additional inequality added to the problem formulation that improves the description of the feasible decisions. Within a solver, many cuts are added that allow a tight description of the near optimal feasible decisions, and hence make it easier to nd these decisions. Not only is it important to choose good cuts to add, it is also important to add cuts that work well together. Typically this is handled by considering alarge pool of cuts, and then apply a cutting plane selection procedure to determine which ones to add. To highlight the importance of this issue, in a recent survey, Dey and Molinaro [31] express the need to focus on alternative questions in order to better develop the science of cutting-plane selection."We will study the amount of volume cut o by multiple cutting planes at a time. We will use a prominent general relaxation of the original problem with which to study and evaluate so call cut generating functions that provide formulas for cutting planes. Through this study, we will prove theorems establishing conditions under which certain groups of cuts are jointly optimal along withtheoretical guarantees of how much improvement can be gained by adding additional cuts. We will consider the pure integer setting, the mixed-integer setting, settings where coecients come from dierent distributions, and also a new technique of generating an extended formulation (by adding new integer variables) that allow for derivation of much stronger cuts. Technical approaches will begin with a computational framework of computing volume of specicpolyhedra and also generating good cut generating functions for studying. Although volume in general can be very dicult to compute, we will produce ecient algorithms for these polyhedra. This will include analyzing specic polyhedra to understand their structure and determine short formulas that output the volume. We will then use theory of convex analysis, geometry of numbers, and linear algebra to prove results motivated by computations. Lastly, a computational study of the results of our theory will expose problem classes where these techniques are most useful. The anticipated outcome of the research is a theory and application of how to jointly use cutting planes which will result published work, publicly available code for computational studies and also volume computations, and improved ability to solve a variety of problem classes.Impact on DoD capabilities will be that we are more capable of solve large scale optimization problems. In particular, solving mixed-integer optimization problem is crucial for the DoD to im-prove eciency in scheduling, planning, operations, logistics, and many other contexts. Continuing to improve our ability to solve these dicult problems have large eects on many of these areas.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Apr 29, 2020
- Source ID
- N000142012156
Entities
People
- Robert Hildebrand
Organizations
- Office of Naval Research
- United States Navy
- Virginia Tech