Column Generation Algorithm: A revision from its application to the Student Assignation Problem
DOI:
https://doi.org/10.17533/udea.redin.17937Keywords:
Column generation algorithm, assignment problem, branch and price algorithmAbstract
The Column Generation Algorithm (CGA) is commonly cited in the bibliography as alternative to solve large scale optimization problems. This article deals with the description of the GC algorithm in the context of the student assignation to the public schools. Some of the wea�nesses and shortcomings encountered in the implementation and application to a real problem are discussed and some strategies to sort it out are presented. This work pointed out how the CGA could be used within a general Branch and Price procedure to solve problems with additional constrains.
Downloads
References
P. Maya. Estudio de Modelos de Apoyo al Proceso de Asignación de Cupos Escolares en el Sistema de Educación Pública del Distrito de Bogotá. Tesis de Maestria. Universidad de los Andes. Facultad de Ingeniería. 2005. pp. 104
T. Magnanti, R. Orlinj Ahuja, J. B. Orlin. Network Flows. Theory, Algorithms and Applications. Ed. Prentice Hall. New York. 1993. pp 461-463.
J. Jarvis, H. Sherali, M. Bazaara. Programación Lineal y Flujo en Redes. Ed. Limusa. México. 1999. 2ªed. pp. 553-594
F. Vandeerbeck. Descoposition and Column Generation for Integer Programs. Tesis de Doctorado. Universidad Católica de Louvain. 1994, pp. 9-31.
M. Lubbecke. Engine Scheduling by Column Generation. Tesis de Doctorado, Universidad de Braunschweig. 2001, pp. 37-87.
W. Johnson, G. Nemhauser, M. Savelsbergh. “Progress in linear programming-based algorithms for integer programming: An exposition. Journal on Computing. Vol. 12. 2000. pp. 2-22. DOI: https://doi.org/10.1287/ijoc.12.1.2.11900
M. Savelsbergh. “A branch-and-price algorithm for the generalized assignment problem”. Operations Research. Vol. 45. 1997. pp. 831-841.
J. Desrosiers, M. Solomon , G. Desaulniers. (Eds). Column Generation. Ed. Springer. Boston. 2005. pp. 1-32.
L. Wolsey. Integer Programming. Ed. Jhon Wiley. 1998. pp 185-200.
M. Lubbecke, J. Desrosiers. “Selected topics in column generation”. Operations Research. 2005. Vol. 53. 2005. pp. 1007-1023. DOI: https://doi.org/10.1287/opre.1050.0234
F. Vanderbeck. “Implementing Mixed Integer Column Generation”. Column Generation. Ed. Springer. Boston. 2005. pp. 331-358. DOI: https://doi.org/10.1007/0-387-25486-2_12
J. Desrosiers, P. Hansen, O. Merle, D. Villenueve. “Stabilized column generation”. Discrete Mathematics. Vol. 194. 1999. pp. 229-237. DOI: https://doi.org/10.1016/S0012-365X(98)00213-1
A. Pigatti, M. Aragão, E. Uchoa. “Stabilized Branch-and-cut-and-price for the Generalized Assignment Problem.” Electronic Notes in Discrete Mathematics. Vol. 19. 2005. pp. 389-395. DOI: https://doi.org/10.1016/j.endm.2005.05.052
M. Savelsbergh. “A branch-and-price algorithm for the generalized assignment problem”. Operations Research. Vol. 45. 1997. pp. 831-842. DOI: https://doi.org/10.1287/opre.45.6.831
C. Barnhat, E. L. Johnson, G. L. Nemhauser, M. Savelsbergh, P. Vance. Branch-and-price column generation for solving huge integer programs. Operations Research. Vol. 46. 1998. pp. 316-329. DOI: https://doi.org/10.1287/opre.46.3.316
M. Savelsbergh. Branch-and-price: Integer programming with column generation. No publicado. 2002. DOI: https://doi.org/10.1007/0-306-48332-7_47
Downloads
Published
How to Cite
Issue
Section
License
Revista Facultad de Ingeniería, Universidad de Antioquia is licensed under the Creative Commons Attribution BY-NC-SA 4.0 license. https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en
You are free to:
Share — copy and redistribute the material in any medium or format
Adapt — remix, transform, and build upon the material
Under the following terms:
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
NonCommercial — You may not use the material for commercial purposes.
ShareAlike — If you remix, transform, or build upon the material, you must distribute your contributions under the same license as the original.
The material published in the journal can be distributed, copied and exhibited by third parties if the respective credits are given to the journal. No commercial benefit can be obtained and derivative works must be under the same license terms as the original work.
Twitter