Daniel Dadush appointed Professor of Geometry of Optimisation
Optimisation problems are everywhere
Utrecht University welcomes Daniel Dadush as the newly appointed Professor of Geometry of Optimisation. This position, a part-time role, resides within the Mathematical Institute, in close partnership with the Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands. The mission of this professorship is to advance the field of research and enhance its societal impact through a collaborative effort with computer scientists at Utrecht. Dadush: "The potential for synergy is vast when we combine our strengths."
Optimisation problems pervade our world, spanning international supply chains, public transport planning, and life-saving organ donor matching. These challenges demand optimal solutions that are intricate, and carry substantial consequences; finding the ideal answer can result in millions of euros saved or a significant reduction in CO2 emissions. In the modern age, many optimisation problems are addressed with the aid of commercial software built upon advanced optimisation algorithms, which are perpetually evolving to tackle increasingly complex issues efficiently.
Geometry of optimisation problems
Professor Dadush's research focuses on harnessing the geometric structure of optimisation problems. To cope with the need to solve ever more complex optimisation problems, he believes it is essential to develop a better understanding of these structures.
In many cases, the optimal solutions for optimisation problems can be visualised as points on the boundary or inside high dimensional objects known as polytopes. The geometric properties of the polytope must be exploited to find solutions quickly.
Figure 1 illustrates the famous simplex algorithm for solving linear optimisation problems. The vertices (corner points) of the 3D polytope represent the possible solutions to the optimisation problem at hand. The algorithm must quickly navigate the edges of the boundary to find the vertex minimizing a given cost function.
Figure 2 illustrates an integer algorithm for solving discrete optimisation problems. These algorithms model problems where the variables are required to take integer values only, such as how many drivers to assign to a delivery route, or how many containers to use to ship goods. Integer programming is one of the principal tools used for solving problems in logistics, healthcare, transportation and more.
Shedding light on a paradox: The efficiency of the simplex algorithm
Dadush’s career reached an important milestone when his work shed light on the mysteries of the widely utilised simplex algorithm. While remarkably efficient in practice, one can construct simple examples where it visits an exponential number of vertices, a behaviour which never occurs in real life instances. This long-standing paradox has puzzled researchers for years. In joint work with Sophie Huiberts, who did her doctorate research under Dadush’s supervision at CWI and UU and is now a researcher at the French National Centre for Scientific Research, he helped unravel this enigma.
They did so by improving smoothed analysis estimates. These estimates reveal how the algorithm behaves under small changes in the input data. Smoothed analysis is a powerful framework developed in 2001 to help explain the practical behaviour of algorithms, such as the simplex method. With their work, Dadush and Huiberts showed that this theory could provide much more precise estimates than previously known. The French newspaper Du Monde published an elaborate article about their achievement.
Combining strengths
One important goal of this professorship is to collaborate closely with computer scientists from the Algorithms and Complexity Group at Utrecht University. "The potential for synergy is vast when we combine our strengths,” Dadush says, referring to the mathematical rigor and theoretical foundations emerging from his field, and the practical problem-solving expertise of computer scientists. The partnership not only bridges the gap between theory and practice but also propels innovation, leading to the development of efficient, optimisation algorithms that can have a profound impact on society.