## 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

**Abstract:**

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**

**Abstract:**

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**

**Abstract:**

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.