Mardi 19 Mars

Retour à la vue des calendrier
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.