Guroubi decides not to apply usercuts during the search?

[CBongiova]

Hello,

I have an MILP which I solve through a branch-and-cut procedure (hence using a callback function). I am printing out the violated valid inequalities and the number of explored nodes during the tree search. I have noticed that often times the console returns the same inequality for a different number of explored nodes, which leads me to suppose that the same usercut is being produced twice and at different nodes (hence affecting performance!).

Is it possible that Gurobi didn't apply the usercut for a "low" violation but it is applying it later for a "higher" violation?

For example, say the constraint is the following:
@usercut(cb, sum(x[path[h],path[h+1]] for h=collect(1:length(path)-1)) <= (length(path)-3)
Where path is a vector containing some node ids.
Then, using node = MathProgBase.cbgetexplorednodes(cb), the console prints out:

Num explored nodes 14.0: the constraint is produced for path [10, 13, 19, 42, 26, 34] with
x_val 3.1328960560421835
Num explored nodes 15.0: the constraint is produced for path [10, 13, 19, 42, 26, 34] with x_val 3.14372170874214

[odow]

Hi @CBongiova,

A couple of comments:

• it's a little hard to help without a minimum working example that demonstrates the problem. Can you share a simple example?
• we've had too many problems like this with "solver-independent" callbacks. Hence, the new version of JuMP in development will require the user to implement solver-specific routines.

In future, please post questions like this to our Discourse site as a first port of call. It has many more people who read and might be able to help.

Thanks for using JuMP!

[CBongiova]

Hi @odow

Thanks so much for your reply and suggestions (and preventively, for your time with the working example)
I have also posted the question to the Discourse site 👍
Too bad for the update for the new version of JuMP: I think one of the major attractives of JuMP (and Julia for the people in OR) is indeed that the syntax does not change among solvers...does this mean that I will have to update the syntax of all my callbacks in near future? Will it remain easy to learn and implement?

Here is a working example (in .txt since I cannot post .jl files):
working_example.txt

The data file:
a3-24-14.85-0.3-FULL.txt

And the function used to read the data file (There is no need to review this code, you can just run it in the main code as this is just to read the data for the test).
readDAT_example.txt

In this working example, I get (for example):

Num explored nodes 315.0 : the constraint is produced for path [4, 47, 12, 29, 36, 28] with x_val 4.66579735844086
Num explored nodes 316.0 : the constraint is produced for path [4, 47, 12, 29, 36, 28] with x_val 4.969837497678187

So it seems like the same constraint was produced multiple times? Is the constraint actually produced at different nodes (is there a way to actually print the current b&b node instead of the number of explored nodes in the callback)?

[odow]

I have also posted the question to the Discourse site

You should edit the discourse post to link to this issue. (Always do this when posting the same question in multiple places.)

Some advice crafting a working example. One of the biggest things to do is make it minimal. From the stackoverflow help:

Minimal – Use as little code as possible that still produces the same problem

The less code people have to wade through, the easier it is to help. I didn't run your code because I don't have Erdos installed, there are lot of files, and there is a lot of things going on. Try to remove as much code as possible so that it still demonstrates the problem.

Question: do you mean to add a lazy constraint or a user cut?

is there a way to actually print the current b&b node instead of the number of explored nodes in the callback?

Not to my knowledge. It is one of the reasons why we are removing solver independent callbacks as they often require solver-specific information.

I think one of the major attractives of JuMP (and Julia for the people in OR) is indeed that the syntax does not change among solvers

The problem is that callbacks are tied to particular solvers. The syntax obscures a lot of problems from users. (See, for example, JuliaOpt/GLPKMathProgInterface.jl#19.)

does this mean that I will have to update the syntax of all my callbacks in near future?

Yes.

Will it remain easy to learn and implement?

You will have to understand the particular quirks of the solver you are using and how it implements callbacks. Here is an example of lazy cuts in Gurobi with MOI (not JuMP). For example, you need to know that you can only add lazy constraints when called from Gurobi.CB_MIPSOL. There will be some nice helper functions from JuMP, but I am unsure what form these will take at present.

[CBongiova]

Hi @odow,

You should edit the discourse post to link to this issue. (Always do this when posting the same question in multiple places.)

Thanks I have added the link to this post on the discourse

Some advice crafting a working example. One of the biggest things to do is make it minimal. From the stackoverflow help:
Minimal – Use as little code as possible that still produces the same problem
The less code people have to wade through, the easier it is to help. I didn't run your code because I don't have Erdos installed, there are lot of files, and there is a lot of things going on. Try to remove as much code as possible so that it still demonstrates the problem.

You can remove the line "using Erdos". Actually you won't need it in the working example. Sorry I forgot to remove it myself.

I have started from a minimal MILP model and kept adding decision variables and constraints until I have encountered the same issue I am experiencing right now. Further reducing the model makes the problem so easy to solve that the issue is not replicated. As for the callback function, I have only kept one valid inequality (which is the one being replicated).

The issue is also data-dependent: With different parameters, the solver would possibly not behave the same way. Reproducing another dataset which creates the same issue in Gurobi would probably be very complicated to do (I have actually just spent one hour and a half trying to come up with an easier dataset which reproduces the same error, so that you don't have to download multiple files...and did not succeed!). That's why I have attached a data file and a simple script to read it.

The code is actually quite simple to be used: Download the attached files, change the path to your local path in the working_example code -- lines 7 and 8, and run. The working example is actually a quite compact MILP model and a very small callback function (reproducing only the user cuts which create the issue)

Question:do you mean to add a lazy constraint or a user cut?
I mean to add a user cut because the constraint does not define the problem but should rather cut an infeasible fractional solution during the search. The problem is that if Gurobi keeps adding the same valid inequality during the search, the model becomes heavier and therefore CPU time increases. This is something that I would like to avoid.

Thank you for all the other information!
I really hope someone will be able to help me on this issue... :(

[mlubin]

I really hope someone will be able to help me on this issue... :(

Since this is a question specific to Gurobi's behavior, you may have more luck asking directly on the Gurobi support forum (https://groups.google.com/forum/#!forum/gurobi).

[mlubin]

Closing since the discussion ended and there's no evidence of a JuMP issue. Feel free to reopen or create a new issue if appropriate. As far as I can tell, the issue is about behavior internal to Gurobi.