Revista UIS Ingenierías

Vol. 6 No. 1 (2007): Revista UIS Ingenierías
Articles

Study of models of support for the process of assignment of school spaces in the public education system of the capital district

PDF (Español (España))
  • Pablo Andrés Maya Duque
Pablo Andrés Maya Duque
PABLO ANDRÉSMAYA DUQUE Universidad de Antioquía
Bio

Published 2007-05-28

Keywords

  • Assignment Problem,
  • column generation,
  • branch and price,
  • auction algorithm

How to Cite

Maya Duque, P. A. (2007). Study of models of support for the process of assignment of school spaces in the public education system of the capital district. Revista UIS Ingenierías, 6(1), 35–45. Retrieved from https://revistas.uis.edu.co/index.php/revistauisingenierias/article/view/1841
Copyright Notice

Abstract

The assignation of new students to schools could be considered a problem into the process that manages the studentplaces at the Bogotá educational system. 1t is possible to model that problem like an assignation with similar objects,the solutions of this problem increase in complexity when consider the large number of students and other additionalrestrictions. This Document explores two strategies to approach the student assignation problem, which differ trom thecurrent "greedy" algorithm that is used into the assignation process. Initially a Branch and Price algorithm is discussedwhich presents convergence problems, and then the Auction Algorithm is studied.

PDF (Español (España))

Downloads

Download data is not yet available.

References

MAGNANTI T y ORLINJ AHUJA R. Network Flows. Theory, Algoritlmls and Applications. Prentice Hall, 1993.

NEMHAUSER George SAVELSBERGH Martín y VANCE Pamela BARNHART Cynthia, JOHNSON Ellis. Branch-and-price column generation for solving huge integer programs. No Publicado, Enero1996.

JARVIS J y SHERALl H. BAZAARA M. Programación Lineal y Flujo en Redes. Limusa, 2ª edition, 1999

BERTSEKAS D. The auction algorithm: A distributed relaxation method for the assignment. Annals of Operations Research, 14:105-123, 1988

BERTSEKAS D. Auction algorithms for network flow problems: A tutorial introduction. Mayo 1992.

BERTSEKAS D. and CASTANON D. The auction algorithrn for transportation problems. Annals of Operations Research, 20:67-96, Febrero 1989.

DESROSlERS J. y SOLOMON M. DESAULNIERS G. Co1umn Generation, Springer, 1 edition, 2005.

LUBBECKE Marco e. y DESROSIERS Jaques. Selected topics in column generation. Para aparecer en Operations Research, Diciembre 2002.

VANDEERBECK Francois. Descoposition and Column Generation for Integer Programs. PhD thesis, Universidad Catolica de Louvain, Septiembre 1994.

W JOHNSON eellis L., NEMHAUSER George L. y SAVELSBERGH Martin. Progress in linear programming-based algorithms for integer programming: An exposition. lNFORMS Journal on Computing, 12(1), 2000.

WOLSEY Laurence. Integer Programming. Jhon Wiley and sons, 1998.

H'ENON M. Algorithmic aspects of mak. Noviembre 2004.

LUBBECKE Marco. Engine Scheduling by Column Generation. PhD thesis, Universidad de Braunschweig, julio 2001.

SAVELSBERGH Martin. Abranch-and-rice algorithm for the generalize dassignment problem. Operations Research, 45(6):831-841, Diciembre 1997.

SAVELSBERGH Martin. A branch-and-price algorithm for the generalized assignment problem. Operations Research, 45(6):831-842, Noviembre 1997.

SAVELSBERGH Martin. Branch-and-price: Integer progratrullillg with column generation. No Publicado, Febrero 2002.

DESROSIERS Jacques y HANSEN Pierre MERLE Olivier, VILLENUEVE Daniel. Stabilized co1umn generation. Discrete Mathematics, (194):229-237, 1999

PIGGATI Alexander y POGGl Marcus. Satbilized branch-and cut-and price for the generalized assignment prob1em. No Publicado, Octubre 2004.