Skip to main content

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

Answered

Comments

3 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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
    First Comment
    First Question

    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 Gurobi Staff

    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.