How Gurobi solves a optimisation problem that doesn't have an objective?
回答済みHello!
I am solving an LP optimisation problem and wondering how Gurobi solves a problem without an objective?
For example, an LP problem with some inequality constraints and some equality constraints but there is no objective function. It is basically a feasibility problem. In such a situation, what solution will Gurobi provide? After searching for some literature, we guess Gurobi will choose a point that is the centre to all the constraints. In other words, Gurobi will choose a point that satisfies the equality constraint exactly and have the maximum product of distances to the inequality constraints. It is called the analytical centre in literature. We are guessing Gurobi is doing analytic centre, but could anyone confirm what we thought?
The Gurobi solver is set to use interior point, no crossover, presolve on/off.
Kind regards,
Hongyu.
-
正式なコメント
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
Hi Hongyu,
We are guessing Gurobi is doing analytic centre, but could anyone confirm what we thought?
The Barrier algorithm without crossover, i.e., Crossover set to 0, in general returns a solution positioned in the analytic center of the optimal facet (or at least very close to it).
The post Is it possible to get the value of the Interior Point solution? discusses this in a bit more detail.
Best regards,
Jaromił0 -
-
Hi Jaromił,
Thanks very much for your answer. It confirms what we have been thinking. But I have two follow-up questions hope you could answer.
1. What will Gurobi do if we set "min 0" as a fake objective function instead of a non-objective feasibility problem? (Under the same Gurobi option setting as the question above). Will Gurobi still do the analytic centre?
2. What will Gurobi do if we turn on the presolve when we have 1) a non-objective feasibility problem and 2) an optimisation problem with a fake min 0 objective function? (the same setting for Gurobi as the question above, only presolve is on).
Kind regards,
Hongyu.
0 -
-
-
Hi Hongyu,
What will Gurobi do if we set "min 0" as a fake objective function instead of a non-objective feasibility problem? (Under the same Gurobi option setting as the question above). Will Gurobi still do the analytic centre?
If you don't set any objective, then Gurobi will use 0 as objective function meaning that setting the objective explicitly to 0 should have no effect. Gurobi will then still return the analytic center.
What will Gurobi do if we turn on the presolve when we have 1) a non-objective feasibility problem and 2) an optimisation problem with a fake min 0 objective function? (the same setting for Gurobi as the question above, only presolve is on).
There should be no difference between the two settings because Gurobi will use the 0 objective as default when no objective is provided. Please note that provided a non-zero objective function when searching for a feasible point only can greatly benefit the solution process, because the objective function can be used by certain heuristics to "lead" them into a feasible point. In order to stop as soon as a first feasible point is found you should set the SolutionLimit parameter to 1.
Best regards,
Jaromił0 -
投稿コメントは受け付けていません。
コメント
4件のコメント