← volver

Ciclo conferencias Management Science-> Andreas Wiese, Profesor visitante Ingeniería Industrial

13:30-14:25 horas, sala Asamblea (Beauchef 851, 4° piso, Santiago)

Invitado: Andreas Wiese, Profesor visitante Ingeniería Industrial

Título conferencia: “Optimization methods applied to a problem in avionic industry” (joint work with Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier, Martin Skutella, and Jose Verschae)

Este ciclo convoca charlas de distinguidos académicos nacionales y extranjeros en temas de investigación en areas afines a gestion, incluyendo Gestion de Operaciones, Investigación Operativa, Marketing, Tecnologia de Informacion, Economia Conductual, entre otros.  Este seminario esta dirigido a academicos, post-docs, alumnos de post-grado y alumnos de pre-grado que trabajen en investigacion.

Abstract

In this talk we show how methods from optimization can be used to solve a problem arising at the aircraft manufacturer Boeing. This problem is part of the design process of the onboard computer of a new plane. We are given a set of tasks which represent computer programs that control the aircraft. The goal is to assign these task to the processors of the computer. In order
to guarantee flight safety, strict rules must be obeyed regarding which tasks can be assigned to the same processor. A standard optimization approach to a problem of this kind is to formulate it as an integer linear program (ILP) and then to solve it using e.g., CPLEX or Gurobi. For our problem, we demonstrate that standard textbook formulations are too weak to handle instances of even modest size. However, we show that real-world instance have properties which we can exploit to speed up the computation.

Using methods from combinatorial optimization to show that there are always solutions that are of a very special type. This then allows us to write a completely different ILP formulation which is able to solve instances of industrial size. Finally, we study the problem from a theoretical point of view and investigate approximation algorithms for it. In particular, we show a 2-approximation algorithm for the type of instances arising at Boeing which is provably best possible (unless P=NP which is widely believed in theoretical computer science).

Organizan: Ingeniería Industrial U. Chile e Instituto Sistemas Complejos de Ingeniería (ISCI)

Interesados confirmar asistencia AQUÍ

Más información: Pamela Tapia / ptapia@dii.uchile.cl