Originally posted by: SystemAdmin

Hi All,

Sorry if this a naive question, but I certainly lack any experience, and documentation isn't helping much with my problem right now. I am trying to solve a problem in which I derive a cut using a separation problem and then need to add this cut thus obtained to the master problem, and derive a new solution and keep doing this until the solution to the master problem satisfies the separation criteria.

I wanted to compare how adding callbacks instead of actual constraints would affect the performance of the algorithm. I wrote a cut callback routine using the macro available in concert, however when I try to use it with my cplex object it is not doing anything, the same cut when added to the model as a constraint works fine, but not as a callback. I am very sure I am doing something wrong. Can someone please explain how can I achieve the desired, that is adding these callbacks as obtained to my master problem. I can't find a way to use these in an iterative manner.

I would really appreciate any help!

Thanks!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

First, while it doesn't matter much at this level of discussion, for future reference it will help if you specify what API you are using (C++, Java, Python, ...). You mentioned a macro, which sounds like the C interface (rather than Concert).

Second, just to confirm, the master problem is a MILP (not an LP)?

Third, do you try to derive new cuts at every node (even if the LP relaxation gives a non-integer solution), or only when an incumbent is found?

Fourth, do you add cuts as local or global cuts in the cut callback? (If they are globally valid, which I suspect to be true, they should be added as global.)

I've used callbacks on discriminant problems, which I suspect is similar to what you're doing. I generate cuts only when an incumbent is found, so I use both an incumbent callback and a cut callback. The incumbent callback tests new incumbents and, if necessary, uses a subproblem to generate a new cut, which is added to a queue in my code. The cut callback (automatically called at every node) checks the queue and, if a cut is queued, removes it from the queue and adds it to the problem.

If you intend to test every node solution, whether integer feasible or not, you can do the testing in the cut callback and add the resulting cut immediately. I believe that will allow you to skip the incumbent callback, but I have not tested this. (The key question is whether the cut callback is called after a heuristic finds a new incumbent and before the incumbent is accepted.)

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi Paul,

I would like to thank you for your prompt response. Regarding the problem, I can provide the following details to the best of my knowledge.

Q1: First, while it doesn't matter much at this level of discussion, for future reference it will help if you specify what API you are using (C++, Java, Python, ...). You mentioned a macro, which sounds like the C interface (rather than Concert).

Ans: I am using C++. I was trying to use ILOCUTCALLBACKn(...) method to implement the cut callback.

Q2: Second, just to confirm, the master problem is a MILP (not an LP)?

Ans: Yes, the master problem is a MILP.

Q3: Third, do you try to derive new cuts at every node (even if the LP relaxation gives a non-integer solution), or only when an incumbent is found?
Ans: I would like to derive new cuts only when an incumbent is found. I am trying to optimize a problem, the formulation of which contains exponential number of constraints. I thus, want to implement these cuts only when the optimal solution to the MASTER_relaxed(n){master problem with n such cuts added} doesn't satisfy the separation criteria, i.e. not feasible for the actual solution set of the original Master problem.

Q4: Fourth, do you add cuts as local or global cuts in the cut callback? (If they are globally valid, which I suspect to be true, they should be added as global.)
Ans: You're right, I want to add these cuts as global, i.e. valid for the entire search tree.

>>> I've used callbacks on discriminant problems, which I suspect is similar to what you're doing. I generate cuts only when an incumbent is found, so I use both an incumbent callback and a cut callback. The incumbent callback tests new incumbents and, if necessary, uses a subproblem to generate a new cut, which is added to a queue in my code. The cut callback (automatically called at every node) checks the queue and, if a cut is queued, removes it from the queue and adds it to the problem.

This is exactly what I intend to do, however I am not really sure where to start reading about these implementations. Could you please provide me some reference or an example that might help!

Thanks again,
Avinash
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Probably a silly question, but after creating the callback did you attach it to your IloCplex instance (cplex.use(my_callback))?

Have you looked at the iloadmipex5.cpp example (in the examples\src\cpp directory of the CPLEX installation)? It uses the same macro you're using to create a cut callback.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Yes, I did use the same example, and I did attach the callback to my cplex instance. I think the problem was that I was passing the expressions to the callback and not the variables, and when I did pass the variables instead the callback did work.

Although now I am stuck with one more thing, that I would like to ask you. Do we always need to create a fresh instance of IloCplex whenever we want to use the callbacks, or is there a way to use the callbacks on already used IloCplex instance, what I mean to say is, can we do the following.

IloCplex cplex(model);
cplex.solve();
cplex.use(MyCallback(.....));
cplex.solve();

Right now it doesn't work for me. Is there a workaround?

Thanks again,
Avinash
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi Paul,

Is it possible for you to provide me with the code you mentioned you used for the discriminant problems, that uses both an incumbent callback and a cut callback. I am sure it can be of great help to me for the understanding of these scenarios.

Thanks,
Avinash
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> avinashbhardwak wrote:

> Is it possible for you to provide me with the code you mentioned you used for the discriminant problems, that uses both an incumbent callback and a cut callback. I am sure it can be of great help to me for the understanding of these scenarios.

Wish I could, but I think that code wound up in the bit recycler. (I punted that project several years ago and have not returned to it.)

I have some library code that uses cut, incumbent and branch callbacks, but (a) it's in Java and (b) it doesn't directly solve the classification problem (although it could be used to do so -- that's why I punted the previous approach). The master problem it solves is a set covering problem. In a classification or minimum infeasible subset application, the binary variables would represent misclassifications or constraint violations, and the subproblem would generate a new set to cover (representing either a set of observations of which at least one must be misclassified, or a set of constraints of which at least one must be violated).

If you want to see that, send an e-mail to rubin <at> msu <dot> edu and ask me for the DynamicSCP code.

Cheers,
Paul
Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> avinashbhardwak wrote:
> Although now I am stuck with one more thing, that I would like to ask you. Do we always need to create a fresh instance of IloCplex whenever we want to use the callbacks, or is there a way to use the callbacks on already used IloCplex instance, what I mean to say is, can we do the following.
>
> IloCplex cplex(model);
> cplex.solve();
> cplex.use(MyCallback(.....));
> cplex.solve();
>
> Right now it doesn't work for me. Is there a workaround?

Along with adding the callback, try invoking cplex.clearCuts(). That works for me in Java. Probably clearUserCuts and a few other things would as well, but I have not tested them. It is a bit odd that use(...) does not cause CPLEX to reinitialize the problem.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I got a definitive answer on this from Ed Klotz of IBM, which I'm posting here for posterity.

First, CPLEX does not scrap a previous solution and restart if you change parameters between calls to solve(), which makes sense since parameters do not affect the underlying model. CPLEX treats addition or removal of callbacks as a form of parameter change. (I'm not sure I buy the logic, since callbacks can modify the model by adding lazy constraints, but so be it.) So the observed behavior is intentional.

Second, the "official" way to reset the model between solves is to turn off the advanced start indicator (PreInd) before the second call to solve().

Third, if the intent of the second call to solve() (after adding the cut callback) is to winnow solutions, it might be preferable to use the solution pool and then filter it.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Paul,

Thanks for the help and explanations. This is really helpful for me.

Thanks again.
#CPLEXOptimizers
#DecisionOptimization