Algoritmo de Generación de Columnas: Una revisión desde su aplicación al problema de asignación de cupos escolares
DOI:
https://doi.org/10.17533/udea.redin.17937Palabras clave:
Algoritmo de generación de columnas, problema de asignación, algoritmo Branch and Price.Resumen
El algoritmo de generación de columnas (GC) se cita usualmente como alternativa para la solución de problemas de optimización de gran escala; este artículo aborda la presentación de dicho algoritmo en el contexto de la asignación de cupos escolares en el sistema de educación pública del distrito de Bogotá. Se discuten algunas de las falencias evidenciadas en la puesta en práctica del algoritmo, presentando estrategias para enfrentarlas. Se ilustra además, la forma como la generación de columnas se acopla dentro del algoritmo Branch and Price para dar solución a problemas de mayor complejidad.
Descargas
Citas
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
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Los artículos disponibles en la Revista Facultad de Ingeniería, Universidad de Antioquia están bajo la licencia Creative Commons Attribution BY-NC-SA 4.0.
Eres libre de:
Compartir — copiar y redistribuir el material en cualquier medio o formato
Adaptar : remezclar, transformar y construir sobre el material.
Bajo los siguientes términos:
Reconocimiento : debe otorgar el crédito correspondiente , proporcionar un enlace a la licencia e indicar si se realizaron cambios . Puede hacerlo de cualquier manera razonable, pero no de ninguna manera que sugiera que el licenciante lo respalda a usted o su uso.
No comercial : no puede utilizar el material con fines comerciales .
Compartir igual : si remezcla, transforma o construye a partir del material, debe distribuir sus contribuciones bajo la misma licencia que el original.
El material publicado por la revista puede ser distribuido, copiado y exhibido por terceros si se dan los respectivos créditos a la revista, sin ningún costo. No se puede obtener ningún beneficio comercial y las obras derivadas tienen que estar bajo los mismos términos de licencia que el trabajo original.
Twitter