HiGHS (via JuMP) decides MIP solution to be infeasible

Specific Domains Optimization (Mathematical)
1

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_i and 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_i for which the previous value was false, 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.
1 Like