Optimization under Uncertainty works

State-of-the-art and its limits

Mixed-integer linear programming (MIP) is a well-established state-of-the-art technique for computer-aided optimization. Especially, in order to support the planning for logistics, this form of mathematical optimization has become standard. However, companies observe an increasing danger of disruptions that prevent them from acting as planned. One reason is that input data are often assumed to be deterministic, but in reality, they are afflicted with uncertainties which usually cannot be adequately described in MIPs. Currently, there are several activites which try to overcome this drawback. One of them is called

Quantified (Mixed Integer) Linear Programming

Quantified (Mixed Integer) Linear programs are both: a strong modelling language and an intuitive input to next generation optimization software. They serve with a rigorous formalism that allows to incorporate uncertainty bits into traditional MIP forlmulations. We mainly investigate the pure continuous variant (QLP), the pure integer variant (QIP), and a mixed variant where variables of the last stage may be continuous or discrete but the variables of all other stages have to be binary. For experiments, we have developed an own solver: Yasol.

Algorithms and Heuristics for Optimization under Uncertainty and Artificial Intelligence

Tree Search and Shortcut Heuristics

Originally, game tree search addressed two-person zero-sum games like Chess, Checkers, Go etc. However, there are various connections between this field of research and optimization under uncertainty.

• Our intuition says that playing chess against an opponent is somehow similar to optimizing a logistic task, considering Murphy's law.
• Complexity Theory devides the world of problems in different classes. Linear Programming is in P, linear integer programming is NP-complete and quantified integer programming is PSPACE-hard. It is the similar for parlour games. Simple puzzles are in P, many one-person games like Sudoku or Solitair are NP-complete and many two-person games like Chess, Checkers, amd Go are PSPACE-hard.
• Two algorithms have become famous in the area of two-person zero-sum games, i.e. the alphabeta algorithm and the UCT search. Nowadays, we apply them in the solution process of Quantified Integer Programs.

•  Hartisch M., Lorenz U., (2019): Mastering Uncertainty: Towords robust multistage optimization with decision dependent uncertainty. In Pacific Rim International Conference on Artificial Intelligence, pages 446-458. Springer, 2019. 

• Hartisch M., Lorenz U., (2019): Game tree search in a robust multistage optimization framework: Exploiting pruning mechanisms. arXiv preprint arXiv: 1811.12146;To appear in: 16th International Conference on Advances in Computer Games, ACG 2019.

• T. Ederer, M. Hartisch, U. Lorenz, T. Opfer, J. Wolf (2017): Yasol: An Open Source Solver for Quantified Mixed Interger Programs. Advances in Computer Games 15, Springer 2016

• U. Lorenz, J. Wolf (2015): Solving Multistage Quantified Linear Optimization Problems with the Alph-beta nested Benders Decomposition. EURO Journal on Computational Optimization, Springer 2015, pp. 349–370.

• T. Ederer, U. Lorenz, A. Martin, J. Wolf (2011): Quantified Linear Programs: A Computational Study, Proceeding ESA, 2011,Springer, 2011, 203-214, Saarbrücken, Deutschland.

• T. Graf, U. Lorenz, M. Platzner, L. Schaefers (2011):Parallel Monte-Carlo Tree Search for HPC Systems.  In Proc. European Conf. on Parallel Processing (Euro-Par), volume 6853 of Lecture Notes in Computer Science (LNCS), Springer, 2011.

• C. Donninger, U. Lorenz. The Chess Monster Hydra. International Conference on Field-Programmable Logic and Applications (FPL), 2004, Antwerpen – Belgium, LNCS 3203, pp. 927 – 932, eds. J. Becker, M. Platzner, S. Vernalde.

  other ...

Validation via highly competitive demonstrators

Chess programs: Hydra, P.ConNers

Go program: Gomorra 

 

Real World Applications 

We have been involved in the following applications. 

• Aircraft Planning, Fleetassignment
• Production Planning
• Railway Delay Management
• Process Chains under Uncertainty [2]
• Planning and Control, and Simulation