As part of an optimisation-based control algorithm I solve a series of equally structured problems that only differ by the numerical values. For some “random” instances, I get output such as the following:
MIP has 7 rows; 13 cols; 28 nonzeros; 12 integer variables (12 binary)
Coefficient ranges:
Matrix [1e+00, 5e+01]
Cost [9e-01, 2e+00]
Bound [1e+00, 1e+00]
RHS [1e+00, 3e+01]
Presolving model
3 rows, 9 cols, 20 nonzeros 0s
3 rows, 9 cols, 20 nonzeros 0s
Presolve reductions: rows 3(-4); columns 9(-4); nonzeros 20(-8)
Solving MIP model with:
3 rows
9 cols (8 binary, 0 integer, 0 implied int., 1 continuous, 0 domain fixed)
20 nonzeros
Src: B => Branching; C => Central rounding; F => Feasibility pump; H => Heuristic;
I => Shifting; J => Feasibility jump; L => Sub-MIP; P => Empty MIP; R => Randomized rounding;
S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution; Y => HiGHS solution;
Z => ZI Round; l => Trivial lower; p => Trivial point; u => Trivial upper; z => Trivial zero
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
J 0 0 0 0.00% -inf 5.319081761 Large 0 0 0 0 0.0s
R 0 0 0 0.00% 0 0.5190817611 100.00% 0 0 0 3 0.0s
87.5% inactive integer columns, restarting
0 0 0 0.00% 0.5190807611 0.5190807611 0.00% 0 3 0 3 0.0s
Solving report
Status Optimal
Primal bound 0.519080761099
Dual bound 0.519080761099
Gap 0% (tolerance: 0.01%)
P-D integral 0.00566762785555
Solution status feasible
0.519080761099 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.03
Max sub-MIP depth 0
Nodes 0
Repair LPs 0
LP iterations 3
0 (strong br.)
0 (separation)
0 (heuristics)
ERROR: MIP solver claims optimality, but with num/max/sum primal(1/1e-06/1e-06) infeasibilities
ERROR: Setting model status to Solve error
The last two lines (starting with ERROR) irritate me. HiGHS’s MIP solver solves the problem successfully (optimal and feasible), but then after the fact HiGHS (which “entity”?) judges that the solution actually is NOT feasible?
The thing is that no solution is available in that case, so my algorithm fails.
- I read some stuff on the internet about related issues, turned “off”
presolve. Helped in some cases, but the problem still occurs randomly. - Then I also deactivated restarts (
mip_allow_restart = false). This helped in many cases. But then I still hit the same problem again. - Then I set the integer variables to the starting value of the previous iteration on the control problem. With all three measures, I now, on the test suite, don’t get the issue anymore. But I am concerned that the actual, underlying problem is not solved and for some combination of numerical values I accidentally do not test, the problem will still occur.
I did read on feasibility vs. optimality vs. tolerances. But that specific problem with the “after-the-fact infeasibility detection” is not mentioned anywhere. A also cannot find the error-text string anywhere in the HiGHS codebase. So I’m a bit lost right now…
Thanks for any help in advance!
Details on problem characteristic:
- There is some switched actuators that may take several discrete values.
- I model each setting as a binary variable
z_iand add a constraint that they sum to 1. - There is switching costs, so I add a switching penalty to the objective, which is the sum of all
z_ifor which the previous value wasfalse, times a penalty factor (that is adapted over time, individually for each actuator). - The actual objective is the absolute value of a tracking error (auxiliary variable to model the absolute value). The tracking error is a weighted sum of all actuator’s binary variables (the weights being the output of the respective actuator state), minus the target value.
. Also, I’ll probably keep both SCIP and HiGHS as solvers, one backing up the other.
.
