Wow, already the fifth blog in this series…What is left to tell about numerics? Quite a bit, actually!
In my previous blogs, we have mainly concentrated on tiny (or not so tiny) violations in the feasibility of linear constraints and optimality conditions. In case you missed my previous posts, we have discussed:
However, there is another place where a MIP solver can sneak in minor violations that we have not yet discussed: The integrality conditions.
As with many other decisions in numerical software, the judgment of whether a particular value should be considered integral or not is subject to a threshold. For the Xpress Optimizer, this is MIPTOL, which is set to 5e-6 by default. This threshold implies that, e.g., all values between 41.999995 and 42.000005 will be treated as if they were integral, given that they are at most 0.000005 away from an integer value, namely 42.
Figure 2.
In my previous blogs, we have mainly concentrated on tiny (or not so tiny) violations in the feasibility of linear constraints and optimality conditions. In case you missed my previous posts, we have discussed:
- Where such inaccuracies come from and why some of them are unavoidable (to a certain extent)
- How we can recognize whether a model is prone to numeric errors
- How we can avoid many inaccuracies by automatically learned scaling operations
- How we can fix the remaining inaccuracies a posteriori by a refinement procedure
However, there is another place where a MIP solver can sneak in minor violations that we have not yet discussed: The integrality conditions.
As with many other decisions in numerical software, the judgment of whether a particular value should be considered integral or not is subject to a threshold. For the Xpress Optimizer, this is MIPTOL, which is set to 5e-6 by default. This threshold implies that, e.g., all values between 41.999995 and 42.000005 will be treated as if they were integral, given that they are at most 0.000005 away from an integer value, namely 42.
Figure 1.
Take a look at Figure 1 and judge for yourself. When zooming in on what seems to be an integer vertex of the polyhedron, should this point be considered a feasible solution (because the vertex should have been integer) or not (because the point is outside the polyhedron)?
You might wonder where such slightly off-integer solution values for integer variables might come from in the first place. Of course, when branching on integer variables, the solver will fix them to precise integer values. However, when an unfixed variable happens to be (almost) integer in an LP solution, the value might be slightly off. After all, the LP solver is agnostic to integrality information; the solution value is the result of resolving a system of equations that might involve values that had to be truncated due to floating-point representation.
In most situations, this is just fine, and the values can be safely rounded to an integer value afterward. But in some extreme cases, moving a variable by a tiny bit might introduce an infeasibility at another place. Consider the following example.
You might wonder where such slightly off-integer solution values for integer variables might come from in the first place. Of course, when branching on integer variables, the solver will fix them to precise integer values. However, when an unfixed variable happens to be (almost) integer in an LP solution, the value might be slightly off. After all, the LP solver is agnostic to integrality information; the solution value is the result of resolving a system of equations that might involve values that had to be truncated due to floating-point representation.
In most situations, this is just fine, and the values can be safely rounded to an integer value afterward. But in some extreme cases, moving a variable by a tiny bit might introduce an infeasibility at another place. Consider the following example.
Figure 2.
In Figure 2, x is a continuous variable, and b is a binary variable. Both problems are mathematically equivalent. They only differ in the second row being multiplied by a constant factor.
Let’s consider a few potential solutions for this problem:
In this particular situation, one would probably prefer to get the (x = 1, b = 1) solution. But what if the minimization was made over b and not over x? Here, it might already depend on the situation, whether a user is willing to accept some violations or whether a solution with precise integer values is preferred.
When precise integer solutions matter, the FICO Xpress Optimizer offers a non-default feature called “MIP solution refinement.” It performs various steps to eliminate violations in the integrality conditions, thereby guaranteeing that the Optimizer solutions have truly integer values and are still feasible (within FEASTOL tolerances) when integer variables are fixed.
Note that you can use our iterative refinement procedure to achieve reductions in constraint violation, see this blog. Both strategies are orthogonal to each other and can be seamlessly applied together.
Figure 3: Stopping an error propagation.
Let’s consider a few potential solutions for this problem:
- (x = 1, b = 0) is precisely integral. It is feasible w.r.t. numerical tolerances in the scaled problem since it violates the second constraint only by 10-6, which happens to be the default tolerance (FEASTOL) that is allowed for constraint violations. However, it is infeasible in the original problem since the second constraint is violated by 1.
- (x = 1, b = 10-6) is integral within tolerances. It is feasible in both, the original and the scaled problem. However, if you fix the binary variable to a value of exactly 0 in the original problem and reoptimize, the solver will find it to be infeasible.
- (x = 1, b = 1) is precisely integer and truly feasible for both problems.
In this particular situation, one would probably prefer to get the (x = 1, b = 1) solution. But what if the minimization was made over b and not over x? Here, it might already depend on the situation, whether a user is willing to accept some violations or whether a solution with precise integer values is preferred.
When precise integer solutions matter, the FICO Xpress Optimizer offers a non-default feature called “MIP solution refinement.” It performs various steps to eliminate violations in the integrality conditions, thereby guaranteeing that the Optimizer solutions have truly integer values and are still feasible (within FEASTOL tolerances) when integer variables are fixed.
Note that you can use our iterative refinement procedure to achieve reductions in constraint violation, see this blog. Both strategies are orthogonal to each other and can be seamlessly applied together.
Figure 3: Stopping an error propagation.
Situations where precise integrality matter include multi-level optimization and rolling horizon approaches. In multi-level optimization approaches, one considers nested optimization problems where each level has coefficients on a different order of magnitude. Slight errors on one level might propagate to an infeasibility in another level.
In rolling horizon approaches, one solves series of optimization problems (all on the same order of magnitude). The solution of one optimization problem is the input for the following problem. In unfortunate cases, errors might again propagate and amplify. In particular, one might fall into the trap that we saw for the (x = 1, b = 10-6) solution above. Rounding and fixing a solution might lead to unexpected infeasibilities in the aftermath.
If you experience such situations, consider setting bit 9 of the REFINEOPS control. It is off by default because, just like other refinement procedures, it takes additional computation time. Even though in our experiments, it only slowed down the solver by less than 10% on average, it was the problems that needed MIP refinement the most, which also experienced the largest slowdowns. In any case, this procedure generates solutions that are truly integral in the integer values. If necessary, the Optimizer can be not only close enough but spot on!
Interested in staying up to date with this type of content? Make sure to subscribe to our Optimization blog to be notified of new blog posts.
In rolling horizon approaches, one solves series of optimization problems (all on the same order of magnitude). The solution of one optimization problem is the input for the following problem. In unfortunate cases, errors might again propagate and amplify. In particular, one might fall into the trap that we saw for the (x = 1, b = 10-6) solution above. Rounding and fixing a solution might lead to unexpected infeasibilities in the aftermath.
If you experience such situations, consider setting bit 9 of the REFINEOPS control. It is off by default because, just like other refinement procedures, it takes additional computation time. Even though in our experiments, it only slowed down the solver by less than 10% on average, it was the problems that needed MIP refinement the most, which also experienced the largest slowdowns. In any case, this procedure generates solutions that are truly integral in the integer values. If necessary, the Optimizer can be not only close enough but spot on!
Interested in staying up to date with this type of content? Make sure to subscribe to our Optimization blog to be notified of new blog posts.
Updated 5 years ago
Version 3.0