Reformulating the disjunctive cut generating linear program
- PDF / 395,992 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 7 Downloads / 207 Views
Reformulating the disjunctive cut generating linear program Thiago Serra1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Lift-and-project cuts can be obtained by defining an elegant optimization problem over the space of valid inequalities, the cut generating linear program (CGLP). A CGLP has two main ingredients: (i) an objective function, which invariably maximizes the violation with respect to a fractional solution x¯ to be separated; and (ii) a normalization constraint, which limits the scale in which cuts are represented. One would expect that CGLP optima entail the best cuts, but the normalization may distort how cuts are compared, and the cutting plane may not be a supporting hyperplane with respect to the closure of valid inequalities from the CGLP. This work proposes the reverse polar CGLP (RP-CGLP), which switches the roles conventionally played by objective and normalization: violation with respect to x¯ is fixed to a positive constant, whereas we minimize the slack for a point p that cannot be separated by the valid inequalities. Cuts from RP-CGLP optima define supporting hyperplanes of the immediate closure. When that closure is full-dimensional, the face defined by the cut lays on facets first intersected by a ray from x¯ to p, all of which corresponding to cutting planes from RP-CGLP optima if p is an interior point. In fact, these are the cuts minimizing a ratio between the slack for p and the violation for x. ¯ We show how to derive such cuts directly from the simplex tableau in the case of split disjunctions and report experiments on adapting the CglLandP cut generator library for the RP-CGLP formulation. Keywords Cutting planes · Lift-and-project · Integer programming
1 Introduction Many optimization problems can be formulated as a Mixed Integer Linear Program (MILP) of n−q the form min{c T x : Ax ≥ b, x ∈ {0, 1}q × R+ }. Some are found more frequently and have been studied in more detail, such as the classic traveling salesman problem, for which families of valid inequalities are known (Applegate et al. 2006). One can tackle an MILP problem by n−q solving its Linear Program (LP) relaxation min{c T x : Ax ≥ b, x ∈ [0, 1]q × R+ } and then iteratively branch to restrict the domains of integer variables or add inequalities of the form α T x ≥ β to separate solutions in which those variables are fractional. These inequalities are
B 1
Thiago Serra [email protected] Bucknell University, 1 Dent Drive, Lewisburg, PA 17837, USA
123
Annals of Operations Research
denoted as cuts with respect to the fractional solutions that they separate, and in many cases the cuts from different methods are equivalent (Balas and Serra 2019). In general, there is a greater and justified interest for facet-defining cuts, which are those essential to characterize a full-dimensional convex hull of feasible solutions. There is also a secondary interest in the broader family of cuts defining supporting hyperplanes, which cannot be strengthened by merely increasing the right-hand si
Data Loading...
