Naked assert in latest branch

[Thell]

Near the end of the case HighsPresolveStatus::kUnboundedOrInfeasible: there is an assert I am hitting

https://github.com/ERGO-Code/HiGHS/blob/2da0f1cccf2801574630ff9fa5f7c044b2e9d124/src/lp_data/Highs.cpp#L1279

        setBasisValidity();
        assert(model_status_ == HighsModelStatus::kInfeasible ||
               model_status_ == HighsModelStatus::kUnbounded);
        return returnFromRun(return_status);

should this be wrapped in the kAllowDeveloperAssert flag instead of being direct? If not, how do I get around it? I saw an option objective_bound but even after setting it to the max possible cost I still hit that assert so I am guessing that option doesn't set the flag being checked for at the start of that case (options_.allow_unbounded_or_infeasible).

[Thell]

I was able to find more options by using HighsOptions.h and tried setting allow_unbounded_or_infeasible true but still hit the same assert and after perusing the code base a bit more I went ahead and tried setting presolve off and I was able to process that dataset to completion and validate the final results so at least I know my model isn't at fault.

Turning off presolve is obviously not what I want to do considering that I experience a 2.6x time to complete on a bunch of other datasets for which I already have timing data on (ie: from 3.9s to 10.7s and 5.2s to 13.9s and 2m19s to 5m52s) so having presolve is definitely desired.

I was thinking I could call using the simplex solver to test feasibility prior to fully solving but if I understand the block of code I am hitting the assert in that is exactly what that section of code is meant to do so I am guessing that isn't the way forward.

[Thell]

I thought I'd also mention that with the presolve set off my pywraplp -> CBC implementation is again notably faster than the Rust -> HiGHS implementation on my larger test sets.

One nice thing is that out of ~70,000 solutions from a variety of data sets the two optimizers only have 1 conflicting response and its on one of the larger datasets so an exact solution isn't available but they agree on the cost and one of the state values (I'm doing a multi-state subset selection problem) so that's a good thing. :)

[jajhall]

Indeed, setting presolve=off is a radical solution.

The assert that you've hit shouldn't matter, in that when compiling in release the case is still handled. It's a developer's assert, and could be side-stepped by making it also conditional on kAllowDeveloperAssert.

The assert is a low probability event, and is there to allow me to understand how the outcome can occur. Since you're building from source, could you send me the output if you

1. remove the if statements in lines 1257 and 1266
2. just before the assert, add the following print statement printf("After presolve infeasible or unbounded: simplex model status is %d\n", int(modelstatus));

I'm a little puzzled that setting allow_unbounded_or_infeasible to be true doesn't avoid the assert. Could you print out the value of this option before line 1242, please.

To learn more about options, you can now use

https://ergo-code.github.io/HiGHS/dev/options/definitions/#option-definitions

I trust that you're not comping HiGHS with Cbc when both are compiled with debug. The only valid performance comparison comes when compiled with release.

[Thell]

Thanks for the reply @jajhall ; here is a capture of an instance of the infeasible/unbounded assertion:

[2023-04-22T18:47:48.636692400Z DEBUG housecraft::optimize] running for (1100,0)...
Presolving model
246 rows, 402 cols, 758 nonzeros
135 rows, 291 cols, 613 nonzeros
133 rows, 229 cols, 549 nonzeros
112 rows, 88 cols, 184 nonzeros
18 rows, 79 cols, 118 nonzeros
18 rows, 30 cols, 69 nonzeros
3 rows, 12 cols, 16 nonzeros
Objective function is integral with scale 1

Solving MIP model with:
   3 rows
   12 cols (9 binary, 3 integer, 0 implied int., 0 continuous)
   16 nonzeros

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

         0       0         0   0.00%   312             inf                  inf        0      0      0         0     0.0s
Assertion failed: model_status_ == HighsModelStatus::kInfeasible || model_status_ == HighsModelStatus::kUnbounded, file C:\Users\thell\.cargo\git\checkouts\highs-sys-libz-228d8310235e4834\7c0c66a\HiGHS\src\lp_data\Highs.cpp, line 1280

output.txt subset_select_highs.log

edit: I forgot to mention there should be a feasible solution to that problem as I only change the lower bound and the upper bounds are infinite (in this case the lower bounds for the two constraints are (1100, 0) and a solution exists at (1101, 0).

I also captured a different assert:

[2023-04-22T18:23:34.902811400Z DEBUG housecraft::optimize] running for (653,6)...
Presolving model
247 rows, 402 cols, 788 nonzeros
136 rows, 291 cols, 643 nonzeros
132 rows, 189 cols, 478 nonzeros
Objective function is integral with scale 1

Solving MIP model with:
   132 rows
   189 cols (189 binary, 0 integer, 0 implied int., 0 continuous)
   478 nonzeros

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

         0       0         0   0.00%   0               inf                  inf        0      0      0         0     0.0s
 R       0       0         0   0.00%   187.5652174     190                1.28%        0      0      0        96     0.0s
 C       0       0         0   0.00%   187.6679901     189                0.70%       46      5      0       124     0.0s
Assertion failed: std::fabs(double(lowerFromScratch - objectiveLower)) <= domain->feastol(), file C:\Users\thell\.cargo\git\checkouts\highs-sys-libz-228d8310235e4834\7c0c66a\HiGHS\src\mip\HighsDomain.cpp, line 1098

which I could not capture on subsequent runs.

I'm wondering... Is it possible that I am perhaps causing a model state that is leading to these issues by using the same model repetitively and changing constraint bounds on each iteration? Should I perhaps be calling something to clear the model's solution state between each iteration?

And, yes, that linked option list is what I had been using but the 'advanced' option of allow_unbounded_or_infeasible isn't listed. I don't think I would have clicked on a link for listing more advanced options either without having already having looked at the source around that assert but it couldn't hurt to link HighsOptions.h in the options section of the documentation.

Perhaps I was setting it wrong, I assumed it was a bool option

            let option = CString::new("allow_unbounded_or_infeasible").unwrap();
            Highs_setBoolOptionValue(highs, option.as_ptr(), 1);

I'll run and print that along with wrapping the assert with kAllowDeveloperAssert and then try again with presolve in its default choose. 🤞

Regarding the timings... yes, that was both in release mode but with presolve off in HiGHS.

[Thell]

I only had 1 instance of those printf statements in my output:

Solving MIP model with:
   132 rows
   189 cols (189 binary, 0 integer, 0 implied int., 0 continuous)
   478 nonzeros
         0       0         0   0.00%   312             inf                  inf        0      0      0         0     0.0s
options_.allow_unbounded_or_infeasible is 0

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

After presolve infeasible or unbounded: simplex model status is 7
         0       0         0   0.00%   1               inf                  inf        0      0      0         0     0.0s
 S       0       0         0   0.00%   312             333                6.31%        0      0      0         0     0.0s

Solving report
  Status            Optimal
  Primal bound      333
  Dual bound        333
  Gap               0% (tolerance: 0.01%)
  Solution status   feasible
                    333 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            0.02 (total)
                    0.02 (presolve)
                    0.00 (postsolve)
  Nodes             1
  LP iterations     6 (total)
                    0 (strong br.)
                    0 (separation)
                    0 (heuristics)

The allow_unbounded_or_infeasible was set as mentioned above and I had the assert wrapped with kAllowDeveloperAssert.

[Thell]

Alright! This is good. 👍

I've been able to run my test data sets with presolve and the wrapped assert and the timings are back inline with expectations (~40-45% of the time Python -> CBC optimization takes)! When I add in the time of post-processing it gets pretty dramatic with the Python -> CBC implementation taking 49m52 -vs- Rust -> HiGHS taking 8m32s; that's a nice win. Although, to be fair I came up with the Python implementation in a day and its been about 3 weeks for the Rust one soo.... lol.

---

I wanted to let you know that even though that option value is read as not being set when that case block is accessing it I tested with getBoolOptionValue right after setting it and right before destroying the HiGHS instance while running some tests and I get a 1 response so it is indeed being set. I'll just leave it unset and the assert wrapped.

[Thell]

Should I start a new issue for this?

After adding some more datasets to process I ran into another presolve assert. I'm not sure if it is a developer assert or not but the data runs through Python -> CBC and completes just fine in HiGHS with presolve off...

Presolving model
19 rows, 51 cols, 72 nonzeros
6 rows, 25 cols, 33 nonzeros
6 rows, 15 cols, 23 nonzeros
5 rows, 13 cols, 19 nonzeros
Objective function is integral with scale 1

Solving MIP model with:
   5 rows
   13 cols (11 binary, 2 integer, 0 implied int., 0 continuous)
   19 nonzeros

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

         0       0         0   0.00%   10              inf                  inf        0      0      0         0     0.0s
Assertion failed: model->col_lower_[col] == -kHighsInf || (model->col_lower_[col] <= implColLower[col] + primal_feastol && colLowerSource[col] == row), file C:\Users\thell\.cargo\git\checkouts\highs-sys-libz-228d8310235e4834\a52e7ce\HiGHS\src\presolve\HPresolve.cpp, line 2913

https://github.com/ERGO-Code/HiGHS/blob/2da0f1cccf2801574630ff9fa5f7c044b2e9d124/src/presolve/HPresolve.cpp#L2913

This is within https://github.com/ERGO-Code/HiGHS/blob/2da0f1cccf2801574630ff9fa5f7c044b2e9d124/src/presolve/HPresolve.cpp#L2854

[Thell]

I figured out a big part of my frustrations and that is that I work both in WSL and Windows but on Windows using the highs-sys NDEBUG never gets set so the asserts are always enabled. I'm guessing this has something to do with CMake and MSVC interaction but 🤷 . It's also why my performance on Windows is about half of what it is in WSL for the optimization portion of my program.