DominguezRios assumes exact tolerances

[odow]

x-ref #119 (comment)

I don't really understand the algorithm, but I followed a few leads to:

https://github.com/MiguelAngelDominguezRios/boxMO/blob/f316f0301ffea3b694de17ae076a0cd091a2ac26/main_boxes.cpp#L202-L204

Their tests all used

        status = CPXsetdblparam(*env, CPX_PARAM_EPGAP, 0.0); //Default 1e-04. Value between 0 and 1. Sets a relative tolerance on the gap between the best integer objective and the objective of the best node remaining
	status = CPXsetdblparam(*env, CPX_PARAM_EPAGAP, 0.0); //Default 1e-06
	status = CPXsetdblparam(*env, CPX_PARAM_EPINT, 0.0); //Default 1e-05. CPLEX tolerance for integer variables

which is one way to avoid needing to deal with tolerances in the algorithm.

We probably need to make a few changes.

[odow]

This might actually have been an issue in HiGHS: #121

It works with presolve=off.

I get sub solves like this:

MIP  has 3 rows; 51 cols; 152 nonzeros; 50 integer variables (50 binary)
Coefficient ranges:
  Matrix [1e+00, 3e+03]
  Cost   [6e-01, 2e+00]
  Bound  [1e+00, 1e+00]
  RHS    [2e+02, 2e+04]
Presolving model
3 rows, 51 cols, 152 nonzeros  0s
3 rows, 51 cols, 152 nonzeros  0s

Solving MIP model with:
   3 rows
   51 cols (50 binary, 0 integer, 0 implied int., 1 continuous, 0 domain fixed)
   152 nonzeros

Src: B => Branching; C => Central rounding; F => Feasibility pump; J => Feasibility jump;
     H => Heuristic; L => Sub-MIP; P => Empty MIP; R => Randomized rounding; Z => ZI Round;
     I => Shifting; S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution;
     z => Trivial zero; l => Trivial lower; u => Trivial upper; p => Trivial point

        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            11769.649487       Large        0      0      0         0     0.0s
 R       0       0         0   0.00%   2036.755868     3752.964094       45.73%        0      0      0         5     0.0s
 C       0       0         0   0.00%   2116.384921     3323.444309       36.32%       53      5      0        18     0.0s
 L       0       0         0   0.00%   2116.384921     2349.400912        9.92%       53      5      0        18     0.1s

62.0% inactive integer columns, restarting
Model after restart has 3 rows, 20 cols (19 bin., 0 int., 0 impl., 1 cont., 0 dom.fix.), and 59 nonzeros

         0       0         0   0.00%   2125.053791     2349.400912        9.55%        4      0      0       275     0.1s
         0       0         0   0.00%   2125.053791     2349.400912        9.55%        4      3      1       282     0.1s
 L       0       0         0   0.00%   2153.509695     2217.386907        2.88%      386     24      1       359     0.2s

26.3% inactive integer columns, restarting
Model after restart has 3 rows, 15 cols (14 bin., 0 int., 0 impl., 1 cont., 0 dom.fix.), and 44 nonzeros

         0       0         0   0.00%   2153.644474     2217.386907        2.87%        9      0      0       452     0.2s
         0       0         0   0.00%   2153.644474     2217.386907        2.87%        9      9      2       464     0.2s
        23       0        12 100.00%   2217.386907     2217.386907        0.00%      427      9    108       991     0.3s

Solving report
  Status            Optimal
  Primal bound      2217.38690667
  Dual bound        2217.38690667
  Gap               0% (tolerance: 0.01%)
  P-D integral      0.0603689083898
  Solution status   feasible
                    2217.38690667 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            0.35 (total)
                    0.00 (presolve)
                    0.00 (solve)
                    0.00 (postsolve)
  Max sub-MIP depth 3
  Nodes             23
  Repair LPs        0 (0 feasible; 0 iterations)
  LP iterations     991 (total)
                    258 (strong br.)
                    106 (separation)
                    495 (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
ERROR: AssertionError: _is_scalar_status_optimal(model)

So we're violating an unscaled feasibility tolerance.

[odow]

Closing because our conclusion is that this is a HiGHS issue: #119 (comment), not a DominguezRios issue