Column Generation Algorithm: A revision from its application to the Student Assignation Problem
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.
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.
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.
F. Vanderbeck. “Implementing Mixed Integer Column Generation”. Column Generation. Ed. Springer. Boston. 2005. pp. 331-358.
J. Desrosiers, P. Hansen, O. Merle, D. Villenueve. “Stabilized column generation”. Discrete Mathematics. Vol. 194. 1999. pp. 229-237.
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.
M. Savelsbergh. “A branch-and-price algorithm for the generalized assignment problem”. Operations Research. Vol. 45. 1997. pp. 831-842.
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.
M. Savelsbergh. Branch-and-price: Integer programming with column generation. No publicado. 2002.
Copyright (c) 2018 Revista Facultad de Ingeniería
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Authors can archive the pre-print version (i.e., the version prior to peer review) and post-print version (that is, the final version after peer review and layout process) on their personal website, institutional repository and / or thematic repository
- Upon acceptance of an article, it will be published online through the page https://revistas.udea.edu.co/index.php/ingenieria/issue/archive in PDF version with its correspondent DOI identifier
The Revista Facultad de Ingeniería -redin- encourages the Political Constitution of Colombia, chapter IV
Chapter IV Sanctions 51
The following shall be liable to imprisonment for two to five years and a fine of five to 20 times the legal minimum monthly wage: (1) any person who publishes an unpublished literary or artistic work, or part thereof, by any means, without the express prior authorization of the owner of rights; (2) any person who enters in the National Register of Copyright a literary, scientific or artistic work in the name of a person other than the true author, or with its title altered or deleted, or with its text altered, deformed, amended or distorted, or with a false mention of the name of the publisher or phonogram, film, videogram or software producer; (3) any person who in any way or by any means reproduces, disposes of, condenses, mutilates or otherwise transforms a literary, scientific or artistic work without the express prior authorization of the owners thereof; (4) any person who reproduces phonograms, videograms, software or cinematographic works without the express prior authorization of the owner, or transports, stores, stocks, distributes, imports, sells, offers for sale, acquires for sale or distribution or in any way deals in such reproductions. Paragraph. If either the material embodiment or title page of or the introduction to the literary work, phonogram, videogram, software or cinematographic work uses the name, business style, logotype or distinctive mark of the lawful owner of rights, the foregoing sanctions shall be increased by up to half.