search

ERGO-Code / HiGHS

Linear optimization software
MIT License
962 stars 179 forks source link

Infeasible problem in highs, solveable in lpsolve #1756

Closed nunzioono closed 5 months ago

nunzioono commented 5 months ago

Hi, i've been writing for some time a program using good lp (rust crate that extends highs-rs), i've a model with 2k rows of constraints and while i've implemented it in good lp using the highs solver specified in the features it gets detected as unfeasible. On the other hand if i debug the same model printing it as an lp file and pass it within lpsolve ide it gets solved specifying that some of the constraints are redundant. I wonder if this can be a feature to be added or should be classified as a presolve bug in the highs crate/module since, as me, i believe many models can be represented using "implicitely" redundant constraints. As implicit i mean bounds that in some solution result as redundant and changing a parameter in the problem (another bound), are no more redundant.

jajhall commented 5 months ago

I'm not sure what "feature" you'd like, or quite what you mean by "implicitly" redundant constraints. I can understand that constraints may be inactive at the solution of a problem, but are then active when the problem is modified.

I'd be particularly keen to have the model that has exhibited this behaviour, and know of the version of HiGHS that is being used in good lp, since (1) we may be able to fix the bug and (2) recent bug-fixes may mean that the error does not occur in the latest version of HiGHS.

Finally, it's surprising that HiGHS is failing on a problem where the relatively poor MIP solver in lpsolve succeeds. Are you certain that the problem is feasible?

nunzioono commented 5 months ago

Sorry for the missunderstanding i don't either know yet if is a lpsolve (highs missing feature in the presolve module) or if is just my model. Sure can use my problem to check, the program i'm writing is on this repo either the "model.lp" file which i use in lpsolve and works. On each time i run the program the model.lp is different but the behaviour is the same: Unfeasible in good_lp and solved in lpsolve.

nunzioono commented 5 months ago

To further help in the meaning of the repo, the model should be representing a domino puzzle (a sequence of domino tiles). Each binary variable is named as xijkk where i and j are the numbers of the 2 halves of the tile and kk is the number (expressed on 2 digits) of the position that the tile will take in the puzzle. The constraints are divided in 3 categories: unique tile per position, unique tile in the puzzle and bounds for preceiding/succeding tiles in the sequence.

nunzioono commented 5 months ago

The repo does in order:

  1. Generates a certain number of random extracted tiles in random positions (done to reduce the computation time)
  2. Model is represented mapping the non used tiles in the whole tileset (assume a tileset is the set of couples raning from 00 to nn where n can be either 6, 9, 12)
  3. The model is runt in good_lp
  4. The file .lp represeting the above model is written locally
jajhall commented 5 months ago

Thanks. I've downloaded your model. However it is in the lpsolve "LP" format, not the CPLEX LP format . The two formats are similar, but HiGHS (and Gurobi) can't read the lpsolve "LP" format. I've converted it by hand - faithfully, I believe - and Gurobi also finds the problem to be infeasible. Hence the bug may be in lpsolve. Have you extracted the solution from lpsolve and verified that it is feasible?

To be sure, please would you get lpsolve to write the model out in MPS format.

nunzioono commented 5 months ago

Thank you, i've found out that the lpsolve solver does compute a solution even if is unfeasible but it's indeed an "unfeasible" solution to the problem/puzzle in real world so it should be a bug of lpsolve not highs. Thanks for your time.

jajhall commented 5 months ago

Thanks. I'm pleased to see this resolved, and will remember it as a possible source of confusion for lpsolve users.