New mathematical insights on popular optimization methods

The widely used simplex algorithm (1947) is one of the algorithms that work well in practice, while according to the theory, this should not always be possible. Sophie Huiberts (CWI) and her colleagues provided new theoretical solutions for long-standing problems in this area.

Publication date: 30-05-2022

In 1947, George Dantzig invented the simplex algorithm, which is still widely used around the world for optimization processes: from optimizing compound feeds to aircraft movements. This is one example of an algorithm that works well in practice, while, according to the theory, this should not always  be possible. For a long time, no one understood that. In her research, Sophie Huiberts - PhD student at the Centrum Wiskunde & Informatica (CWI) - and her colleagues provided new theoretical solutions for long-standing problems in this area. Huiberts defended her PhD thesis 'Geometric aspects of linear programming: shadow paths, central paths, and a cutting plane method' at Utrecht University on 16 May.

For software developers and researchers it is important which algorithms are fast and which are slow; it makes the difference between seconds or weeks of computing time. One application, for example, is planning software that optimizes processes: from package delivery and international supply chains to matching kidney donors with patients. Better planning can cut your costs and get better results with the resources you have. Despite its importance, little is known about why this software works so well.

“In my research I studied different models and I was able to turn certain practical observations into hard mathematics,” Huiberts says. “In one project, we investigated the effect of adding a little random noise to the input of the so-called simplex algorithm, an important part of all software for solving so-called mixed integer linear programming problems. We were able to prove that this algorithm is much faster after noise had been added. This addition of noise already happened in practice, but no one knew why it worked. My research helps to understand important algorithms for solving linear programming problems, including the Simplex method, Internal Point methods, and  Cutting Plane methods.”

Columbia University

Sophie Huiberts did her research in the Networks & Optimization group of the Centrum Wiskunde & Informatica (CWI). She previously studied mathematics and computer science at Utrecht University and is a Junior Fellow of the Simons Society at Columbia University in New York, USA. Huiberts gave an international 'Rising Star talk' at the STOC 2021 meeting, was invited to participate in the Heidelberg Forum and, as chair of CWI's works council, was committed to promoting diversity in the workplace. She designed a browser plugin for LaTeX on chat website Slack, which allows mathematicians to communicate easily and which has 3500 users.

More information