How should I interpret the cutting planes in the summary section of the log file?

[Ali Baharev]

I solve a pure integer linear program (all variables are binary) by calling:

    model.params.LazyConstraints = 1
    model.optimize(callback)

The initial model had 441 constraints, and I had to add 944 additional distinct constraints in total when Gurobi called my callback function. I counted it myself in my callback function. I am fairly certain that at least some of those constraints were absolutely necessary to find the optimal solution and to prove its optimality (though I haven't checked this).

In the summary section of the log file I see something like:

  Cutting planes:

    Gomory: 4

    Flow cover: 7

    Zero half: 21

How should I interpret this cutting planes summary?

Did Gurobi compact my 944 lazy constraints into these 32 cutting planes?

Can I somehow make the solution process faster based on this information?

In other words, is this information actionable? Does it convey anything useful?

Using the terminology of Constraint Integer Programming (PhD thesis of Tobias Achterberg), I assume that Gurobi, among other things, did something similar to what is discussed in 3.3.8 Separation Storage, and that Gurobi generated those cutting planes with clever heuristics based on my lazy constraints ("compacted" my lazy constraints into smart cutting planes).

Is there a place in the official Gurobi website / documentation where this is explained at least on a very high level?

If not: Which sections of Tobias Achterberg's PhD thesis are the closest descriptions of what is happening here?

Many thanks in advance,

Ali

[Daniel Espinoza]

Hi Ali,

The log only shows the cuts that were active at the end of the B&B process.

Your cuts might have been used during the solve, but at some point where either dominated by the internal cuts, or even used to derive new cuts, but where not used in the final LP.

To see if they where helpful or not, you should try to run your model without them and compare final running time.

Best,

Daniel

[Ali Baharev]

Hi Daniel,

Thanks for the quick response.

> The log only shows the cuts that were active at the end of the B&B process.
> Your cuts might have been used during the solve, but at some point where
> either dominated by the internal cuts, or even used to derive new cuts, but
> where not used in the final LP.

OK. So that summary is not very useful for users.

> To see if they where helpful or not, you should try to run your model
> without them and compare final running time.

Yes, I know. It wasn't my question.

And it is more complicated than that: It is very likely that without
those lazy constraints that were added later, Gurobi would end up in a
point that is infeasible in my original problem. (The constraints of
the original problem cannot be enumerated explicitly; there are too
many of them.) But it wasn't the question.

Could you answer my other questions, please?

Namely these:

[Daniel Espinoza]

Hi Ali, I'll try to go in detail for each question

How should I interpret this cutting planes summary?

That I explained before.

 

Did Gurobi compact my 944 lazy constraints into these 32 cutting planes?

No, Gurobi will not `compact` your constraints, but it may use them to derive new ones.

 

Can I somehow make the solution process faster based on this information?

Assuming your constraints are needed, the fact that they do not appear in the final log at least suggest that they are somewhat weak for the full problem, so, trying to strengthen them might be useful.

 

In other words, is this information actionable? Does it convey anything useful?

If your problem requires many B&B nodes to solve, then trying to be more aggressive on the successful cuts might help.

But as everything in MIP, you have to try.

 

Using the terminology of Constraint Integer Programming (PhD thesis of Tobias Achterberg), I assume that Gurobi, among other things, did something similar to what is discussed in 3.3.8 Separation Storage, and that Gurobi generated those cutting planes with clever heuristics based on my lazy constraints ("compacted" my lazy constraints into smart cutting planes).

As I said, they might have been used to generate Zero-half cuts... or it could be a bit more involved than that (i.e. several rounds of derived cuts using other classes in between)

 

Is there a place in the official Gurobi website / documentation where this is explained at least on a very high level?

Not really, but in essence is what Branch and Cut is, with several cut-generators and (in principle) several rounds of cuts and re-solve.

 

If not: Which sections of Tobias Achterberg's PhD thesis are the closest descriptions of what is happening here?

Should ask Tobias about that ;-)

 

Best,

Daniel

[Ali Baharev]

Hi Daniel,

OK, thanks.

One last question:

> The log only shows the cuts that were active at the end of the B&B process.
> Your cuts might have been used during the solve, but at some point where
> either dominated by the internal cuts, or even used to derive new cuts, but
> where not used in the final LP.

I am not sure what "the final LP" is. The search tree has several leaf
nodes, and it can be arbitrary which node is processed last, and it
can also be arbitrary why a node of the search tree becomes a leaf
node.

Please define "the final LP".

Thanks,

Ali

> --
>
> ---
> 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/bQzlHHyG_eM/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to
> gurobi+un...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Tobias Achterberg]

Hi Ali,

Gurobi is only using globally valid cuts, and these cuts are added to all LP
relaxations that are solved subsequently, independent on where in the search
tree they have been generated. Hence, the "final" LP is really the very last LP
that has been solved during the solving process.


Best regards,

Tobias

[Ali Baharev]

Hi Tobias,

Thanks for the clarification! And now I have an official point where I
can link to, namely this thread on the mailing list. :)

Many thanks,

Ali