AGCO Seminar: Parametric Polyhedra in Mixed-Integer Programming

Abstract: 

We present some old and new results on arbitrary families of parametric polyhedra. First, if the constraint matrix is fixed, in the literature there are structural results for the integer hull and the finiteness of cutting plane closures for varying r.h.s. For instance, recently, Becu et al. proved in “Approximating the Gomory Mixed-Integer Cut Closure Using Historical Data” that the GMI closure of this family is finitely generated, in the sense that there exists a finite list of aggregation weights defining the GMI cuts that give the GMI closure for any polyhedra in the family. We extend this result for other cutting plane closures. Second, if the family of parametric polyhedra is arbitrary but all polyhedra in the family have the same integer hull, they define the same MIP, and we can leverage this information to understand and solve MIPs better. These families have been used to understand theoretical properties of the rank of cutting planes and to obtain better formulations. We present an application of these same-integer-hull families to formulations for the Asymmetric Traveling Salesman Problem. This is joint work with Jason Dai, Rensselaer Polytechnic Institute; Gustavo Angulo, Pontificia Universidad Católica de Chile; Silvia Di Gregorio, Sorbonne Paris Nord University.

Speakers: Diego Morán, Rensselaer Polytechnic Institute
When: May 6, 3:00 pm – 4:00 pm.
Where: Sala de Seminario von Neuman, 7th floor, CMM, Av. Beauchef 851, Torre Norte.