Is it possible to return the initial problem gap without solving it?

Answered

Araz Nasirian

• February 03, 2023 07:50

I am working on a decomposition algorithm.

The algorithm develops a number of constraints in each iteration. The constraints can be added to an original problem.

Without the developed constraints the Gurobi initial gap is 75% for example.

Adding developed constraints after a few iterations limits the search place and makes the initial gap 30 %, for say. And solution time decrease.

If too many constraints are added the model gets big and initial gap increases and solution time increases.

At the moment, I run the algorithm and add the constraints to the original problem and watch the gap if the gap decreases I continue the algorithm if the gap increases I stop. I don't wait for the whole solution I just watch the gap and stop solution. If the gap is good I let the solution procedure continue.

Is there any way to automate this process. I mean is there a function that returns the initial gap without actually solving it?

Related to

• MIP Gap

0

• 

  Jonasz Staszek

  Community Moderator

  • February 03, 2023 11:04

  

  

  

  Hi Alex,

  if you are only interested in the initial gap, then you might be happy taking the first feasible solution found by Gurobi, as well as the value of the bound. This can be done by setting the Solution Limit parameter to 1, and then querying for the appropriate attributes (here MIPGap could be the one you are after).

  This approach has one weakness - if Gurobi manages to find a feasible solution heuristically before coming up with a bound, it will then terminate immediately and you might be left without a bound to calculate the MIPGap.

  Perhaps someone from Gurobi Team can comment further?

  Best regards
  Jonasz

  0
• 

  Jaromił Najman

  Gurobi Staff

  • February 03, 2023 12:38

  Hi Alex,

  In addition to what Jonasz already pointed out I have a few questions.

  Adding developed constraints after a few iterations limits the search place and makes the initial gap 30 %, for say. And solution time decrease.

  If too many constraints are added the model gets big and initial gap increases and solution time increases.

  The gap can only increase when you add constraints which cut off the current incumbent or which make the dual bound flip from negative to positive or vice versa or to 0 (unless I am missing something). Is this possible with your constraints? If yes then, one possibility would be to set the SolutionLimit parameter as mentioned by Jonasz, retrieving the feasible point values via the X attribute and checking whether your constraints cut it off.

  Could you implement your constraints as user cuts of lazy constraints?

  I mean is there a function that returns the initial gap without actually solving it?

  No, there is no such function, because one has to have a feasible point and a dual bound to compute a gap. This is not possible without at least partially solving the model. You could implement a MIPNODE callback, retrieve the dual and primal bounds and compute the mipgap within the callback. Alternatively, you could use the MESSAGE callback and extract the MIPGap printed by Gurobi from a given log line.

  Best regards, 
  Jaromił

  0

Please sign in to leave a comment.