Student Seminar

Our student seminar is conceived as a discussion forum for students interested in the ACGO themes. The talks are held every second Wednesday of each month and the talks contain a broad introduction to the topic to be covered.

Student Seminars 2017

2017-06-14:

Autor:  Ulrike Schmidt-Kraepelin, Technical University of Munich.

Dónde:  República 779 B, 3er Piso, DII, U Chile.

Cuándo: Miércoles 13 de Septiembre, 13:30.

Título:  Evasión del pago en el transporte público

Abstract: Las redes de transporte público forman parte importante de la vida cotidiana urbana y son esenciales para una parte importante de la sociedad. Sin embargo, los operadores de estas redes enfrentan enormes pérdidas causadas por personas que no pagan su pasaje. La colocación de inspectores en la red de tránsito es un enfoque frecuentemente usado para contrarrestar la evasión. Sin embargo, una vez que los evasores aprenden sobre la distribución de los inspectores, pronto ajustan sus maneras de evitar los controles. Este proceso fue modelado como un juego de Stackelberg por Correa et al. en su publicación Fare Evasion in Transit Networks (2017). El operador de la red es modelado como el líder, mientras que los evasores hacen el papel de seguidores.

El trabajo teórico mencionado anteriormente inspiró el desarrollo de un proyecto que tiene como objetivo reducir la tasa de evasión en la red de transporte público de Santiago. La charla pretende ilustrar algunos antecedentes teóricos, así como mencionar obstáculos y resultados recientes en la ejecución del proyecto.

2017-06-14:

Autor:  Natalie Epstein, DII, U Chile.

Dónde:  República 779 B, 3er Piso, DII, U Chile.

Cuándo: Miércoles 14 de Junio, 13:30.

Título:  Asignación Escolar en Chile

Abstract:  Uno de los pilares fundamentales de la nueva Ley de Inclusión Escolar es el fin de la selección en establecimientos educacionales que reciben aportes estatales. En este contexto, diseñamos un algoritmo que permite realizar, en base a desempates aleatorios de los postulantes, una asignación que cumple con los requerimientos de la ley, permitiendo a las familias elegir los colegios y programas educativos de su preferencia.

El desarrollo del algoritmo está sujeto a varios factores, entre ellos, mantener ciertos criterios de prioridad de los alumnos, tales como tener un hermano en un colegio o ser un alumno vulnerable. Además, para que las familias puedan postular a los colegios que realmente quieren, el algoritmo debe ser a prueba de estrategias de manera que una familia no pueda falsificar sus preferencias y quedar en un colegio que prefiera más.
En este sentido, abordaremos el desarrollo de los elementos distintivos del algoritmo diseñado para el proceso de admisión escolar 2017 en la Región de Magallanes, demostraremos bajo qué condiciones las propiedades deseables de la asignación se mantienen y mostraremos los resultados más significativos del proceso.

2017-04-12:

Autor:  Ignacio Morales, PUC.

Dónde:  República 779 B, DII, U Chile.

Cuándo: Miércoles 12 de Abril, 13:35.

Título:  Un algoritmo primal-dual para el problema de Knapsack Cover con costo variable

Abstract:  Este trabajo se motiva en el problema de un planificador central que tiene que calendarizar la producción de energía dado un conjunto de recursos (plantas generadoras) para satisfacer una demanda conocida en un horizonte de tiempo fijo minimizando el costo total de producción. Este problema es un caso particular de Unit Commitment Problem (UCP) que nace naturalmente en el área eléctrica y en el cuál también abordan los costos de la distribución.

Además, al igual que UCP, en investigación operativa es muy común encontrarse con problemas de producción en donde se utilizan restricciones de tipo cubrimiento (como cubrir demanda) y que los costos tienen una naturaleza de costos fijos y variables. En este trabajo tomamos un problema clásico de cubrimiento llamado Minimum Knapsack ( o Knapsack Cover) Problem que es un caso particular de UCP y que tiene un algoritmo primal dual que es 2-aproximado y lo generalizamos manteniendo la misma cota de aproximación. Nuestra generalización se basa en la idea de tener costos fijos y variables, para lo cual tomamos una función de costos lineal a tramos con la cual se puede modelar de manera exacta el problema de los costos fijos y variables y se pueden aproximar otros problemas más complejos.

2017-03-15:

Autor:  Felipe Garrido, DIM, U Chile.

Dónde:  República 779 B, DII, U Chile.

Cuándo: Miércoles 15 de Marzo, 13:30.

Título:  Equilibrio dinámico en redes de transporte con múltiples orígenes y destinos.

Abstract:   Este trabajo describe el modelo teórico de una red de flujo dinámico con múltiples orígenes y destinos, al poseer arcos con latencia y capacidad. Caracteriza los equilibrios dinámicos de la red, consistentes en la forma óptima de distribuir cada partícula infinitesimal de flujo por medio de los distintos caminos que unen orígenes con destinos, de modo que siempre se esté recorriendo un camino mínimo considerando tanto los costos invertidos en pasar por cada arco, como el tiempo gastado en esperar en cada una de las colas a las que se haya formado.

Para el caso de poseer un solo nodo fuente, además del modelo teórico entregado para la red y las distintas formas de caracterizar un equilibrio dinámico, se estudia una forma de obtener extensiones a lo largo del tiempo de este mediante la introducción de flujos finos normalizados. Se entregan dos algoritmos, el primero que extiende el flujo de modo que siga siendo óptima su distribución, y otro que explica la forma de obtener estos flujos finos normalizados.

Por otro lado, para el caso de tener múltiples nodos fuente, tras presentar el modelo teórico y las complicaciones que este presenta, eliminando la posibilidad de utilizar una estrategia de flujos finos normalizados, se dan ejemplos que evidencian la pérdida de linealidad en sistemas de ecuaciones necesarios para el desarrollo de un algoritmo.

Esto nace como una continuación del trabajo hecho por R. Cominetti, J. Correa y O. Larré en 2015 “Dynamic equilibria in fluid queueing networks”, quienes lograron modelar, caracterizar los equilibrios dinámicos y posteriormente entregar un algoritmo de extensión en el caso de una red de flujo dinámico con una única fuente y un único origen.

Previous Years