Dr. Tobias Achterberg (Gurobi & Zuse-Institut Berlin)

Abstract
Mathematical optimization, and more specicially mixed integer programming (MIP), is a field of operations research that emerged in the 1950s and that is nowadays a crucial part in a wide variety of business applications. Many practical planning and operational tasks can be formulated as a mixed integer program and solved reliably using commercial or academic software packages.  
In terms of solvability of practical problems, there is, however, a huge gap between theory and practice. Since MIP is NP-hard, the central theoretical question is whether P = NP, one of the seven so-called Millennium Problems, for whose solution the Clay Mathematics Institute has offered a prize of one million US dollars. Most researchers believe that P != NP, and hence, mixed integer programs that arise in applications should be impossible to solve in reasonable runtime. Computational results on practical problem instances, however, yield a completely different picture. State-of-the-art solvers are so powerful in exploiting the structure of real-world models that they often allow to solve instances with thousands or even millions of decision variables.  
With the example of the Gurobi MIP solver we show the development of solver performance during the last 18 years, and we give a brief insight into the research beind these improvements.
12.11.2026, Zeit: 17:00, Raum G03-106