Seminario 2008
Guillermo Durán
"Aplicaciones de la Investigación Operativa al Estado y a la Industria
desde la Universidad: la experiencia en Chile y Argentina"
Se presentan aplicaciones de la Investigación Operativa realizadas o en
desarrollo desde las Universidades de Chile y de Buenos Aires. Serán reseñados
en esta charla problemas de planificación de la producción, logística
y transporte en la industria salmonera chilena; la programación eficiente
de eventos deportivos (vóley en Argentina, fútbol en Chile); convenios
con el Estado para mejorar la gestión pública (licitaciones, recolección
de residuos, transporte público), entre otras aplicaciones.
<<
Flavia Bonomo
"Variantes del problema de coloreo de grafos"
El problema de coloreo de grafos es usado habitualmente para modelar diversos
problemas reales. Vamos a hablar sobre algunas de sus variantes, definidas a fin
de considerar situaciones particulares que surgen en dichos problemas. Hablamos
tanto de aspectos teóricos como algorítmicos de las diferentes variantes
de coloreo, y mencionaremos sus principales aplicaciones.
<<
Javier Marenco
"Diseño de fixtures para ligas deportivas con sistema grand-prix"
La planificación del fixture de una liga deportiva es un problema combinatorio
que puede resultar muy difícil. En esta charla estudiaremos un formato
particular que es útil para ligas de deportes de gimnasio con un número
pequeño e impar de equipos. Analizaremos un modelo de programación
lineal entera para este problema, y veremos cómo se pueden obtener fixtures
para este tipo de ligas sobre la base de un estudio poliedral previo. Finalmente,
presentaremos algunos problemas abiertos sobre este tipo de fixtures.
<<
Federico Larumbe
"Optimización de la recolección de basura por medio de contenedores
en la zona sur de la Ciudad de Buenos Aires"
Se presentará el avance de un proyecto realizado con el Ente de Higiene
Urbana de la Ciudad de Buenos Aires. Este organismo se ocupa de recolectar los
contenedores de residuos que se encuentran en las cuadras de los CGP 8 y 9, la
zona sur de la ciudad. En la charla se mostrará la aplicación de
un algoritmo exacto para el problema del Viajante de Comercio con el objetivo
de optimizar los recorridos de los camiones de recolección.
<<
Alejandro Baranek
"Un jugador automático para el Tute Cabrero"
El Tute Cabrero (ver, por ejemplo, http://www.tute.com.ar/reglamento.html)
es un juego tradicional de cartas españolas que se desarrolla por bazas.
Se puede jugar de 3, 4 o 5 jugadores y posee la particularidad de que existen
2 estrategias principales para ganar: sumar la mayor cantidad de puntos posibles
o sumar la menor cantidad. En general, el que no logra ninguno de estos objetivos
pierde. En esta charla contaremos los avances en el desarrollo de un jugador automático
de Tute Cabrero.
<<
Andrés Cardemil
"Una aplicación del Traveling Tournament Problem: la Liga Argentina
de Voley"
La planificación de fixtures deportivos es una tarea muy compleja que las
ligas organizadoras de torneos enfrentan frecuentemente. Esto se debe principalmente
a que tienen que satisfacerse diversos tipos de requisitos como los que imponen
los contratos televisivos, los equipos participantes, la disponibilidad de estadios,
etc. Además, es frecuente que se intente minimizar costos o las distancias
que los equipos deben recorrer a lo largo del torneo. La enorme cantidad de soluciones
factibles que pueden generarse convierte a estos problemas en casos muy interesantes
de estudio en el campo de la Optimización Combinatoria. En esta charla
describiremos primero las características y requisitos más comunes
del armado de fixtures. Luego presentaremos el Traveling Tournament Problem (TTP,
http://mat.gsia.cmu.edu/TOURN/),
un problema teórico que abstrae importantes conceptos y es muy usado actualmente
para la prueba y comparación de distintas técnicas de resolución.
Finalmente contaremos un modelo de programación entera y un algoritmo "Tabu
Search" que utilizamos para resolver el fixture de la fase regular de la
Liga Argentina de Voley, el cual tiene muchas similitudes con el TTP.
<<
Jaime Catalán (DII, U. de Chile)
"Un ejemplo real de licitación combinatoria exitosa: la experiencia
en los comedores escolares de Chile"
Desde el año 1997, la licitación para proveer de comida a todas
las escuelas públicas chilenas es administrada con el apoyo de un modelo
matematico diseñado por académicos del Departamento de Ingeniería
Industrial de la Universidad de Chile. En esta charla se hará una reseña
de estos 10 años trabajando con esta herramienta. El trabajo realizado
se engloba en un area muy difundida de la Gestión de Operaciones, conocida
como "Combinatorial Auctions".
<<
Regina Berretta (University of Newcastle, Australia)
"Combinatorial optimization models for finding genetic signatures from
gene expression datasets"
The aim of this talk is to present the possibilities that combinatorial optimization
models and techniques give for the analysis of microarray datasets. Two problems
will be discussed as examples of different models and approaches we have developed.
The first one is the gene ordering problem and the second is the problem of selecting
discriminative groups of genes.
Dr. Regina Berretta is a Senior Lecturer at School of Electrical Engineering and
Computer Science at University of Newcastle, Australia, and member of Centre for
Bioinformatics, Biomarker Discovery and Information-Based Medicine. Her research
interests include combinatorial optimization modelling with applications in bioinformatics
and development of metaheutistics as Tabu Search and Memetic Algorithms.
<<
Pablo Moscato (University of Newcastle, Australia)
"Towards robust classification methods for clinical bioinformatics"
Robustness is increasingly being recognized as a central theme in Systems Biology.
However, in the area of algorithm design and analysis, the robustness of the algorithms
to perturbations of their inputs is seldom study or discussed. A main theme of
our Centre is to develop algorithmic solutions which are aware of the problems
that incorrect measurements can give to the final outcome. When these algorithms
are used for clinical applications, a number of issues arise worth of consideration
and mathematical modelling. We illustrate our talk with current progress in the
application of our methods in neurodegenerative diseases, classification of tumours
and prognosis evaluation of subtypes of cancer.
Associate Professor Pablo Moscato is the Founding Director of Newcastle Bioinformatics
Initiative (2002-2006) and is currently the Co-Director of the Centre for Bioinformatics,
Biomarker Discovery and Information-based Medicine of The University of Newcastle.
He is currently the Deputy Director of the Information-based Medicine Program
of the Hunter Medical Research Institute and a Chief Investigator of the Australian
Research Council Centre of Excellence in Bioinformatics. His research interests
are in combinatorial optimization methods in bioinformatics, exact and hybrid
techniques for optimization, mathematical modelling and heuristics. In Bioinformatics,
he has been primarily involved in mathematical models for mining large-scale datasets,
hierarchical clustering and phylogenetics, and bioinformatics analysis of gene
expression dataset in neurodegenerative diseases and cancer.
<<
Pablo Rey (EII, U. Diego Portales, Chile)
"Un metodología híbrida basada en optimización y simulación
para la determinación de dotación de personal de boleterías
para el Metro de Santiago"
El servicio de Metro en la ciudad de Santiago transporta, en sus 4 líneas,
más de 2,3 millones de pasajeros por día (Marzo 2007). Su red tiene
90 estaciones y 102 mesaninas (lugar físico donde se encuentran las boleterías
y los torniquetes de acceso a los andenes en una estación).
Entre las decisiones operacionales que debe enfrentar la empresa se encuentra
la asignación del servicio de caja para las distintas mesaninas de cada
estación. Para el presente trabajo, se entiende como servicio de caja a
un vendedor de boletos asignado a un puesto fijo dentro de una boletería
o a un vendedor fuera de una boletería ("rompe fila"). Los servicios
de caja son subcontratados y se debe determinar la cantidad, tipo, hora de inicio
y duración de los servicios requeridos. Además se deben respetar
ciertas condiciones de operación y otras que garantizan la calidad de servicio
mínima requerida.
La metodología implementada tiene como objetivo determinar una asignación
que satisfaga las condiciones requeridas al menor costo posible. Esta fue implementada
en un sistema computacional compuesto por dos módulos integrados. El primer
de ellos, el "módulo de asignación", determina programaciones
óptimas de servicios de caja para todas las mesaninas de la red, bajo ciertos
supuestos simplificadores. El "módulo de simulación",
valida y agrega correcciones a las programaciones producidas por el módulo
de asignación. Estos módulos interactúan iterativamente:
Inicialmente se determina una primera programación que luego es validada
por el módulo de simulación. Si se detecta alguna violación
al estándar de calidad de servicio establecido esta información
es utilizada para obtener una nueva programación donde se ha solucionado
este problema. Esto se logra incluyendo nuevas restricciones en la instancia resuelta
por el módulo de asignación. Esta nueva asignación es entonces
procesada por el módulo de simulación. Este proceso iterativo continúa
hasta que una asignación satisfactoria es obtenida o se cumplen otras condiciones
de parada (infactibilidad para satisfacer las condiciones requeridas con los recursos
disponibles).
<<
Andrés Weintraub (DII, U. de Chile)
"Uso de Investigación Operativa en el mundo real: desafíos,
éxitos y problemas abiertos"
En esta charla se verá la multiplicidad de aplicaciones de IO exitosas
que se tienen en el mundo. Mostraremos especialmente la
experiencia desde la Universidad de Chile en problemas de empresas forestales,
mineras, de acuicultura, manejo de containers por una naviera, adjudicación
de comidas de colegios por el Ministerio de Educación en licitaciones combinatoriales,
y otros problemas. Discutiremos las dificultades para desarrollar e implementar
estos sistemas, los motivos de éxito y posibles causas de fracasos. También
discutiremos los desafios académicos, algorítmicos y los problemas
que aún están abiertos.
<<
Martín Safe
"Subclases y variantes de los grafos perfectos"
Los grafos perfectos fueron definidos por Berge en los '60 y han despertado mucho
interés en la literatura especializada. Su caracterización por subgrafos
prohibidos permaneció como conjetura por 40 años y fue probada recientemente.
En los últimos años han aparecido publicaciones sobre diferentes
variantes y subclases de los grafos perfectos. En esta charla haremos un repaso
sobre los trabajos que se han llevado a cabo y se siguen llevando a cabo en éste
tópico dentro
de nuestro grupo.
<<
Luciano Grippo
"Caracterizaciones parciales de grafos arco-circulares y circulares"
Los grafos arco-circulares y circulares son dos familias importantes de grafos
de intersección. En esta charla daremos una introducción al estado
del arte en el estudio de estas dos familias de grafos. Particularmente nos focalizaremos
en estudiar el problema de dar una caracterización de estas clases por
subgrafos prohibidos y mostraremos algunas caracterizaciones parciales obtenidas
en esta dirección.
<<
Diego Delle Donne
"Un modelo de coloreo para minimizar interferencias en redes de telefonía
celular"
La asignación de frecuencias a las antenas de una red de telefonía
celular es un problema combinatorio que puede resultar muy difícil. En
esta charla presentaremos una forma de modelar este problema como un problema
de coloreo de grafos y veremos cómo resolverlo utilizando técnicas
de Programación Lineal Entera. Plantearemos tres modelos de PLE y presentaremos
un estudio poliedral sobre uno de ellos. Mostraremos una implementación
de un algoritmo Branch&Cut para dicho modelo y finalmente expondremos los
resultados obtenidos.
<<
Esteban Feuerstein
"Subastas estocásticas y determinísticas "veraces"
para la búsqueda patrocinada" (Truthful stochastic and deterministic
auctions for sponsored search)
Incentive compatibility is a central concept in auction theory, and a desirable
property of auction mechanisms. In a celebrated result, Aggarwal, Goel and Motwani
presented the first truthful deterministic auction for sponsored search (i.e.,
in a setting where multiple distinct slots are auctioned).
Stochastic auctions present several advantages over deterministic ones, as they
are less prone to strategic bidding, and increase the diversity of the winning
bidders. Meek, Chickering and Wilson presented a family of truthful stochastic
auctions for multiple identical items.
We present the first class of incentive compatible stochastic auctions for the
sponsored search setting. This class subsumes as special cases the laddered
auctions of and the stochastic auctions with the condex pricing rule of
Meek, Chickering and Wilson, consolidating these two seemingly disconnected mechanisms
in a single framework. Moreover, when the price per click depends deterministically
on the bids the auctions in this class are unique. Accordingly, we give a precise
characterization of all truthful auctions for sponsored search, in terms
of the expected price that each bidder will pay per click.
We also introduce randomized algorithms and pricing rules to derive, given an
allocation mechanism for the single- or multiple-identical-slots scenarios, a
new mechanism for the multislot framework with distinct slots. These extensions
have direct practical applications.
<<
Mónica Braga
"Estudio poliedral del problema de coloreo acíclico"
El problema de coloreo acíclico surge naturalmente en el contexto de la resolución
de problemas de partición de matrices. Muchos algoritmos para resolver problemas
de optimización numérica y sistemas de ecuaciones no lineales requieren de la
estimación de la matriz Jacobiana o Hessiana asociada a las funciones que participan
en el problema. Aprovechando la estructura poco densa de estas matrices, es posible
reducir la cantidad de evaluaciones de la función en forma significativa. El problema
de minimizar el número de evaluaciones necesarias para estimar una matriz Hessiana
se puede formular como un problema particular de coloreo de grafos. En esta charla
veremos cómo se modela este problema como un problema de coloreo acíclico, plantearemos
un modelo de programación lineal entera y comenzamos su estudio poliedral.
<<
Clara Betancur
"Coloreo equitativo de grafos y trabajo reciente sobre variaciones del
coloreo de grafos"
La noción de coloreo equitativo fué introducida por Walter Meyer
en el año 1973, coloreado que tiene como condición adicional, que
la cantidad de vértices de
cada clase de colores difiera a lo sumo en uno. La motivación provino de
Tucker con el problema de recolección de basura y Meyer pensó que
para este problema
era conveniente tener un número aproximadamente igual de rutas. En este
trabajo presentamos una serie de conceptos fundamentales y los resultados más
recientes,
que muestran el estado del arte sobre el coloreado equitativo de grafos. El número
cromático equitativo, χ=(G), es el menor entero k
tal que G es k-coloreado equitativamente. A partir de éste número
demostraremos algunos resultados para ciertos tipos de grafos, mostrando las condiciones
que se requieren para que tengan dicho coloreo.
<<
René Caldentey (New York University y U. de Chile)
"El Juego de la Cerveza (Beer Game)"
Las cadenas de suministro son el engranaje central que facilitan (o entorpecen)
el flujo de productos e informacion desde productores a clientes finales. Una
buena gestion de esta cadena de suministro (e.g., reduciendo los tiempos de
respuesta, disminuyendo inventarios de productos intermedios, aumentando la
calidad del servicio o reduciendo quiebres de stock, entre otras) es una necesidad
fundamental que enfrentan las empresas para asegurar el exito en la comercializacion
de sus productos.
En este Juego de la Cerveza, donde dos o más equipos competirán
entre sí de acuerdo a la cantidad de participantes, simularemos la operacion
de una cadena de suministro, identificando los principales problemas que tradicionalemente
afectan la gestion de inventarios e informacion de la cadena. Una vez finalizada
la simulacion discutiremos una serie de soluciones que han sido propuestas para
resolver estos problemas dentro de lo que se conoce en la literatura como estrategias
de "Quick Response".
Todos aquellos que quieran participar de una simulación de este Juego,
están cordialmente invitados. Previo al inicio del juego habrá
una breve clase de Inventario a cargo del Prof. Caldentey, para que todo el
que asista pueda participar del juego con más elementos de juicio. Para
organizar la logística del juego solicitamos que aquellos que vayan a
asistir lo confirmen a gduran(a)dm.uba.ar.
<<
Ivo Koch
"Sobre el problema de elegibilidad en el coloreo de grafos"
El problema de choosability fue planteado a mediados de los '70 por
Erdös, Rubin y Taylor. Se trata de una generalización del problema de
coloreo de grafos y consiste en asociar a cada vértice de un grafo G
una lista de colores admisibles del mismo tamaño k. Se busca encontrar
el mínimo k tal que cualquier coloreo de G, eligiendo para cada
vértice un color de su lista, sea un coloreo válido de G. Este k se
llama choice number de G, ch(G). En este problema es de gran interés
conocer los casos en que el choice number es igual al número cromático
de G.
Uno las conjeturas más importantes en esta área es comprobar si
ch(L(G)) = X(L(G)) para G, si G es un multigrafo y L(G) su grafo de
línea. X(G) es el número cromático de G.
Adicionalmente, Alon conjeturó en 1995 que si G es la unión
eje-disjunta de n grafos de orden n cada uno, entonces ch(G) = n.
Se mostrarán las direcciones de trabajo actuales en ambos problemas.
<<
Martín Pustilnik
"Caracterización del crecimiento de cultivos celulares monitoreados
sobre un microscopio mediante la toma de imágenes a intervalos regulares"
El seguimiento de un cultivo celular actualmente es un proceso manual en la
mayoría de los casos.
En este contexto es muy difícil analizar durante días y en forma
sistemática cualquier cultivo. En especial para las áreas de investigación
que requieren analizar procesos a largo plazo como cambios morfológicos
o respuestas de tratamientos inductores de la división, muerte y diferenciación
celular.
En esta charla presentaremos los conceptos para la generación de un algoritmo
de reconocimiento para algún estadio celular discreto en particular,
como el momento previo a la citocinesis (división celular citoplasmática),
a partir de las imágenes tomadas desde el microscopio.
Esto nos permitiría seguir el ciclo celular de forma individual
a lo largo de toda la secuencia de imágenes.
Finalmente se discutirán ideas que permitan caracterizar una célula
a partir de sus imágenes utilizando algoritmos similares al algoritmo
previamente expuesto.
<<
Nicolás Stier Moses
"Competencia en redes y eficiencia de equilibrios"
Podemos utilizar a las redes como el componente principal para modelar diversos
tipos de industrias. Algunos ejemplos obvios son en el área de telecomunicaciones
y transporte, pero también se usan en aplicaciones en logística,
cadenas de suministros y programación de máquinas. Como en la
mayoría de estos casos
el control del sistema no esta a cargo de una única entidad que vela
por el bienestar del sistema, sino por distintos agentes que intentan maximizar
sus ganancias, el sistema no opera en su punto mas eficiente. Aunque ejemplos
tradicionales de teoría de juegos como el Dilema del Prisionero muestran
que los equilibrios pueden
ser arbitrariamente ineficientes en general, esto no pasa en las aplicaciones
mencionadas. En esta charla haremos una reseña de resultados recientes
que muestran que los equilibrios de juegos de redes no son demasiado ineficientes
en el peor caso. Estos resultados, conocidos colectivamente como el Precio
de la anarquía, combinan ideas y técnicas traídas de disciplinas
variadas como Gestión de Operaciones, Economía e Informática
Teórica.
Bio:
Nicolas E. Stier Moses es Profesor Asociado de la Escuela de Negocios de la
Universidad de Columbia en Nueva York. Obtuvo un Ph.D. en Investigación
de Operaciones otorgado por el Massachusetts Institute of Technology (MIT).
Su investigación se enfoca en Gestión de Operaciones, en particular
en aspectos competitivos de redes logísticas, de distribución,
de transito y de telecomunicaciones, así como también en políticas
de precios para dichos sistemas.
<<