Daniel Dadush appointed Professor of Geometry of Optimization

Daniel Dadush is appointed Professor of Geometry of Optimization at Utrecht University. This position, a part-time role, resides within the Mathematical Institute (UU), 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.

Optimisation problems are everywhere

Optimization 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 optimization problems are addressed with the aid of commercial software built upon advanced optimization algorithms, which are perpetually evolving to tackle increasingly complex issues efficiently.

Geometry of optimisation problems

Daniel Dadush's research focuses on harnessing the geometric structure of optimization problems. To cope with the need to solve ever more complex optimization problems, he believes it is essential to develop a better understanding of these structures.

In many cases, the optimal solutions for optimization problems can be visualized 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 optimization problems. The vertices (corner points) of the 3D polytope represent the possible solutions to the optimization 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 optimization 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 utilized 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 PhD research under Dadush’s supervision at CWI, defended it at 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

At CWI, Daniel Dadush is the group leader of the Networks and Optimization research group. 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, optimization algorithms that can have a profound impact on society.

Picture of Daniel Dadush: ©Universiteit Utrecht. Source: news item on Daniel Dadush's professorship on the UU website.

See also Daniel Dadush's contact data at CWI.