6533b82afe1ef96bd128b942
RESEARCH PRODUCT
Dual Inequalities for Stabilized Column Generation Revisited
Timo GschwindStefan Irnichsubject
Vector packingMathematical optimization021103 operations researchInequalityLinear programmingBin packing problemmedia_common.quotation_subjectColumn generation dual inequalities stabilization0211 other engineering and technologiesGeneral Engineering0102 computer and information sciences02 engineering and technology01 natural sciencesCombinatorics010201 computation theory & mathematicsSlow convergenceColumn generationInteger programmingMathematicsmedia_commondescription
Column generation (CG) models have several advantages over compact formulations: they provide better linear program bounds, may eliminate symmetry, and can hide nonlinearities in their subproblems. However, users also encounter drawbacks in the form of slow convergence, also known as the tailing-off effect, and the oscillation of the dual variables. Among different alternatives for stabilizing the CG process, Ben Amor et al. [Ben Amor H, Desrosiers J, Valério de Carvalho JM (2006) Dual-optimal inequalities for stabilized column generation. Oper. Res. 54(3):454–463] suggest the use of dual-optimal inequalities (DOIs) in the context of cutting stock and bin packing problems. We generalize their results, provide new classes of (deep) DOIs, and show the applicability to other problems (vector packing, vertex coloring, bin packing with conflicts). We also suggest the dynamic addition of violated dual inequalities in a cutting-plane fashion and the use of dual inequalities that are not necessarily (deep) DOIs. In the latter case, a recovery procedure is needed to restore primal feasibility. Computational results proving the usefulness of the methods are presented.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2014-07-23 |