Branch and Cut algorithm using callbacks

[Carlos Casorran]

Hello,

I have a couple of questions regarding Branch and Cut in Python using Gurobi as a solver.

In a maximisation problem, at each node, I would like to add cuts (obtained from a separation problem) to cut off fractional solutions. I have done this using callback functions.

if where == GRB.callback.MIPNODE:

nodecnt = int(model.cbGet(GRB.callback.MIPNODE_NODCNT))

status = model.cbGet(GRB.Callback.MIPNODE_STATUS)

print '*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*'

print "Node count: %s" %nodecnt

print "Objective bound: %s" %mipnodeobjbnd

 print '*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*'

if status==GRB.OPTIMAL:

CurrentBestObjBound=model.cbGet(GRB.callback.MIPNODE_OBJBND)

CurrentBestObj=model.cbGet(GRB.callback.MIPNODE_OBJBST)

if CurrentBestObjBound-CurrentBestObj>0.001:

             I generate and optimize my Separation Problem.

             I get one of two types of cuts (feasibility or optimality)

             If cut is violated:

                      model.cbCut( bla bla)

                      print "OPTIMALITY CUT ADDED" (or feasibility cut added)

From what I see from the output it would appear that several cuts are added at the root node but then from then on, no more than one cut is added at subsequent nodes.

Changed value of parameter Presolve to 0

   Prev: -1  Min: -1  Max: 2  Default: -1

Changed value of parameter Heuristics to 0.0

   Prev: 0.05  Min: 0.0  Max: 1.0  Default: 0.05

Changed value of parameter Cuts to 0

   Prev: -1  Min: -1  Max: 3  Default: -1

Changed value of parameter PreCrush to 1

   Prev: 0  Min: 0  Max: 1  Default: 0

Changed value of parameter TimeLimit to 1800.0

   Prev: 1e+100  Min: 0.0  Max: 1e+100  Default: 1e+100

Changed value of parameter Threads to 1

   Prev: 0  Min: 0  Max: 1024  Default: 0

*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*

Node count: 0.0

Objective bound: 21.9468085106

*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*

OPTIMALITY CUT ADDED

*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*

Node count: 0.0

Objective bound: 6.26442665386

*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*

OPTIMALITY CUT ADDED

*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*

Node count: 0.0

Objective bound: 6.26442665386

*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*

OPTIMALITY CUT ADDED

*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*

Node count: 1.0

Objective bound: 6.25559677952

*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*

OPTIMALITY CUT ADDED

*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*

Node count: 2.0

Objective bound: 6.25141656732

*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*

OPTIMALITY CUT ADDED

*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*

Node count: 3.0

Objective bound: 6.24290495181

*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*

OPTIMALITY CUT ADDED

*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*

Node count: 4.0

Objective bound: 6.23847511683

*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*

OPTIMALITY CUT ADDED

*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*

Node count: 5.0

Objective bound: 6.22881353932

*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*

OPTIMALITY CUT ADDED

*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*

Node count: 6.0

Objective bound: 6.18265139116

*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*

Cutting planes:

  User: 8

Explored 7 nodes (51 simplex iterations) in 0.27 seconds

Thread count was 1 (of 4 available processors)

Optimal solution found (tolerance 1.00e-04)

Best objective 6.182651391162e+00, best bound 6.182651391162e+00, gap 0.0%

So it seems that I am adding cuts at the root node and then at some point, the algorithm decides to branch and move on to the next node. Is there no way I can control how many cuts I can add at a node before branching? Also, I get the impression that once the cut is added at a node other than the root node, that node is not then resolved before moving on the next one. Is this the case? Again, how can I ensure staying at the node to apply successive rounds of cuts before moving on?

I guess that I would be able to do what I want if the callback were called when a new fractional solution is found and not when a new node is visited. I would then have some parameter to force the algorithm to branch after a certain condition is met (number of cuts added at the node, or time spent at the node). Is this possible?

I saw in a reply to this question (https://groups.google.com/forum/#!newtopic/gurobi/gurobi/YZHG48FQLaU) that setting the number of threads to 1 ensured that the cut be applied at the node, but in the instances I have tried, this has not made a difference.

Any help will be appreciated :) Thank you!

Carlos.

[Tobias Achterberg]

Hi Carlos,

the root node is the only node for which we separate cuts in rounds. For all
other nodes we would only call the cut separators (including the user callback)
once, then resolve the LP and then branch.

The difference with parallel and sequential solves is the following:

For a sequential solve the cuts are applied immediately, then the LP is
resolved, and then we branch. Consequently, for all subsequent nodes, the cut
will already be in the LP (except if we decide later to purge the cut again).

For a parallel solve, however, the cuts are not always applied immediately but
buffered somewhere to be applied later. Thus, it can happen that the next node
(for example, the child node) is not yet having the cut in its LP relaxation and
thus the new LP solution may still violate the cut. At some point, the cut will
be added to the LP, and from then on it will be satisfied by all subsequent LP
relaxations (except for cut purging).

Hope this helps!

Regards,

Tobias

[Carlos Casorran]

Gotcha. Thank you for your prompt and detailed answer.

Carlos.

--

--- You received this message because you are subscribed to a topic in the Google Groups "Gurobi Optimization" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/gurobi/_JUHVqdNy7s/unsubscribe.
To unsubscribe from this group and all its topics, send an email to gurobi+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Carlos Casorran]

Tobias,

Regarding the first part of your answer, if I well understood, you do separate cuts in rounds at the root node. These rounds are governed by some parameter which can be fixed beforehand so that I can tell my program how many rounds have to be performed at the root node before branching?

The reason I ask is the following. In my case, I have two MILP formulations which are valid for the same problem and one is stronger from an LP relaxation point of view than the other. I implement a B&C on the weak formulation, where the cuts are produced from solving a separation problem. This separation problem comes from applying Benders decomposition on the strong formulation. In this setting I would expect the MIP gap % (the gap % between the LP solution at the root node and the integer optimal solution) of the weak formulation plus the cuts to be the same as that of the strong formulation. And as you can see in the attached graph, this is not the case.

My guess is I am not correctly retrieving the LP solution after having added the cuts, prior to branching. The way I go about this inside the callback is the following:

def mycallback_q(model, where):

if where == GRB.callback.MIPNODE:

        mipnodeobjbnd=model.cbGet(GRB.callback.MIPNODE_OBJBND)

        nodecnt = model.cbGet(GRB.Callback.MIPNODE_NODCNT)

        if status==GRB.OPTIMAL:

                Retrieve fractional solution

                Solve Sep. Problem & Obtain Cut

                Check violation--If cut violates current fractional sol., add cut

                If nodecnt == 0

                       LPValueWithCuts = Objective Function computed on current fractional solution

Should I use  nodecnt == 0 or nodecnt ==1? (I guess that for nodecnt == 1, I would obtain the sol after having added the last cuts from the root node, and would not have yet optimised with the cuts obtained from node 1)

                       

Or maybe I'm doing it all wrong and there is a much simpler way of getting the LP value after the cuts.

Hope all of this makes sense. Thanks for your help!

Carlos.     

[Tobias Achterberg]

Hi Carlos,

the root node is node 0. Node 1 would be the first child node of the root that
is processed.

What you are doing in your callback seems fine.

Most likely, the issue is just that you cannot expect the two versions to
produce the same objective value after finishing the root node cutting plane
loop. The reason is that cut separation is a heuristic procedure. It takes the
current LP solution as input (and this will be different in your two
formulations) and produces some set of cutting planes. Some of those cuts
(usually not all) are added to the LP, with the selection process being again
some heuristic procedure. Then it repeats until an abort criterion is reached.
Again, the abort criterion is heuristic (it depends on the progress in the
objective value and in the number of integer infeasible variables).

You can specify the maximum number of cut passes at the root node using the
"CutPasses" parameter. This overrides the heuristic abort criterion. But still,
if at some point none of the cut separators find any violated cut, the cut loop
is aborted prematurely.

I understand that your two models should procude the same LP objective value,
provided that all violated cuts produced by your separation procedure are added
to the weak formulation. You may achieve this situation if you disable all
Gurobi-internal cuts (setting the "Cuts" parameter to 0). But as soon as some
Gurobi-internal cuts are active, your objective values will typically differ.

Tobias