Mathematical optimization is a great way to find solutions to a problem that we can describe as a decision between various alternatives constrained by certain conditions and ranked by some function of how good each of these alternatives is. The beauty of mathematical optimization, in contrast with many other methodologies, is that it not only provides us with a good solution (in terms of the ranking function) but also with the best possible solution. Furthermore, it provides us with proof of why no better solution for the instance at hand can exist. Isn't that wonderful: "This is the solution, and here is why it is optimal." That's the promise of mathematical optimization.
At least, that is what the textbooks say. In practice, however, we often encounter huge and complex problems, highly symmetric or numerically challenging problems, and we are tasked with finding solutions for them in a short amount of planning time. So, while in theory, a MIP solver would provide us with a proven optimal solution, in practice, it often hits the time limit we imposed, and the solver has only explored a tiny fraction of the search space.
A small optimization gap is often the goal when solving MIPs
In such cases, we are typically willing to sacrifice the proof of optimality and hope for a good, but potentially suboptimal, solution, which is maybe 1% or 2% away from some bound on the optimal value.
Again, the beauty of mathematical optimization is that it provides us with such a measure of solution quality.This is where primal heuristics kick in. These auxiliary procedures try to find high-quality solutions in a short amount of time, typically interleaved with or in parallel to the actual MIP search. The amount by which heuristics are applied in a MIP solver is carefully calculated to not to slow down the primary goal, which is the optimality-seeking search, too much. But what if we already know we will likely not reach optimality?
For such situations, we introduced the heuristic emphasis mode in the most recent Xpress solver release (8.12). It comes in the form of a single catch-all control, called HEUREMPHASIS, which allows changing the focus of the solver from solving to optimality to getting high-quality solutions as quickly as possible. Setting to HEUREMPHASIS=1 will change much of the solver tuning behind the scenes to achieve that goal. It will activate additional non-default heuristics, increase the work limits of others or trigger them more frequently. It will also apply some changes to cutting and branching, assuming we are dealing with a challenging problem.
Searching for a MIP solution can be like looking for a needle in a haystack.
And HEUREMPHASIS is your metal detector!
For the optimization enthusiasts: We tuned HEUREMPHASIS=1 to minimize the average Primal-Dual Integral (or short PDI), a metric used to assess the heuristic performance of MIP solvers. The PDI is defined as the area under the gap curve over time, up to a fixed time limit. It measures how quickly the primal-dual gap is closed. Hence: The smaller the PDI, the better. We'll elaborate on this measure in a future blog post.
When using our new heuristic emphasis mode on our internal benchmarks, the PDI reduces by 25% on average for instances that cannot be solved within a time limit of one hour. For models with a particularly large PDI, i.e, problems for which finding any good solution is a challenge, the improvement was 83% on average. Also, other measures for solution quality improved. We observe a 28% improvement of the MIP gap at termination, the time to the first solution improves by 15%, and, finally, the time to achieve a gap value of 0.5 decreases by 8.5%.
Finally, note that setting HEUREMPHASIS=0 will completely deactivate heuristics, and HEUREMPHASIS=2 enables a super-aggressive heuristic mode, which works well for some problems, but deteriorates the PDI on average. Thus, it would be best if you only tried this as a last resort.
Finally, note that it might be helpful for some applications to change HEUREMPHASIS during optimization. For example, you might start a run with default settings and, after 80% of the intended run time, switch to our heuristic emphasis mode to improve the incumbent solutionAlternatively, your application might need to produce high-quality solutions quickly, and can then spend the rest of the time proving optimality. These and many other interactions can be applied within the rich callbacks framework supported by the Xpress Optimizer that allows you to interact with the MIP solution process.
Find out which usage fits your needs best and start playing with the latest Xpress release and its features today. Visit ourOptimization Community, download a free community license or watch this video (external) for more details on what's new in Xpress 8.12.
At least, that is what the textbooks say. In practice, however, we often encounter huge and complex problems, highly symmetric or numerically challenging problems, and we are tasked with finding solutions for them in a short amount of planning time. So, while in theory, a MIP solver would provide us with a proven optimal solution, in practice, it often hits the time limit we imposed, and the solver has only explored a tiny fraction of the search space.
A small optimization gap is often the goal when solving MIPs
In such cases, we are typically willing to sacrifice the proof of optimality and hope for a good, but potentially suboptimal, solution, which is maybe 1% or 2% away from some bound on the optimal value.
Again, the beauty of mathematical optimization is that it provides us with such a measure of solution quality.This is where primal heuristics kick in. These auxiliary procedures try to find high-quality solutions in a short amount of time, typically interleaved with or in parallel to the actual MIP search. The amount by which heuristics are applied in a MIP solver is carefully calculated to not to slow down the primary goal, which is the optimality-seeking search, too much. But what if we already know we will likely not reach optimality?
For such situations, we introduced the heuristic emphasis mode in the most recent Xpress solver release (8.12). It comes in the form of a single catch-all control, called HEUREMPHASIS, which allows changing the focus of the solver from solving to optimality to getting high-quality solutions as quickly as possible. Setting to HEUREMPHASIS=1 will change much of the solver tuning behind the scenes to achieve that goal. It will activate additional non-default heuristics, increase the work limits of others or trigger them more frequently. It will also apply some changes to cutting and branching, assuming we are dealing with a challenging problem.
Searching for a MIP solution can be like looking for a needle in a haystack.
And HEUREMPHASIS is your metal detector!
For the optimization enthusiasts: We tuned HEUREMPHASIS=1 to minimize the average Primal-Dual Integral (or short PDI), a metric used to assess the heuristic performance of MIP solvers. The PDI is defined as the area under the gap curve over time, up to a fixed time limit. It measures how quickly the primal-dual gap is closed. Hence: The smaller the PDI, the better. We'll elaborate on this measure in a future blog post.
When using our new heuristic emphasis mode on our internal benchmarks, the PDI reduces by 25% on average for instances that cannot be solved within a time limit of one hour. For models with a particularly large PDI, i.e, problems for which finding any good solution is a challenge, the improvement was 83% on average. Also, other measures for solution quality improved. We observe a 28% improvement of the MIP gap at termination, the time to the first solution improves by 15%, and, finally, the time to achieve a gap value of 0.5 decreases by 8.5%.
Finally, note that setting HEUREMPHASIS=0 will completely deactivate heuristics, and HEUREMPHASIS=2 enables a super-aggressive heuristic mode, which works well for some problems, but deteriorates the PDI on average. Thus, it would be best if you only tried this as a last resort.
Finally, note that it might be helpful for some applications to change HEUREMPHASIS during optimization. For example, you might start a run with default settings and, after 80% of the intended run time, switch to our heuristic emphasis mode to improve the incumbent solutionAlternatively, your application might need to produce high-quality solutions quickly, and can then spend the rest of the time proving optimality. These and many other interactions can be applied within the rich callbacks framework supported by the Xpress Optimizer that allows you to interact with the MIP solution process.
Find out which usage fits your needs best and start playing with the latest Xpress release and its features today. Visit ourOptimization Community, download a free community license or watch this video (external) for more details on what's new in Xpress 8.12.
Updated 5 years ago
Version 3.0