Degeneracy and stabilization in column generation

• Grant number: 10/05922-5
• Support Opportunities: Scholarships abroad - Research
• Start date: August 01, 2010
• End date: July 31, 2011
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Marcos Antonio Pereira
• Grantee: Marcos Antonio Pereira
• Host Investigator: Jacques Desrosiers
• Host Institution: Faculdade de Engenharia (FEG). Universidade Estadual Paulista (UNESP). Campus de Guaratinguetá. Guaratinguetá , SP, Brazil
• Institution abroad: École des Hautes Études Commerciales (HEC Montréal), Canada

Abstract

Column generation methods have regained interest for solving large-scale combinatorial problems, mainly due to the development of faster and reliable commercial optimization software, which allow inherently complex problems to be solved in reasonable computing times. The column generation technique can be applied to large linear problems when not all variables are explicitly known or when the problem is to be solved by the Dantzig-Wolfe decomposition. It is well known that the direct application of column generation methods produces many columns that are not relevant to the final solution, slowing the solution process convergence. In such cases, it has been observed that the dual solutions oscillate around the optimal dual solution, justifying the application of stabilization methods to inhibit such behavior and, thus, accelerating the problem resolution. This project intends to employ stabilization/acceleration techniques to solve the maximum covering location problem, whose set partitioning formulation presents bad convergence performance when solved by column generation approaches. (AU)