Vol. 6 Núm. 1 (2007): Revista UIS Ingenierías
Artículos

Estudio de modelos de apoyo al proceso de asignación de cupos escolares en el sistema de educación pública del distrito capital

Pablo Andrés Maya Duque
PABLO ANDRÉSMAYA DUQUE Universidad de Antioquía
Biografía

Publicado 2007-05-28

Palabras clave

  • Problema de Asignación,
  • generación de columnas,
  • blgoritmo de subastas,
  • branch and price

Cómo citar

Maya Duque, P. A. (2007). Estudio de modelos de apoyo al proceso de asignación de cupos escolares en el sistema de educación pública del distrito capital. Revista UIS Ingenierías, 6(1), 35–45. Recuperado a partir de https://revistas.uis.edu.co/index.php/revistauisingenierias/article/view/1841

Resumen

En el proceso de asignación de cupos escolares, en los colegios públicos del distrito de Bogota, es posible identificarcomo una situación problemática la asignación de cupos a los estudiantes que ingresan nuevos al sistema de educaciónpública. Dicha asignación puede modelarse de manera similar a un problema de asignación con objetos repetidos, lasolución de este problema aumenta su complejidad al considerar el gran número de estudiantes que deben ser asignadosy la presencia de restricciones adicionales. Se discuten en este documento estrategias de solución al problema deoptimización inherente a la asignación de cupos, que se distancian del enfoque greedy que rige el procedimiento desolución actual. Inicialmente se discute el algoritmo de generación de columnas, específicamente el algoritmo Branchand-Price. Dadas las dificultades en la convergencia de este algoritmo se estudia el algoritmo de Subastas. Para cadauna de las estrategias discutidas se describen los aspectos mas importantes, se presentan los aspectos más relevantesde su implementación y por ultimo se plantea la forma como podrían incorporarse dentro del proceso de asignaciónque actualmente se ejecuta.

Descargas

Los datos de descargas todavía no están disponibles.

Referencias

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.