Gurobi finds an initial solution faster without an objective function

Answered

Rafael Carsch

• August 12, 2024 22:11

I'm working on a large sports scheduling MILP research, and I'm having the following issue: gurobi takes a huge time to find an initial solution, but when I take the objective function away from the model formulation, gurobi finds a solution very quickly (in less than a minute in most cases). What can I do, so that, while maintaining my objective function, it finds an initial solution in a short amount of time (as fast as it takes to find when it doesn't have an objective function)? I tried to change the MIPFocus and the SolutionPoolMode parameters, but it didn't work...

Related to

• Heuristics

0

• 

  Riley Clement

  Gurobi Staff

  • August 13, 2024 06:23

  Hi Rafael,

  When you take the objective away you are solving what is referred to as a "zero-objective model".  You may have heard of our zero-objective heuristic - this heuristic solves the model without the objective in the hope of finding a solution quickly, if a solution has not yet been found.

  For zero-objective models the solver changes some parameters and the approach to finding a solution, and it is not surprising if the solver can find a solution faster for the zero-objective model faster than the original model.  If the quality of the zero-objective solution is good, with respect to the original objective, then you could set it as a start solution using MIP starts.  If the solution quality is not good then using it as a MIP start may be counterproductive as Gurobi may put substantial effort trying to improve a bad solution, when we'd rather it spend effort looking for good solutions.

  Another approach to try is our No Relaxation (NoRel) heuristic - it is often quite good at finding solutions where they are otherwise hard to find.  To use it, set NoRelHeurTime or NoRelHeurWork to a non-zero value.

  Note, the NoRel heuristic has 2 phases. In the first phase, the heuristic focuses on finding a feasible solution. The relaxation value tells how far the current infeasible solution is from a feasible one. The lower the value, the closer the heuristic is to shifting to phase 2. In phase 2, a feasible point is available and the heuristics tries to improve the objective value.  You will see output in the log related to these phases.  If NoRel does not reach phase 2 before it terminates then it won't have achieved anything.

  - Riley

  0

Please sign in to leave a comment.