Session: Column Generation Techniques (organized by José

Session: Column Generation Techniques (organized by José

Session: Column Generation Techniques
(organized by José Valério de Carvalho)
Solving CSP by Stabilized Column Generation Algorithm
H. Ben Amor
[email protected]
Département de Mathématiques et Génie Industriel,
École Polytechnique, C.P.6079, succ.
Centre-ville, Montréal, H3C 3A7 Canada
Abstract
Available dual optimal information is known to be useful for column generation stability and
hence efficiency. Dual-optimal inequalities have been used for the Cutting Stock problem and
showed very beneficial. We propose new simple dual-optimal inequalities and test their effect
on widely used CSP test instances. Then, we test a strategy based on approximate dual-optimal
information. That is an infeasible near-optimal dual point we used as the starting point of a
proximal stabilized column generation algorithm for CSP.
Keywords: Cutting Stock; Bin Packing; Column generation; Stabilization