Column Generation Algorithm: A revision from its application to the Student Assignation Problem

  • Pablo Andrés Maya Universidad de Antioquia
Keywords: Column generation algorithm, assignment problem, branch and price algorithm

Abstract

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.

|Abstract
= 49 veces | PDF (ESPAÑOL (ESPAÑA))
= 9 veces|

Downloads

Download data is not yet available.

Author Biography

Pablo Andrés Maya, Universidad de Antioquia

Departamento de Ingeniería Industrial

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.

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.

Published
2013-12-11
How to Cite
Maya P. A. (2013). Column Generation Algorithm: A revision from its application to the Student Assignation Problem. Revista Facultad De Ingeniería Universidad De Antioquia, (46), 145-157. Retrieved from https://revistas.udea.edu.co/index.php/ingenieria/article/view/17937