Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

When possible, ensure basis and internal solution are propagated when model status is HighsModelStatus::kUnknown #2108

Open
deryaozyurt opened this issue Jan 7, 2025 · 1 comment
Assignees

Comments

@deryaozyurt
Copy link

deryaozyurt commented Jan 7, 2025

Greetings,
The attached (probably degenerate) problem gives the following output with status "Unknown" (perhaps similar to issue $2015):

Coefficient [ranges:]
Matrix [1e+00, 1e+00]
Cost [1e-02, 2e+03]
Bound [7e-03, 7e+04]
RHS [2e+04, 3e+04]
Presolving model
144 rows, 8041 cols, 8327 nonzeros 0s
144 rows, 7872 cols, 8158 nonzeros 0s
Presolve : Reductions: rows 144(-0); columns 7872(-1152); elements 8158(-1152)
Solving the presolved LP
Using EKK dual simplex solver - serial
Iteration Objective Infeasibilities num(sum)
0 6.5170028673e-02 Pr: 50(1.02587e+06) 0s
362 2.4550484492e+07 Pr: 0(0); Du: 1(1.3e-07) 0s
362 2.4550484492e+07 Pr: 0(0); Du: 1(1.3e-07) 0s
Model status : Unknown
Simplex iterations: 362
Objective value : 2.4550484492e+07
HiGHS run time : 0.12
degenerateProblem.zip

@deryaozyurt deryaozyurt changed the title A medium size LP makes HiGHs return Model Status - Unknown after 360+ itertions A medium size LP makes HiGHS return Model Status - Unknown after 360+ itertions Jan 7, 2025
@jajhall
Copy link
Member

jajhall commented Jan 8, 2025

Yes, this is the anti-cycling test causing termination of the simplex solver with a dual infeasibility. Since that dual infeasibility is 1.3e-7, it's fair for a user to assume that the problem has been solved.

That said, when I used HiGHS to write out the solution, there was no basis, and there appeared to be primal infeasibilities. It looks as if something is "not done" when the problem status is "Unknown". That's something to be addressed, as is logging to inform the user why the solution status is "Unknown" (see #1979), and how to assess whether it's close enough to be optimal.

@jajhall jajhall changed the title A medium size LP makes HiGHS return Model Status - Unknown after 360+ itertions When possible, ensure basis and internal solution are propagated when model status is HighsModelStatus::kUnknown Jan 8, 2025
@jajhall jajhall self-assigned this Jan 8, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants