How Gurobi solves a optimisation problem that doesn't have an objective?

Answered

Hongyu Zhang

• June 14, 2022 11:42

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.

0

• 

  Jaromił Najman

  Gurobi Staff

  • June 14, 2022 13:17

  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
• 

  Hongyu Zhang

  • July 04, 2022 20:54

  

  

  

  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
• 

  Jaromił Najman

  Gurobi Staff

  • August 10, 2022 07:18

  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

Please sign in to leave a comment.