Study of models of support for the process of assignment of school spaces in the public education system of the capital district
No Thumbnail Available
Date
Authors
Advisors
Evaluators
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad Industrial de Santander
Abstract
Description
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.
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.
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.
Keywords
Assignment Problem, column generation, branch and price, auction algorithm, Problema de Asignación, generación de columnas, blgoritmo de subastas, branch and price