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.
Why the software works so well
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
- Personal homepage of Sophie Huiberts
- Sophie Huiberts' contact data at CWI
- Promotor: Prof. G.L.M. Cornelissen (UU), copromotor: Dr. D.N. Dadush (CWI), head of CWI's Networks and Optimization group
- Sophie Huiberts' browser plugin to use LaTeX on the chat website Slack can be installed in Firefox or Chrome, and source code is available on Github. The plugin has over 3500 active users.
