Dual Inequalities for Stabilized Column Generation (StabCG)

• Applicant: Professor Dr. Stefan Irnich
• Subject Area: Accounting and Finance
• Term: from 2016 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 280866737

Many planning and optimization approaches are based on mixed-integer programming models and methods. Substantial progress has been made over the last 60 years, on the one hand driven by increased power of today's computers, on the other hand by various methodological achievements in mixed-integer programming. Column generation (CG) methods are among the most successful and important algorithms to deal with huge linear programs comprising many variables. Embedding CG in a branch-and-bound algorithm allows the solution of mixed-integer programs. Such methods are commonly referred to as a branch-and-price algorithms. Many successful branch-and-price algorithms can be found, for example, in the areas of vehicle routing, manpower planning, packing and cutting problems, sequencing and graph optimization. The main disadvantages of CG techniques can be attributed to instability of the values ¿¿of the dual variables. Previous techniques for mitigating the negative effects can be subsumed as "numerical methods of stabilization". Valério de Carvalho (2005: INFORMS Journal on Computing, 17 (2), 175-182) and Ben Amor et al. (2006: Operations Research, 54 (3), 454-463) have followed a different path for cutting stock and bin packing problems. They utilize properties of dual optimal solutions for stabilizing the CG process. Any dual optimal inequality (DOI) for the polyhedron of the optimal dual solutions can be added as an additional variable in the corresponding primal CG formulation. The dissertation (Gschwind 2014: Gutenberg School of Management and Economics, University of Mainz) developed a series of innovative concepts, which extend the existing literature on stabilized CG method using DOIs in several aspects.The overall objective of the research project is to improve exact methods for solving various problems. Compared to prior research, the project aims at solving larger and more difficult problem instances to proven optimality by developing new techniques for stabilizing CG method with DOIs. Previous findings from the literature and our own preliminary work supports the hypothesis that a successful stabilization can significantly improve CG methods in many applications.

• DFG Programme: Research Grants