Algorithms in search of many optimal solutions
Making decisions is not always easy, especially when you are pursuing several goals all at once. Computer programs can help by finding solutions to complex problems in fields such as production, logistics and mobility. But even highly developed computer-aided technologies are challenged to find the best – the optimal – solutions, for this requires taking into account hundreds or even thousands of variables.
In her FWF-funded project “MOMIP: Multi-objective (mixed) integer programming”, Sophie Parragh, Head of the Department of Production and Logistics Management at the Johannes Kepler University Linz, and her team are investigating new algorithms that are designed to solve a specific type of optimization task: mixed-integer problems with several different objectives, all of which are to be met in the best possible way. “Many problems in business can be modeled as mixed-integer systems,” says the researcher. “We are talking here about mathematical models that take into account costs, resources, decisions and a great deal more.”
There is a wide range of potential applications for these algorithms: they can be used to minimize CO2 emissions in a production chain or to find the optimal routes for shared electric mobility, which is expected to not only keep waiting times for customers short but also minimize noise pollution for residents. Another example relates to the efficient planning of mobile care services. In this context it is not only important to ensure sufficient care time, but also to take into account the wishes of customers in terms of preferred caregivers and visiting times.
Sophie N. Parragh's research focuses on the development of optimization methods for decision support in production and logistics. The “MOMIP: Multi-objective (mixed) integer programming” project (2018–2022) received roughly EUR 390,000 in funding from the Austrian Science Fund FWF.
Defining variables from flexible to fixed
Mixed integer models mean that some variables in the model are continuous – hence can assume all possible values – while some variables can only assume certain integers such as zero or one. To give an example: the length of a delivery service's route is a continuous variable, because the delivery van driver can take any number of different detours to avoid certain roads and thereby make the route longer. The decision to set up a parcel distribution center, on the other hand, is an integer variable, as it can only be built (represented as “1”) or not (represented as “0”).
Apart from the mixed-integer variables, the second key aspect that Parragh and her team are addressing is the need to fulfil several objectives simultaneously. While holding particular challenges for the researchers, this aspect also enables the system to find more nuanced approaches to solutions.
Many goals, many solutions
“Previously established algorithms were mainly able solve tasks having only one objective. They can therefore find only one optimal solution, but this is not always helpful,” notes Parragh. When delivering parcels, for example, the obvious goal is to keep transportation costs as low as possible. Focusing on costs alone, however, leads to other goals being neglected.
“Algorithms with multiple objectives, like ours, can find a set of optimal solutions that represent different trade-offs,” explains Parragh. “One of the solutions may generate the lowest cost but result in more CO2 emissions. Another solution may be a little more expensive but produce fewer emissions. And there are many other solutions in between those two.”
Elbow room for the management
In the context of their project, the researchers were looking for a method that finds the optimal solutions for different types of complex problems. Existing programs have already found approximations to the best solutions, but the aim of Parragh and her team is to create general algorithms that are mathematically proven to find the optimal solutions for many different problems.
With the nuanced solutions that their programs produce, Parragh and her team want to give decision-makers in business and politics more elbow room. “Our models have shown us that goals such as reduced emissions, environmental protection or even higher customer satisfaction suffer if the only thing you focus on is optimizing cost,” says Parragh. “These goals can often be achieved in a much better way provided you accept slightly higher costs.”
Branched algorithms
“Combinatorics is a key issue in the problems we are working on. This means that the number of possible combinations of variables for different solutions rises enormously fast, so that we can no longer deal with them easily,” explains Parragh. Together with her team – Nicolas Forget, Fabien Tricoire, Duleabom An, Markus Sinnl and Miriam Enzi – and international cooperation partners, she developed so-called branch-and-bound algorithms.
With the branch-and-bound method, the set of all possible solutions – meaning not just the optimal ones – is divided into smaller groups that are then examined individually. Instead of analyzing all solutions at once, the program can thus decide more quickly whether the optimal solutions it is looking for are to be found at all in one of these sub-groups.
If the computations reveal that the optimal solutions cannot be found in an individual group, all the solutions in this group are discarded. If a group does include the optimal solutions, the algorithm of this group can be branched out into even smaller sub-groups and the search goes on. With this system of branching out, the program finally finds the optimal solutions that meet the desired objectives with various trade-offs.
Project milestone
This is Parragh’s conclusion: “One of the milestones at the end of the project was that we developed an algorithm for systems with around one hundred integer decision variables and for three or even four objectives and that the algorithm is able to compete with other established methods. We are now working on further developing these programs.”
Parragh and her team continued their work after the end of the “MOMIP: Multi-objective (mixed) integer programming” project in September 2022. They refined their algorithms, for example to model the risk awareness of decision-makers, open up new fields of application or make the calculations more effective. The research teams can rest assured that the need for nuanced solutions to the problems of our complex society will not diminish in the future.
Personal details
Sophie Parragh studied international business administration at the University of Vienna. As a postdoc, she conducted research at the IBM Center for Advanced Studies in Porto and subsequently held a Hertha Firnberg position funded by the FWF. After a visiting professorship at the Vienna University of Economics and Business, she completed her professorial qualification at the University of Vienna in 2016. Sophie Parragh has been heading the Institute of Production and Logistics Management at the Johannes Kepler University Linz since March 2017.
Publications
Forget N., Parragh S. N.: Enhancing Branch-and-Bound for Multiobjective 0-1 Programming, in: INFORMS Journal on Computing 2024
An D., Parragh S. N., Sinnl M., Tricoire F.: A matheuristic for tri-objective binary integer linear programming, in: Computers & Operations Research 2024
Parragh S.N., Tricoire F., Gutjahr W.J.: A branch-and-Benders-cut algorithm for a bi-objective stochastic facility location problem, in: OR Spectrum 2022
