Mardi 19 Mars

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.  The column generation master program is a set covering problem where columns correspond to feasibly filled bins that cover a subset of the items.  It is known that standard column generation suffers from slow convergence (tailing off).  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.  The presentation addresses three issues:  First, the standard approach is the a priori construction of dual optimal inequalities before solving the master program.  We show that the most violated inequalities can be easily identified in the column generation process and so be added dynamically.  For standard benchmark problems, computation times were approximately halved.  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.  We present a way to handle these cases and to reconstruct primal feasible solutions needed in the branch-and-bound process.  Third, we generalize our results to the BP with conflicts.