Advanced search
Start date

Degeneracy and stabilization in column generation

Grant number: 10/05922-5
Support Opportunities:Scholarships abroad - Research
Effective date (Start): August 01, 2010
Effective date (End): 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
Research place: École des Hautes Études Commerciales (HEC Montréal), Canada  


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)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

Please report errors in scientific publications list using this form.