search

ERGO-Code / HiGHS

Linear optimization software
MIT License
912 stars 169 forks source link

Solver option "choose", MIP ignored otherwise #1723

Open Cellophil opened 4 months ago

Cellophil commented 4 months ago

The documentation states:

Solver option: "simplex", "choose", "ipm" or "pdlp". If "simplex"/"ipm"/"pdlp" is chosen then, for a MIP (QP) the integrality constraint (quadratic term) will be ignored.

It's easy to overlook that integrality is ignored I think; people will try to speed up their problems and the first thing as an end-user does is to switch out the solvers. I'll admit I did that and enjoyed a nice speedup with my MIP problem (LP of course much easier). Also, is there no way to influence what solver is preferred for the subproblems for MIP?

I think an easy fix would be to raise an Error whenever a user tries to run a MIP or QP model with one of the solvers specified, instead of ignoring integrality.

jajhall commented 4 months ago

I think an easy fix would be to raise an Error whenever a user tries to run a MIP or QP model with one of the solvers specified, instead of ignoring integrality.

That makes sense. I didn't give much thought to people trying to solve MIQPs when is stated reasonably clearly in the documentation that HiGHS can't solve them. However, I'd not considered the "switch out the solvers" scenario.

Also, is there no way to influence what solver is preferred for the subproblems for MIP?

For the root node, we should offer interior point, and it shouldn't be difficult. For the node problems, there's no sense in using anything other than dual simplex, so we wouldn't offer the option.

mzy2240 commented 4 months ago

Like many other solvers which provide two common endpoints solve and solvelp, the only efficient way to achieve the same thing in HiGHS is to use the param solver to switch between modes. And it can be very useful in some case where you use LP as some sort of logical presolve for a MIP problem. I sincerely suggest we keep the current behavior as is, or provide some other ways to achieve the same effortless relaxation.

jajhall commented 4 months ago

I see how solve and solveLp differ in COPT

HiGHS allows the MIP relaxation to be solved as an LP - by IPM or simplex - if anyone wants to use its solution for a primal heuristic.

Who would define a (MI)QP and then want to solve the problem without the Hessian? COPT is great software, but I question the value of having solveLp just to enable any integrality and Hessian to be ignored automatically. Even without a solveLp, it's not hard to do using HiGHS.

Are you saying that it's wrong to return an error if someone tries to use HiGHS to solve a MIQP, rather than solve it as a QP? If someone is trying to solve a MIQP, they need to know that HiGHS can't do so. If they want to solve the QP relaxation I feel that it's better for them to tell HiGHS explicitly that they want to do so. I might have to modify HiGHS, but this isn't hard to achieve.

What makes no sense is to use anything but dual simplex to solve LP subproblems in a MIP solver.

mzy2240 commented 4 months ago

My usecase is just solving MILP in an iterative process to gradually add more constraints. I have no knowledge on MIQP.

jajhall commented 4 months ago

What "many other solvers" provide two common endpoints like solve and solveLp?

If you're interested in solving the LP corresponding to a MIP with HiGHS, just set the option solve_relaxation=true

No need for separate solvers.

I'm genuinely looking to understand the point that you're trying to make

mzy2240 commented 4 months ago

Ic. Now it makes sense. I did not see ‘solve_relaxation’ in the list of options tho.

jajhall commented 4 months ago

OK we don't document HiGHS as well as we might

jajhall commented 4 months ago

Highs::run() does return an error if the incumbent model is an MIQP

jajhall commented 4 months ago

Currently, for the solver option, if "simplex"/"ipm"/"pdlp" is chosen then, for a MIP (QP) the integrality constraint (quadratic term) will be ignored.

As observed above, this can lead to unexpected behaviour when the incumbent model is a MIP or QP, and a user specifies the solver option, believing that alternatives will be considered.

In v2.0 - since it breaks behaviour fundamentally - it's preferable to ignore the solver option when it's not relevant to the incumbent model.

Note:

Solver option: "simplex", "choose", "ipm" or "pdlp". If "simplex"/"ipm"/"pdlp" is chosen when the incumbent model is not an LP, the setting will be ignored.

Cellophil commented 3 months ago

I like the solution, very much appreciated!

Am 5. Mai 2024, 18:23, um 18:23, Julian Hall @.***> schrieb:

Currently, for the solver option, if "simplex"/"ipm"/"pdlp" is chosen then, for a MIP (QP) the integrality constraint (quadratic term) will be ignored.

As observed above, this can lead to unexpected behaviour when the incumbent model is a MIP or QP, and a user specifies the solver option, believing that alternatives will be considered.

In v2.0 - since it breaks behaviour fundamentally - it's preferable to ignore the solver option when it's not relevant to the incumbent model.

Note:

  • The documentation string will become

Solver option: "simplex", "choose", "ipm" or "pdlp". If "simplex"/"ipm"/"pdlp" is chosen when the incumbent model is not an LP, the setting will be ignored.

  • Once the new IPM solver is introduced for LPs, "ipm_direct" and "ipm_iterative" will have to be introduced, with "ipm" leaving HiGHS to choose between "ipm_direct" and "ipm_iterative"

  • Once the new IPM solver can handle QPs, "qp_ipm" and "qp_asm" will have to be introduced

-- Reply to this email directly or view it on GitHub: https://github.com/ERGO-Code/HiGHS/issues/1723#issuecomment-2094867127 You are receiving this because you authored the thread.

Message ID: @.***>