Invited Session Fri.2.H 2033

Friday, 13:15 - 14:45 h, Room: H 2033

Cluster 11: Integer & mixed-integer programming [...]

Cutting plane theory


Chair: Jeff Linderoth



Friday, 13:15 - 13:40 h, Room: H 2033, Talk 1

Alberto Del Pia
On the rank of disjunctive cuts


Let L be a family of lattice-free polyhedra containing the splits.
Given a polyhedron P, we characterize when a valid inequality for the mixed integer hull of P can be obtained with a finite number of disjunctive cuts corresponding to the polyhedra in L.
We also characterize the lattice-free polyhedra M such that all the disjunctive cuts corresponding to M can be obtained with a finite number of disjunctive cuts corresponding to the polyhedra in L, for every polyhedron P.
Our results imply interesting consequences, related to split rank and to integral lattice-free polyhedra, that extend recent research findings.



Friday, 13:45 - 14:10 h, Room: H 2033, Talk 2

Esra Buyuktahtakin
Partial objective function inequalities for the multi-item capacitated lot-sizing problem

Coauthors: Joseph Hartman, Cole Smith


We study a mixed integer programming model of the multi-item capacitated lot-sizing problem (MCLSP), which incorporates shared capacity on the production of items for each period throughout a planning horizon. We derive valid bounds on the partial objective function of the MCLSP formulation by solving the first t-periods of the problem over a subset of all items, using dynamic programming and integer programming techniques. We then develop algorithms for strengthening these valid inequalities
by lifting and back-lifting binary and continuous variables. These inequalities can be utilized in a cutting-plane strategy, in which
we perturb the partial objective function coefficients to identify violated inequalities to the MCLSP polytope. We test the effectiveness of the proposed valid inequalities on randomly generated instances.



Friday, 14:15 - 14:40 h, Room: H 2033, Talk 3

Robert Hildebrand
The triangle closure is a polyhedron

Coauthors: Amitabh Basu, Matthias Koeppe


Recently, cutting planes derived from maximal lattice-free convex sets have been studied intensively by the integer programming community. An important question in this research area has been to decide whether the closures associated with certain families of lattice-free sets are polyhedra. For a long time, the only result known was the celebrated theorem of Cook, Kannan and Schrijver who showed that the split closure is a polyhedron. Although some fairly general results were obtained by Andersen, Louveaux and Weismantel "An analysis of mixed integer linear sets based on lattice point free convex sets'' (2010), some basic questions have remained unresolved. For example, maximal lattice-free triangles are the natural family to study beyond the family of splits and it has been a standing open problem to decide whether the triangle closure is a polyhedron. We resolve this question by showing that the triangle closure is indeed a polyhedron, and its number of facets can be bounded by a polynomial in the size of the input data.


  There are three major facts that should be watched out for in all payday loans in the United States. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.