The FICO Xpress Best Paper Award was established in 2022 to recognize exceptional research in Mathematical Optimization, Operations Research, and related fields. Among many high-quality submissions, the scientific committee had the challenging responsibility of selecting a winner for the 2024 edition of the award. And the Award goes to …*drumroll* …:
Luteberget, Bjørnar, and Giorgio Sartor. "Feasibility Jump: an LP-free Lagrangian MIP heuristic." Mathematical Programming Computation 15.2 (2023): 365-388.
In this blog post, we explore the innovative new heuristic developed by Bjørnar and Giorgio, which not only won the FICO Xpress Best Paper Award but also became part of the FICO Xpress Solver once the Xpress development team became aware of this great algorithm.
How do we find solutions to difficult optimization problems with millions of variables and constraints in just a few seconds? In general, that can be an extremely hard challenge. Unless the problem we are considering possesses special structures, optimization solvers can require significant computational time to find a first feasible solution. This is where heuristic algorithms, such as the awarded Feasibility Jump (JP), can make a difference.
Many important optimization problems arising from real-life scenarios can be modeled via mathematical programming and subsequently solved by sophisticated algorithms such as those available in the FICO Xpress Solver. Unfortunately, most of these problems are intrinsically difficult to solve to proven optimality (for example, vehicle routing, portfolio optimization, or production planning). This prompts clever techniques that are specifically designed for certain types of problems.
Let’s quickly recap some technical details. When solving a MIP problem, optimization solvers typically start by finding the optimal solution to the so-called Linear Programming (LP) relaxation of the problem, which is constructed by relaxing the integrality constraints (for example, a binary variable of the original MIP problem can take any value between 0 and 1 in its LP relaxation instead of being restricted to taking either 0 or 1, but nothing in between). The LP solution may be infeasible for the original MIP problem (because some integer variables may have fraction values), but it is computed relatively quickly, and it provides a starting point for several exact and heuristic algorithms. However, in large-scale MIP problems, even computing an LP solution may be challenging, substantially delaying the discovery of a first MIP solution.
Feasibility Jump is a heuristic algorithm for MIP problems that does not require computing any LP solution. Therefore, it can be very effective in quickly producing feasible solutions to large-scale, complex MIP problems.
MIP heuristics that don't require LP solutions can be divided into two classes, propagation heuristics and relaxation heuristics. The first ones choose a variable ordering and assign values to variables following this order. Whenever a variable is assigned a value, this value is "propagated" through all the constraints in which the variable is included, possibly fixing other variables. This greedy behavior (i.e., previous variables assignments cannot change) can easily lead to infeasible situations, making these heuristics very quick but not particularly effective.
The second class of heuristics, relaxation heuristics, considers a different formulation of the MIP problem in which some constraints are relaxed, i.e. temporarily removed. Feasibility Jump (FJ) belongs to this class. FJ is a Lagrangian relaxation heuristic, meaning that relaxed constraints no longer restrict the feasible region and that solutions that don't satisfy these constraints are penalized in the objective function. FJ takes this approach to the extreme and relaxes all constraints but the integrality ones.
Technically speaking, the algorithm used by FJ can be best described as a highly efficient stochastic guided local search over a Lagrangian relaxation, and it can be summarized as follows:
Feasibility Jump was initially developed for the MIP 2022 Computational Computation, which challenged participants to develop LP-free MIP heuristics. After winning the competition, a question was left hanging in the air: How does FJ compare with state-of-the-art commercial solvers, and can it be used to complement them? This is where the FICO Xpress Solver entered the picture: its high customization capabilities and low-level control possibilities were essential to properly integrate and rigorously test FJ inside a MIP solver for the award-winning paper.
Figure 2 shows the ratio between the time it takes to find the first feasible solution by Xpress alone (XPR) and FJ integrated into Xpress (XPR+FJ) on the well-known MIPLIB 2017 benchmark set (time limit set to 60 seconds). For more than half of the instances (some of which have millions of variables and constraints), FJ contributed to a significant reduction in Time to Feasibility. This can represent the difference between obtaining the first feasible solution in seconds instead of minutes!
Figure 3 shows how these quick feasible solutions can also improve Time to Optimality in certain scenarios. The effect here is less pronounced, but it represents an average reduction of 3%, which is significant for a mature commercial solver such as the FICO Xpress Solver.
We at FICO congratulate Bjørnar and Giorgio on winning the 2024 FICO Xpress Best Paper Award. Amidst numerous strong contenders, their remarkable research stood out prominently. The Award jury was impressed by its originality and practical relevance. The awarded paper significantly contributed to the development of MIP technology and showed remarkable results in challenging instances.
Like many other research teams worldwide, the authors are members of our Academic Partner Program. Join our FICO Xpress Optimization Community and learn about our free community licenses for everyone and our fully-fledged free licenses for all academics. The call for the 2025 edition of the FICO Xpress Best Paper Award is out now: Consider submitting your Xpress-related research paper!
Luteberget, Bjørnar, and Giorgio Sartor. "Feasibility Jump: an LP-free Lagrangian MIP heuristic." Mathematical Programming Computation 15.2 (2023): 365-388.
In this blog post, we explore the innovative new heuristic developed by Bjørnar and Giorgio, which not only won the FICO Xpress Best Paper Award but also became part of the FICO Xpress Solver once the Xpress development team became aware of this great algorithm.
Figure 1: Award winner Giorgio Sartor (right) and Timo Berthold, head of the award committee, at the EURO2024 conference. Where the award was handed over
How do we find solutions to difficult optimization problems with millions of variables and constraints in just a few seconds? In general, that can be an extremely hard challenge. Unless the problem we are considering possesses special structures, optimization solvers can require significant computational time to find a first feasible solution. This is where heuristic algorithms, such as the awarded Feasibility Jump (JP), can make a difference.
Many important optimization problems arising from real-life scenarios can be modeled via mathematical programming and subsequently solved by sophisticated algorithms such as those available in the FICO Xpress Solver. Unfortunately, most of these problems are intrinsically difficult to solve to proven optimality (for example, vehicle routing, portfolio optimization, or production planning). This prompts clever techniques that are specifically designed for certain types of problems.
Let’s quickly recap some technical details. When solving a MIP problem, optimization solvers typically start by finding the optimal solution to the so-called Linear Programming (LP) relaxation of the problem, which is constructed by relaxing the integrality constraints (for example, a binary variable of the original MIP problem can take any value between 0 and 1 in its LP relaxation instead of being restricted to taking either 0 or 1, but nothing in between). The LP solution may be infeasible for the original MIP problem (because some integer variables may have fraction values), but it is computed relatively quickly, and it provides a starting point for several exact and heuristic algorithms. However, in large-scale MIP problems, even computing an LP solution may be challenging, substantially delaying the discovery of a first MIP solution.
Feasibility Jump is a heuristic algorithm for MIP problems that does not require computing any LP solution. Therefore, it can be very effective in quickly producing feasible solutions to large-scale, complex MIP problems.
MIP heuristics that don't require LP solutions can be divided into two classes, propagation heuristics and relaxation heuristics. The first ones choose a variable ordering and assign values to variables following this order. Whenever a variable is assigned a value, this value is "propagated" through all the constraints in which the variable is included, possibly fixing other variables. This greedy behavior (i.e., previous variables assignments cannot change) can easily lead to infeasible situations, making these heuristics very quick but not particularly effective.
The second class of heuristics, relaxation heuristics, considers a different formulation of the MIP problem in which some constraints are relaxed, i.e. temporarily removed. Feasibility Jump (FJ) belongs to this class. FJ is a Lagrangian relaxation heuristic, meaning that relaxed constraints no longer restrict the feasible region and that solutions that don't satisfy these constraints are penalized in the objective function. FJ takes this approach to the extreme and relaxes all constraints but the integrality ones.
Technically speaking, the algorithm used by FJ can be best described as a highly efficient stochastic guided local search over a Lagrangian relaxation, and it can be summarized as follows:
- Determine an initial variable assignment; any will work as long as it satisfies the integrality constraints. Initialize variable scores: higher positive (lower negative) scores indicate a propensity to move closer to (move away from) a feasible solution.
- If the assignment is feasible, we are done. Otherwise, choose the variable with the highest score.
- If the score is negative (we are in a local minimum), update the scores by increasing the importance of the currently unsatisfied constraints and choose a new variable at random.
- Assign the value that minimizes a weighted sum of constraint violations to the chosen variable. This is called the jump value.
- Update the jump value of the chosen variable and all the relevant variable scores.
- Go to Step 2.
Feasibility Jump was initially developed for the MIP 2022 Computational Computation, which challenged participants to develop LP-free MIP heuristics. After winning the competition, a question was left hanging in the air: How does FJ compare with state-of-the-art commercial solvers, and can it be used to complement them? This is where the FICO Xpress Solver entered the picture: its high customization capabilities and low-level control possibilities were essential to properly integrate and rigorously test FJ inside a MIP solver for the award-winning paper.
Figure 2 shows the ratio between the time it takes to find the first feasible solution by Xpress alone (XPR) and FJ integrated into Xpress (XPR+FJ) on the well-known MIPLIB 2017 benchmark set (time limit set to 60 seconds). For more than half of the instances (some of which have millions of variables and constraints), FJ contributed to a significant reduction in Time to Feasibility. This can represent the difference between obtaining the first feasible solution in seconds instead of minutes!
Figure 2: Ratio between Time to Feasibility (TF) of XPR and XPR+FJ for the MIPLIB 2017 benchmark set.
Figure 3 shows how these quick feasible solutions can also improve Time to Optimality in certain scenarios. The effect here is less pronounced, but it represents an average reduction of 3%, which is significant for a mature commercial solver such as the FICO Xpress Solver.
Figure 3: Ratio between Time to Optimality (TO) of XPR and XPR+FJ for the MIPLIB 2017 benchmark set.
We at FICO congratulate Bjørnar and Giorgio on winning the 2024 FICO Xpress Best Paper Award. Amidst numerous strong contenders, their remarkable research stood out prominently. The Award jury was impressed by its originality and practical relevance. The awarded paper significantly contributed to the development of MIP technology and showed remarkable results in challenging instances.
Like many other research teams worldwide, the authors are members of our Academic Partner Program. Join our FICO Xpress Optimization Community and learn about our free community licenses for everyone and our fully-fledged free licenses for all academics. The call for the 2025 edition of the FICO Xpress Best Paper Award is out now: Consider submitting your Xpress-related research paper!
Figure 4: Both winners with the award at their home research organization SINTEF
Updated 2 years ago
Version 3.0