Encountered ERROR: HighsSearch::selectBranchingCandidate

[Thell]

First time I've seen this. I hadn't changed the logical model from prior runs, that didn't encounter this, with the same parameters. The final solution still looks to be valid.

I did add to the input data between the previous runs and this one.

      3020      82       651  66.21%   423991228.5359  402736871.5479     5.28%     6161    912   7613    542737   389.9s
ERROR:   HighsSearch::selectBranchingCandidate Error fracval = 0.444444 <= 1 = 1 + 1e-06 = localdom.col_lower_[col] + mipsolver.mipdata_->feastol: Residual -0.555557
ERROR:   HighsSearch::selectBranchingCandidate Error fracval = 0.666667 <= 1 = 1 + 1e-06 = localdom.col_lower_[col] + mipsolver.mipdata_->feastol: Residual -0.333334
ERROR:   HighsSearch::selectBranchingCandidate Error fracval = 0.444444 <= 1 = 1 + 1e-06 = localdom.col_lower_[col] + mipsolver.mipdata_->feastol: Residual -0.555557
ERROR:   HighsSearch::selectBranchingCandidate Error fracval = 0.75 <= 1 = 1 + 1e-06 = localdom.col_lower_[col] + mipsolver.mipdata_->feastol: Residual -0.250001
ERROR:   HighsSearch::selectBranchingCandidate Error fracval = 0.444444 <= 1 = 1 + 1e-06 = localdom.col_lower_[col] + mipsolver.mipdata_->feastol: Residual -0.555557
ERROR:   HighsSearch::selectBranchingCandidate Error fracval = 0.466667 <= 1 = 1 + 1e-06 = localdom.col_lower_[col] + mipsolver.mipdata_->feastol: Residual -0.533334
ERROR:   HighsSearch::selectBranchingCandidate Error fracval = 0.444444 <= 1 = 1 + 1e-06 = localdom.col_lower_[col] + mipsolver.mipdata_->feastol: Residual -0.555557
ERROR:   HighsSearch::selectBranchingCandidate Error fracval = 0.285714 <= 1 = 1 + 1e-06 = localdom.col_lower_[col] + mipsolver.mipdata_->feastol: Residual -0.714287
ERROR:   HighsSearch::selectBranchingCandidate Error fracval = 0.243342 <= 1 = 1 + 1e-06 = localdom.col_lower_[col] + mipsolver.mipdata_->feastol: Residual -0.756659
ERROR:   HighsSearch::selectBranchingCandidate Error fracval = 0.75 <= 1 = 1 + 1e-06 = localdom.col_lower_[col] + mipsolver.mipdata_->feastol: Residual -0.250001
ERROR:   HighsSearch::selectBranchingCandidate Error fracval = 0.883793 <= 1 = 1 + 1e-06 = localdom.col_lower_[col] + mipsolver.mipdata_->feastol: Residual -0.116208
ERROR:   HighsSearch::selectBranchingCandidate Error fracval = 0.677492 <= 1 = 1 + 1e-06 = localdom.col_lower_[col] + mipsolver.mipdata_->feastol: Residual -0.322509
ERROR:   HighsSearch::selectBranchingCandidate Error fracval = 0.849921 <= 1 = 1 + 1e-06 = localdom.col_lower_[col] + mipsolver.mipdata_->feastol: Residual -0.15008
ERROR:   HighsSearch::selectBranchingCandidate Error fracval = 0.713725 <= 1 = 1 + 1e-06 = localdom.col_lower_[col] + mipsolver.mipdata_->feastol: Residual -0.286276
      3104      83       689  66.21%   423991228.5359  402736871.5479     5.28%     6197    912   7908    549097   395.1s

Solving report
  Status            Optimal
  Primal bound      402736871.548
  Dual bound        420837532.793
  Gap               4.49% (tolerance: 5%)
  Solution status   feasible
                    402736871.548 (objective)
                    0 (bound viol.)
                    8.881784197e-16 (int. viol.)
                    0 (row viol.)
  Timing            609.12 (total)
                    0.54 (presolve)
                    0.00 (postsolve)
  Nodes             5255
  LP iterations     829784 (total)
                    310962 (strong br.)
                    8663 (separation)
                    91836 (heuristics)

[jajhall]

Hmm... that does look a bit alarming.

Are you able to reproduce the behaviour from a .lp or .mps file?

[Thell]

@jajhall Yes, I am able to reproduce using the pulp generated .mps. I am not able to reproduce using the pulp generated .lp. I'm also unsure of how to compare the two without writing up something to load the .mps and write it out as an .lp via HiGHS api to diff; which I am not setup to do right now.

The .mps is 12+MB... MaximizeEmpireValue-pulp.mps.txt MaximizeEmpireValue-pulp.lp.txt

The pertinent options file is

parallel=on
threads=16
mip_rel_gap=0.05
mip_feasibility_tolerance=1e-06
primal_feasibility_tolerance=1e-06

[jajhall]

No problem, I can work with.mps

[Thell]

Update... the error does reproduce via .lp, but less so and much later in the processing...

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work
     Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

     15009    2167       995   8.27%   413843378.7989  388968301.1342     6.40%     2638   1314   5536     2387k  1245.9s
     15112    2231      1011   8.27%   413843378.7989  388968301.1342     6.40%     2701   1354   5509     2412k  1256.2s
ERROR:   HighsSearch::selectBranchingCandidate Error fracval = 0.5 <= 1 = 1 + 1e-06 = localdom.col_lower_[col] + mipsolver.mipdata_->feastol: Residual -0.500001
ERROR:   HighsSearch::selectBranchingCandidate Error fracval = 0.8 <= 1 = 1 + 1e-06 = localdom.col_lower_[col] + mipsolver.mipdata_->feastol: Residual -0.200001
ERROR:   HighsSearch::selectBranchingCandidate Error fracval = 0.5 <= 1 = 1 + 1e-06 = localdom.col_lower_[col] + mipsolver.mipdata_->feastol: Residual -0.500001
     15258    2274      1049   8.27%   413843378.7989  388968301.1342     6.40%     2733   1354   5275     2423k  1261.4s
     15378    2324      1077   8.32%   413843378.7989  388968301.1342     6.40%     2766   1376   4953     2436k  1267.4s

But now I'm curious if they will both reach the same optimum if I let them run to completion, lol.

[Thell]

I guess it's to be expected that the result would be different considering there must be a difference between the problem presented by the .mps and the problem presented by the .lp.

I don't think that part would be a HiGHS issue since Pulp would be responsible for how it writes out the problem, right? I really don't know enough about the difference in the file formats themselves to understand how their structure might influence HiGHS solving of the presented problem.

Result via .lp:

Solving report
  Status            Optimal
  Primal bound      403554485.325
  Dual bound        413843378.799
  Gap               2.55% (tolerance: 5%)
  Solution status   feasible
                    403554485.325 (objective)
                    0 (bound viol.)
                    1.0911271886e-12 (int. viol.)
                    0 (row viol.)
  Timing            1462.36 (total)
                    0.64 (presolve)
                    0.00 (postsolve)
  Nodes             18453
  LP iterations     2822747 (total)
                    886071 (strong br.)
                    71024 (separation)
                    222972 (heuristics)

Result via .mps:

Solving report
  Status            Optimal
  Primal bound      402736871.548
  Dual bound        420837532.793
  Gap               4.49% (tolerance: 5%)
  Solution status   feasible
                    402736871.548 (objective)
                    0 (bound viol.)
                    8.881784197e-16 (int. viol.)
                    0 (row viol.)
  Timing            600.73 (total)
                    0.50 (presolve)
                    0.00 (postsolve)
  Nodes             5255
  LP iterations     829784 (total)
                    310962 (strong br.)
                    8663 (separation)
                    91836 (heuristics)

[jajhall]

The two file formats will induce a reordering of the variables and constraints in the problem, and that will lead to the MIP solver behaving differently.

[jajhall]

Having looked in more detail, it's the nature of MIP that errors like this can happen, without preventing the correct solution from being found. I'll still try to identify what's wrong