ELAVIO     Escuela Latinoamericana de Verano de Investigación Operativa english   
e-mail   


IX ELAVIO
Escuela Latinoamericana de Verano de Investigación Operativa

Vaquerías, Córdoba, Argentina
25 de febrero al 1 de marzo de 2002


Resúmenes

métodos eficientes de simulación para cálculo de medidas de performance en modelos markovianos
Hector Cancela, Universidad de La República, Uruguay

Entre las herramientas más empleadas para modelar aspectos de funcionamiento, servicio, confiabilidad y desempeño de distintos tipos de sistemas (como por ejemplo las redes de comunicaciones) estan las cadenas de Markov. En muchos casos, para modelar adecuadamente el sistema en estudio es necesario emplear una cadena con un número de estados muy grande (o aún infinito), por lo que no es posible aplicar los métodos analíticos usuales para calcular medidas transitorias y asintóticas en la cadena. Una alternativa es el empleo de métodos de simulación para obtener valores aproximados, con una estimacion del error cometido.

En este tutorial, cubriremos distintos aspectos de estos métodos, viendo las limitaciones de la simulación estándar y discutiendo alternativas tales como diversas técnicas de reducción de la varianza que permiten una mayor eficiencia (relación precisión/tiempo de cálculo) en el cálculo de las diversas medidas. En particular, nos concentraremos en casos en que la medida de interés corresponde a eventos raros (de muy pequeña probabilidad) del sistema, y en como encarar este problema a través de muestreo según importancia, splitting, y otras técnicas.

Decomposition methods and applications
Jacques Desroisiers, GERAD-Universidad de Montreal, Canadá

Lagrangian relaxation, Dantzig-Wolfe, Analytic cutting planes, Benders with applications to the field of vehicle routing and crew scheduling.

Métodos de proyecciones para problemas de equilibrio
Alfredo Iusem, IMPA, Brasil

Consideramos una formulación de problemas de equilibrio (que llamamos "Problema de Equilibrio Abstracto") que tiene como casos particulares, entre otros, problemas de desigualdades variacionales, problemas de equilibro de Nash y problemas de optimización a valores vectoriales. Mostramos que este problema puede ser visto como un problema de factibilidad convexa con infinitos conjuntos convexos, pero con propiedades adicionales, de manera que algoritmos conocidos para factibilidad convexa, como los métodos de proyecciones, pueden ser modificados mejorando sus propiedades de convergencia, consiguiéndose convergencia global sin hipótesis de compacidad o coercividad. Analizamos uno de estos algoritmos, estableciendo tales propiedades.

Algoritmos relax and cut
Abilio Lucena, Universidade Federal de Rio de Janeiro, Brasil

Sobre como usar Relaxacao Lagrangeana diante de um numero exponencial de desigualdades candidatas a dualizacao. Este tipo de enfoque pode ser visto como um "branch and cut" Lagrangeano e vem funcionando muito bem para as mais diversas aplicacoes.

Até o momento, trabalhei nas seguintes aplicacoes: Steiner Problem in Graphs, Quadratic Knapsack Problem, Vehicle Routing Problem, Rectangular Partitioning Problem (é uma aplicacao em geometria computacional) e Linear Ordering Problem.

Atualmente estou trabalhando em uma aplicacao para uma empresa de aviacao que consiste em resolver Set Covering Problems com restricoes adicionais. Este e o modulo principal de um sistema de Crew Scheduling.

As origens da ideia talvez possam ser associadas a um trabalho de Balas e Christofides, de 1980. Em 1992 propuz um algoritmo, bastante distinto do de Balas e Christofides, para o Steiner Problem in Graphs. Em 1994, Escudero, Guignard e Malik apresentaram, independentemente, um algoritmo parecido com o meu para o Sequential Ordering Problem. Deram a este algoritmo a denominacao de Relax and Cut. Esta é a forma como esta classe de algoritmos vem sendo chamada na literatura...

Optimización del valor ordenado
Jose Mario Martinez, UNICAMP, Brasil

El problema de optimización del valor ordenado (OVO) ha sido introducido recientemente por R. Andreani, C. Dunder y J. M. Martínez. Dadas m funciones f1,...,fm definidas en R^n y a valores reales, para cada x en el dominio los valores funcionales se ordenan de menor a mayor y la función (p-)OVO se define como aquel valor que ocupa el p-esimo valor en este orden. Si p=m la función OVO es el máximo entre f1(x), ..., fm(x). Si p=1 es el mínimo. El problema OVO consiste en minimizar la función OVO. Por lo tanto, un caso particular del mismo es el clásico problema minimax finito.

La motivación el problema OVO reside en dos tipos de aplicaciones. En los procesos de toma de decisiones la función fi(x) puede representar el perjuicio previsto si se toma la decisión x bajo el i-ésimo escenario. La decisión minimax corresponde a minimizar el máximo perjuicio. Esta decisión corresponde a una estrategia muy pesimista y, muchas veces, el tomador de decisión no desea descartar algunos de los peores escenarios de manera de proceder de manera más realista. La decisión que viene de resolver el problema OVO corresponde a descartar los m-p peores escenarios, para cada decisión posible x. La segunda motivación viene de la estimación robusta de modelos. En este caso, fi(x) representa el error en la observación i-ésima cuando se usan los parámetros x. Si las observaciones tienen grandes errores (sobre todo sistemáticos) es importante tener una manera automática de descartarlos. El problema OVO también se dirige a este objetivo.

La función OVO es continua (si las fi lo son), no diferenciable, casi siempre no convexa y tiene muchos minimizadores locales no globales. Proponemos un método directo para su minimización e introducimos una reformulación del problema como programación no lineal (PNL) suave. Analizamos el PNL correspondiente y, entre otros resultados, obtenemos que todos los puntos estacionarios satisfacen las condiciones KKT, independientemente de condiciones de regularidad.

The Volume Algorithm and the Relax-and-Cut method revisited: relation with bundle methods
Claudia Sagastizabal, PUC- RIO

The talk is divided in two parts. First we revise the Volume Algorithm (VA) for linear programming and relate it to bundle methods. When first introduced, VA was presented as a subgradient-like method for solving the original problem in its dual form. In a way similar to the serious/null steps philosophy of bundle methods, VA produces green, yellow or red steps. In order to give convergence results, we introduce in VA a precise measure for the improvement needed to declare a green or serious step. This addition yields a revised formulation (RVA) that is halfway between VA and a specific bundle method, that we call BVA. We analyze the convergence properties of both RVA and BVA. Finally, we compare the performance of the modified algorithms versus VA on a set of Rectilinear Steiner problems of various sizes and increasing complexity, derived from real world VLSI design instances. Joint work with L.Bahiense and N. Maculan (UFRJ, Rio).

Second, we focus on the Relax and Cut Lagrangian approach. Lagrangian relaxation is a popular technique to solve combinatorial optimization problems. However, the applicability of this technique depends on having a relatively low number of hard constraints to dualize. When there are exponentially many hard constraints, it is preferable to relax them dynamically, according to some rule depending on which multipliers are active. For instance, only the most violated constraints at a given iteration could be dualized. This is the so-called Relax and Cut method. From the dual point of view, this approach yields multipliers with varying dimensions and a dual objective function that changes along iterations. We discuss how to apply a bundle methodology to solve this kind of dual problems. We analyze the convergence properties of the resulting dynamic bundle method and present some numerical experience on Linear Ordering and Travelling Salesman Problems. Joint work with A. Belloni (Impa).

Optimality Systems: Regularity Conditions, Error Bounds and a Class of Newton-Type Methods
Mikhail Solodov, IMPA, Brasil

We discuss error bounds and Newton-type methods for optimality systems of Karush-Kuhn-Tucker type. We obtain a new error bound under an assumption which we show to be strictly weaker than assumptions previously used for KKT systems, such as quasi-regularity or semistability.

Error bounds are useful, among other things, for identifying active constraints and developing efficient local algorithms. We propose a family of local Newton-type algorithms. This family contains some known active-set Newton methods, as well as some new methods. Regularity conditions required for local superlinear convergence compare favorably with convergence conditions of nonsmooth Newton methods and sequential quadratic programming methods.

A Short Survey on Intersection Graphs
Jayme Luiz Szwarcfiter, UFRJ, Brasil

Let S be a family of subsets of some set. The intersection graph of S is a graph G, such that the vertices of G are the subsets of S, two vertices being adjacent in G, whenever the corresponding subsets of S intersect. There are many classes of graphs with can be defined, by finding suitable families of subsets S. We describe some of these classes and present algorithmic applications. Various open problems on this subject will be formulated.

From Conjecture to Theorem: A Progress Report on the Strong Perfect Graph Conjecture
Annegret Wagler, ZIB, Berlin

Berge introduced 1960 the notion of a perfect graph. It turned out that the perfection of some graph classes could be easily proved or followed from well-known theorems of König and Dilworth. The knowledge on these classes of perfect graphs motivated Berge's two famous conjectures: The Perfect Graph Conjecture (which says that a graph is perfect if and only if its complement is) was proved by Lovasz in 1972. The Strong Perfect Graph Conjecture (which says that a graph is perfect if and only if it is Berge, i.e., if it does not contain odd holes or odd antiholes as induced subgraphs) has been open for over 40 years.

The Strong Perfect Graph Conjecture has attracted a lot of attention and has been verified for many graph classes over the years. The proof of that conjecture for square-free Berge graphs by Conforti, Cornuejols & Vuskovic 2001 let to a conjecture how to decompose general Berge graphs. This conjecture was proved in a slightly different form with the help of a remarkable sequence of results by Chudnovsky, Robertson, Seymour & Thomas 2002 - and finally verified the Strong Perfect Graph Conjecture.


Última actualización: 29.01.2003