|
|
 |
|
Jeudi 10 Juillet
| Heure: |
10:30 - 11:30 |
| Lieu: |
Salle B107 |
| Résumé: |
Parametric polyhedra in mixed-integer programming |
| Description: |
Diego Morán Ramírez 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. |
|
|
