AOC - 2013

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Reverse Chvatal-Gomory rank.
Description:	Roland Grappe We introduce the reverse Chvatal-Gomory rank r(P) of an integral polyhedron P, defined as the supremum of the Chvatal-Gomory ranks of all rational polyhedra whose integer hull is P. A well-known example in dimension two shows that there exist integral polytopes P with r(P) infinite. We provide a geometric characterization of polyhedra with this property in general dimension, and investigate upper bounds on r*(P) when this value is finite. This is a joint work with Michele Conforti, Alberto Del Pia, Marco Di Summa and Yuri Faenza.&nbsp;

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Accelerated Column Generation for Cutting Stock and Bin Packing
Description:	Accelerated Column Generation for Cutting Stock and Bin Packing One successful method for solving the cutting stock (CS) and bin packing problem (BP) is branch-and-price.&nbsp; The column generation master program is a set covering problem where columns correspond to feasibly filled bins that cover a subset of the items.&nbsp; It is known that standard column generation suffers from slow convergence (tailing off).&nbsp; For CS, valid inequalities on the dual prices of the covering constraints, so-called dual optimal inequalities, were identified to be helpful to mitigate the tailing off effect.&nbsp; The presentation addresses three issues:&nbsp; First, the standard approach is the a priori construction of dual optimal inequalities before solving the master program.&nbsp; We show that the most violated inequalities can be easily identified in the column generation process and so be added dynamically.&nbsp; For standard benchmark problems, computation times were approximately halved.&nbsp; Second, for BP not all CS inequalities are dual optimal, i.e., fulfilled by at least one optimal solution of the LP-relaxation of the master program.&nbsp; We present a way to handle these cases and to reconstruct primal feasible solutions needed in the branch-and-bound process.&nbsp; Third, we generalize our results to the BP with conflicts.&nbsp;