ERC Starting grant for CWI researcher Daniel Dadush

In July, Daniel Dadush (CWI) was awarded an ERC Starting Grant of 1.5 million euro for his proposal ‘Towards a Quantitative Theory of Integer Programming’. He aims to revolutionize the understanding of integer programming (IP), the most popular method for finding optimal solutions to optimization problems.

Publication date: 27-07-2018

In July, Daniel Dadush from Centrum Wiskunde & Informatica (CWI) in Amsterdam was awarded an ERC Starting Grant of 1.5 million euro for his proposal ‘Towards a Quantitative Theory of Integer Programming’. With this grant, Dadush aims to revolutionize the understanding of integer programming (IP), the most popular method used today for finding optimal solutions to real-world optimization problems. Such problems include finding the most efficient way to schedule a train timetable, optimize an assembly line, or to ship goods to customers from an astronomically large set of alternatives. The future results are expected help modern IP solvers – such as CPLEX, Gurobi and SCIP, currently used ubiquitously in industry – improve their practical performance.

For his research, Dadush will develop a quantitative theoretical approach for predicting when and how well IP techniques will perform on real-world instances, a challenge which has long resisted theoretical attempts. Many of the techniques underlying modern IP solvers were developed in the 1950s and 60s, long before the advent of modern computing, and the reasons for why they are so effective at finding optimal solutions in practical problems remain a mystery. As Dadush explains: “The standard paradigm of measuring the worst-case behaviour of algorithms provides only very limited insights into the success of IP techniques. I believe a new paradigm is needed to explain their surprising effectiveness, which I would call ‘optimistic-case’ analysis.” On receiving the ERC grant, he replied: “I am very grateful to the European research council for supporting this research, which I believe will lead to substantial improvements in our ability to solve IPs”.

Dadush obtained his PhD at the Georgia Institute of Technology in 2012 and has been a tenure track researcher in the CWI Networks and Optimization research group since 2014. He is best known for his work on algorithms for lattice problems and integer programming. In 2015, he won the triennial Tucker Prize for Best Thesis in Mathematical Optimization from the Mathematical Optimization Society as well as an NWO Veni Grant. In 2011, he won the INFORMS Optimization Society Student Paper Prize. The ERC Starting grant, which is expected to begin in January 2019 and will run for 5 years, pays for two postdoc positions and two PhD students. More information on the grants awarded by the European Research Council (ERC) can be found at http://erc.europa.eu/.

More information