|
|
 |
|
Lundi 7 Juillet
| Heure: |
10:30 - 11:30 |
| Lieu: |
Salle B107 |
| Résumé: |
Deep Dual-Optimal Inequalities for Generalized Capacitated Fixed-Charge Network Design Problems |
| Description: |
Alexis Schneider Capacitated fixed-charge network design problems and generalizations, such as service network design problems, have a wide range of applications but are known to be very difficult to solve. Many exact and heuristic algorithms to solve these problems rely on column-and-row generation (CRG), which frequently suffer from primal degeneracy. We present a set of dual inequalities, equivalent to a simple primal relaxation, that speed up CRG algorithms for generalized capacitated fixed charge network design problems. We investigate the impact of the dual inequalities theoretically as well as experimentally. For practical applications, the presented technique is simple to implement, has no additional computational cost and can accelerate CRG by orders of magnitude, depending on the problem size and structure. |
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. |
|
|
