Combinatorial Optimization
Framework
In many fields of industry and technology solving complex optimization problems is the key to increasing productivity and product quality. It is the objective of a combinatorial optimization method to search for the best solution out of a very large number of possible solutions. Normally, the best solution means the solution with the lowest costs or the solution with the highest profit.Simply checking or enumerating all possible solutions of real-world problems would take thousands of years even if using the fastest supercomputers of the world. Classical approaches (e.g. linear integer programming) on the other hand, are not at all efficient in this case. Now, the use of parallel computing shows a way out of this deadlock.
During the last decades optimization methods remarkably improved planning tasks in many areas like transportation, production, and finances. In order to solve complex practical problems with the help of computers the problems have to be transformed into a formal model that abstracts their relevant aspects. But most of the time it is still assumed that all necessary information is known exactly at the time of optimization whereas in practice the information is uncertain to some degree. Therefore, this kind of model building implicitly can result in a significant loss of achievable solution quality for many practical optimization problems.
If the uncertainty of information can be formalized by some random variables with known probability distributions, stochastic optimization can be used to overcome the aforementioned shortcoming by looking for solutions with optimal expected quality. Furthermore, stochastic optimization can also adhere to various risk measures besides expected values, like e.g. the variance.
Multi-stage stochastic optimization problems have the following structure, for which the concept of recourse decisions plays a central role: At a given point a decision maker takes some action in the first stage, after which a random event occurs affecting the outcome of the first-stage decision. A recourse decision can then be made in the second stage that compensates for any bad effects that might have been experienced as a result of the first-stage decision. Then another random event occurs which necessitates another recourse decision, and so on. The optimal policy from such a model is a single first-stage policy and a tree-like collection of recourse decisions (a decision rule) defining which action should be taken in response to each random outcome.
In the research group of Prof. Monien multi-stage stochastic optimization is used for the disruption management of aircraft fleets, in which we combine our long-time experience in airline optimization and parallel game tree search. When disruptions (delays, technical failures, ?) occur the aircraft schedule of an airline becomes invalid and must be repaired by e.g. holding back flights, changing the associated aircrafts of flights, or cancelling flights. During the search for a cost-efficient repair possible future disruptions are taken into account by means of a new solution method for multi-stage stochastic optimization problems.
This new method interprets the optimization problem as a 2-person game, where one player (operations controller) is allowed to make repairs to a disrupted schedule and the other player (nature) can inflict disruptions on the schedule. The operations controller want to find repairs with minimal induced costs, whereas nature randomly selects disruptions according to given probability distributions. Such a game can be represented by a game tree and the optimal move (the repair with least expected costs) of the operations controller can be determined with the help of an extended game tree search algorithm. As a result, the total repair costs could significantly be reduced compared to an established deterministic solution method based on integer programming.
A grand challenge for the future is the application of stochastic optimization to other areas like production planning. Furthermore, new strategies must be developed to cope with the increasing algorithmic complexity induced by stochastic models, e.g. by using massive parallel systems.
Applications
Transportation PlanningContact
Sven Grothklags (sven@upb.de)Georg Kliewer (geokl@upb.de)
Index A – Z | Impressum | Webmaster