Highs fails solving simple problem due to presolving issue

[rma350]

This issue was found internally at Google (by someone else), I am forwarding it. It is relatively minimal.

The problem was written using ortools (sorry, probably not best for you):

  math_opt::Model model;
  int upper_bound = 20;
  math_opt::Variable x0 = model.AddIntegerVariable(0, upper_bound);
  math_opt::Variable x1 = model.AddIntegerVariable(0, upper_bound);
  math_opt::Variable y0 = model.AddIntegerVariable(0, 1);
  math_opt::Variable y1 = model.AddIntegerVariable(0, 1);
  model.AddLinearConstraint(x0 == 1 + y0 * 20);
  model.AddLinearConstraint(x1 == x0 + y1 * 20);
  math_opt::SolveArguments args = {.parameters = {.enable_output = true}};
  const math_opt::SolveResult result =
      *math_opt::Solve(model, math_opt::SolverType::kHighs, args);

The error message is ERROR: MIP solver claims optimality, but with num/sum/max primal(1/1/1) infeasibilities

Note that if upper_bound=20, then y0=y1=0 so the only feasible solution is x0=x1=1. If upper_bound>20 then there are other feasible solutions.

Apparently the presolve is detecting this, but returning an infeasible solution (probably x0=x1=y0=y1=0)

Notes:

1. If upper_bound=21, it works.
2. If x1,y1 and the second constraint are deleted, it works (!!).
3. If x0,x1 are continuous variables, it works.

FULL OUTPUT:

Presolving model
0 rows, 0 cols, 0 nonzeros
0 rows, 0 cols, 0 nonzeros
Presolve: Optimal
WARNING: Untransformed solution with objective 0 is violated by 1 for the original model

Solving report
  Status            Optimal
  Primal bound      0
  Dual bound        0
  Gap               0% (tolerance: 0.01%)
  Solution status   infeasible
                    0 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    1 (row viol.)
  Timing            0.00 (total)
                    0.00 (presolve)
                    0.00 (postsolve)
  Nodes             0
  LP iterations     0 (total)
                    0 (strong br.)
                    0 (separation)
                    0 (heuristics)
ERROR:   MIP solver claims optimality, but with num/sum/max primal(1/1/1) infeasibilities

This was run with a slightly patched version of HiGHS 1.4.1 (Dec 9th, 2022). I attempted to run the same model using open source or-tools in python, but HiGHS is not in the precompiled binary yet AFAICT.

[jajhall]

Thanks for this. I'll try it out with the latest version of HiGHS, as there have been some MIP presolve bug fixes since v1.4.1

[jajhall]

I've reproduced this in v1.4.1, and it's a postsolve error.

It doesn't occur in v1.7.0 (or latest), probably due to a bug fix by @fwesselm

[rma350]

Thanks. Interestingly, now that HiGHs is bundled with the much bigger project scipy, we cannot upgrade HiGHS at will, we need to stay in sync with whatever version of HiGHs is being used by Google's current version of scipy.

https://opensource.google/documentation/reference/thirdparty/oneversion

We might have a little more flexibility in the open source project in supporting a more recent version.

[jajhall]

So,

• you can have an independent version of HiGHS if it's v1.4.1
• the latest version of SciPy is using HiGHS v1.4.1

I also thought that, at least internally, HiGHS is being used as part of OR-Tools

[rma350]

Internally, our scipy is also a bit behind head, so there will be a bit of lag for each step:

• you getting a SciPy to use a new version of HiGHs
• scipy + highs getting upgraded internally
• Or-tools cutting a new release using the newer version.

Sometimes, we have the open source project use a different version of a solver than internally (typically newer), but we generally try to avoid this if possible as it is hard for us to maintain.

Yes HiGHs has some internal use. Externally, I would not expect much use until you part of the precompiled binaries.

[jajhall]

OR-Tools is using HiGHS via SciPy?

This makes no sense to me

I thought it was being used directly @galabovaa

[rma350]

Sorry this is a little confusing, let me try to explain. We connect directly to the C++ API, we do not go through SciPy.

However, the vast majority of Google source code is in one giant repo. The rule of this repo is that there can only be one version of each third party dependency (one scipy, one highs, etc). There are pros and cons to this system that are well discussed in other places. Thus, we are forced to use the same version of HiGHs as Scipy, at least internally.

[jajhall]

Thanks, I read through

https://opensource.google/documentation/reference/thirdparty/oneversion

after your previous message, and it make sense now