[bazel] Highs 1.7.0 math_opt tests failed

[Mizux]

This is a following of HiGhs integration

• 3116

What version of OR-Tools and what language are you using? Version: main (and v99bugfix aka incoming v9.10) Language: C++

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi) HiGHs test from math_opt/solvers

What operating system (Linux, Windows, ...) and version? Linux/MacOS

What did you do?

git checkout main
bazel test -c opt ortools/math_opt/solvers:highs_solver_test

note: same with v99bugfix branch

What did you expect to see all tests pass

What did you see instead?

bazel test -c opt ortools/math_opt/solvers:highs_solver_test
...
ortools/math_opt/solver_tests/status_tests.cc:112: Failure
Value of: _status_or_value2.ok()
  Actual: false
Expected: true
INTERNAL: primal feasibility status is not FEASIBILITY_STATUS_FEASIBLE, but primal feasible solution is returned.

[  FAILED  ] HighsStatusTest/StatusTest.PrimalAndDualInfeasible/1, where GetParam() = { solver_type: highs, parameters: lp_algorithm: LP_ALGORITHM_BARRIER presolve: EMPHASIS_OFF gscip { } gurobi { } glop { } cp_sat { } pdlp { } glpk { } highs { }, disallow_primal_or_dual_infeasible: false, supports_iteration_limit: true, use_integer_variables: false, supports_node_limit: false, support_interrupter: false, supports_one_thread: false } (0 ms)
...
INFO: Found 1 test target...
Target //ortools/math_opt/solvers:highs_solver_test up-to-date:
  bazel-bin/ortools/math_opt/solvers/highs_solver_test
INFO: Elapsed time: 52.607s, Critical Path: 41.15s
INFO: 181 processes: 185 linux-sandbox.
INFO: Build completed, 1 test FAILED, 181 total actions
//ortools/math_opt/solvers:highs_solver_test                             **FAILED in 12 out of 18 in 10.4s**
  Stats over 18 runs: max = 10.4s, min = 0.2s, avg = 2.9s, dev = 2.7s

DevNote: HiGHs 1.4.1 seems to pass... aka this patch

diff --git a/WORKSPACE b/WORKSPACE
index 0fd7395d25..6b53b2f24b 100644
--- a/WORKSPACE
+++ b/WORKSPACE
@@ -156,7 +156,7 @@ cc_library(

 git_repository(
     name = "highs",
-    branch = "v1.7.0",
+    branch = "v1.4.1",
     remote = "https://github.com/ERGO-Code/HiGHS.git",
 )

bazel test -c opt ortools/math_opt/solvers:highs_solver_test`
 ...
INFO: Build completed successfully, 181 total actions
//ortools/math_opt/solvers:highs_solver_test                             PASSED in 10.7s
  Stats over 10 runs: max = 10.7s, min = 0.2s, avg = 2.9s, dev = 3.2s

[Mizux]

Few more tests:

HiGHs version	//ortools/math_opt/solvers:highs_solver_test
1.4.1	PASSED
1.4.2	PASSED
1.5.1	FAILED
1.5.3	FAILED
1.7.0	FAILED

So it seems the move from 1.4.2 to 1.5.1 failed, will try to perform a git bissect from 1.4.2 to 1.5.1...

[Mizux]

this is based on github "historic" view: https://github.com/ERGO-Code/HiGHS/commits/v1.5.1/?after=93f1876e453eeec2d16e2a0c95874d0ef12c5b23+305

inside the WORKSPACE:

git_repository(
    name = "highs",
    #branch = "master",
    #tag = "v1.7.0", # FAILED
    #tag = "v1.5.3", # FAILED
    #tag = "v1.5.1", # FAILED
    #commit = "387fcf926f459ea480053f5b0f4f2aef59a9586c", # 2023-01-03 FAILED
    #commit = "488059f92f0df752f8a411be6bd30b2141d0552b", # 2022-12-24 FAILED
    #commit = "4a22da667e90a38373baf04bb259f8a2332a9d3f", # 2022-12-22 FAILED
    #commit = "6f28a305366f5f53438f9a9e72c025fdf2c550f3", # 2022-12-21 FAILED
    commit = "e0ed5b019109dc76fc6ffaf7962843cbf6de0961", # 2022-12-21 FAILED
    #commit = "61b7dccf1ae8b9f46edf54ad1ca2cb416a273e9c", # 2022-12-17 OK
    #commit = "fd49112140bf8c2ff79312e91423b798be6d6276", # 2022-12-17 OK
    #commit = "4ebb25d4b1e21addaf48fb0e4c8dd0bca04efff6", # 2022-12-15 OK
    #tag = "v1.4.2", # PASSED
    #tag = "v1.4.1", # PASSED
    remote = "https://github.com/ERGO-Code/HiGHS.git",
)

so the commit seems to be https://github.com/ERGO-Code/HiGHS/commit/e0ed5b019109dc76fc6ffaf7962843cbf6de0961

[Mizux]

Digging the gitk of HiGHs repo and following parent(s)...

flowchart TD;
T_7[1.7.0 FAILED] -.-> T_5[1.5.1 FAILED];
T_5 -.-> A[e0ed5 FAILED];
A --> B[33cc544 FAILED];
B --> C[cae9617 FAILED];
C --> D1[05dfb85 PASSED];
C --> D2[7a94304 FAILED];
D2--> E1[316c825 FAILED];
D2 --> E2[2629907 PASSED];
E1 --> F1[daed8b7 FAILED];
E1 --> F2[5acb9c6 FAILED];
F2 --> G1[62763d7 PASSED];
F2 --> F1;
F1 --> H1[bc7f2a2 PASSED];
F1 --> H2[**e9f424f FAILED**];
H2 --> I[e5ea838 PASSED];
I --> J[abff61b PASSED];
J --> K[3549dda PASSED];
K --> H1;
H1 -.-> D[1.4.2 PASSED];

note: we can already see that the github history and gitk graph didn't display the same story...

https://github.com/ERGO-Code/HiGHS/commit/e9f424f

[Mizux]

git diff HEAD~1
diff --git a/WORKSPACE b/WORKSPACE
index 0fd7395d25..ee02668f49 100644
--- a/WORKSPACE
+++ b/WORKSPACE
@@ -156,7 +156,43 @@ cc_library(

 git_repository(
     name = "highs",
-    branch = "v1.7.0",
+    #branch = "master",
+    #tag = "v1.7.0", # FAILED
+    #tag = "v1.5.3", # FAILED
+    #tag = "v1.5.1", # FAILED
+    #commit = "387fcf926f459ea480053f5b0f4f2aef59a9586c", # 2023-01-03 FAILED
+    #commit = "488059f92f0df752f8a411be6bd30b2141d0552b", # 2022-12-24 FAILED
+    #commit = "4a22da667e90a38373baf04bb259f8a2332a9d3f", # 2022-12-22 FAILED
+    #commit = "6f28a305366f5f53438f9a9e72c025fdf2c550f3", # 2022-12-21 FAILED
+    #commit = "e0ed5b019109dc76fc6ffaf7962843cbf6de0961", # 2022-12-21 FAILED
+    #commit = "61b7dccf1ae8b9f46edf54ad1ca2cb416a273e9c", # 2022-12-17 OK
+    #commit = "fd49112140bf8c2ff79312e91423b798be6d6276", # 2022-12-17 OK
+    #commit = "4ebb25d4b1e21addaf48fb0e4c8dd0bca04efff6", # 2022-12-15 OK
+    #tag = "v1.4.2", # PASSED
+    #tag = "v1.4.1", # PASSED
+
+    # try to follow parent historic from "e0ed5b019109dc76fc6ffaf7962843cbf6de0961"
+    #commit = "cae9617de4635aeb3546bc9791831c5e6103132e", # FAILED
+    #commit = "7a943048b9d0e65cad80de5159eb43b6ff446b1e", # FAILED prt cae
+    #commit = "05dfb8553d2a98a6db04f6686e56c8958185989b", # PASSED prt cae
+
+    #commit = "316c825f9433de9bf8c73e1baa2a7734d77bd4af", # FAILED prt 7a94
+    #commit = "262990724218f025edd5b106db78276e8bef90aa", # PASSED prt 7a94
+
+    #commit = "daed8b7ac47364f74c17cdd8eb11bfa94b4575ac", # FAILED prt 316
+    #commit = "5acb9c64e79d4c7c14c9db008bc1dc923d537ee5", # FAILED prt 316
+
+    #commit = "62763d711e98c6f065d79e22885ef9c9da475a78", # PASSED
+
+    #commit = "bc7f2a2ce8089153f0daddb5559eb1e19fbf73d9", # PASSED
+    commit = "e9f424f640de18fba71931a009a8423a0d9b9b54", # FAILED
+
+    #commit = "e5ea838483861867905fc8964442fe1fd176e85d", # PASSED
+    #commit = "abff61b5a33746c4c9b6b59b08bb1a0455b8b23c", # PASSED
+    #commit = "3549dda16a38dd0570e40c3872607c9cd733383c", # PASSED
+
+    #patches = ["highs.patch"],
+    #patch_args = ["-p1"],
     remote = "https://github.com/ERGO-Code/HiGHS.git",
 )

[rma350]

I am not optimistic that we will get HiGHs 1.7 working well if we are stuck on HiGHs 1.4 internally (we cannot move until SciPy moves)

The failing test is here:

https://github.com/google/or-tools/blob/main/ortools/math_opt/solver_tests/status_tests.cc#L112

In this test, we solve an LP that is both primal or dual infeasible. The SolveResultProto returned fails at validation time because we correctly claim the primal problem is not feasible, but then incorrectly return a primal solution that we claim is feasible (the problem has no primal feasible solutions).

I would guess that the issue is probably here:

https://github.com/google/or-tools/blob/main/ortools/math_opt/solvers/highs_solver.cc#L725

in that the value of highs_solution.is_valid has changed between 1.4 and 1.7 for this test, but I would need to debug/run the code to really see what is going on.

There is no documentation on this type:

https://github.com/ERGO-Code/HiGHS/blob/master/src/lp_data/HStruct.h#L30

so it is not easy to predict how it will work beyond running the code. Even if the primal problem is infeasible, you can still return a feasible solution and have it be valid.

Big picture, I would recommend using the same version of HiGHs we use internally. MathOpt has contracts that are programatically enforced, but the underlying solvers generally do not (have contracts or enforce them). When you upgrade the solvers, some of the tests break always end up breaking and it is very time consuming to deal with this issues.

If you want to discuss further, we should move this to an internal list a very few people will see this discussion out here.