Originally posted by: open_ball

Hi,

 

I am trying to understand the logic of Lazy constraint callback function for a Benders implementation. Suppose I have a framework that I ensure feasibility when solving the master problem meaning that I only generate optimality cuts. Does the Lazy constraint callback function work in the following way?

 

1) Start solving the master problem and stop at the first integer solution.

2) Go to sub problem and get an optimality cut.

3) Add the cut into master problem and continue the solution process where you left in (1) 

 

The reason for asking this question is that Lazy constraint callback function is not active in OPL and I am trying to implement it myself. Is my interpretation correct? If not, what am I missing?

 

For instance, when I implement the steps explained above in my model, I stop with the first integer and generate a cut. However, in the second iteration, the algorithm gets stuck. If anyone can assist me, I'd be really appreciated. 

 

#CPLEXOptimizers
#DecisionOptimization

It probably does not matter much, what the lazy constraint callback does (although it looks like you got that right) but what your code in OPL does.

First of all, if you say the true objective value 14650 then how can the lower bound in the first iteration be 25600? That is already bigger than the optimal solution?

Second, if you obtain a lower bound that is too high in the second iteration then either something with your cut is wrong or you compute the lower bound in a wrong way. You would have to show a lot more details for us to help you.

Finally, how do you add the cut? Do you add this as a new constraint? I am not exactly sure but I think that in OPL there is no way to add a cut in a way that will not make CPLEX discard the current search tree. This is because adding a new row is a model modification and thus requires solving from scratch.

By the way, CPLEX ships with example opl/examples/opl/models/TravelingSalesmanProblem/tsp.mod and this basically implements a lazy constraint callback in OPL: it solves the traveling salesman problem by generating subtour elimination constraints on the fly. You may want to use this code as boiler plate.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: open_ball

Hi Daniel,

 

Thanks for your answer

 

First, I attached my code that I use as a toy example and it's pretty easy to understand and debug. It's not my main model, however, the code respond me in the same way. 

 

1) "First of all, if you say the true objective value 14650 then how can the lower bound in the first iteration be 25600? That is already bigger than the optimal solution?"

 

I guess since I solve MP only once, there is no need to keep track of LB and UB anymore.

 

 

2)"Second, if you obtain a lower bound that is too high in the second iteration then either something with your cut is wrong or you compute the lower bound in a wrong way. You would have to show a lot more details for us to help you."

 

I already attached my code, but as I explained in the first question, I debugged my code. It's a very small scale problem and everything seems correct. When I do not set insollim as 1 (this implies that I interrupt the solution process) , everything seems correct. I have two different codes for the same problem. The first one regenerates the MP with every cut (i.e., all the constraint set is reformed from scratch) and the second one does not regenerate the MP (i.e., I only update the empty constraints). Both of them give me the same cuts and are able to reach optimum for a small scale problem. 

 

3)"Finally, how do you add the cut? Do you add this as a new constraint? I am not exactly sure but I think that in OPL there is no way to add a cut in a way that will not make CPLEX discard the current search tree. This is because adding a new row is a model modification and thus requires solving from scratch."

 

Normally I was using the same method with TSP example, but Alex recommended me using the empty constraint framework with which I create a set of empty constraints, Then, I update the coefficient and bounds at every iteration. Doing so prevents me from regenerating the MP. Also, this enables me to continue the branch and cut process where I left at the first iteration. 

 

4) "By the way, CPLEX ships with example opl/examples/opl/models/TravelingSalesmanProblem/tsp.mod and this basically implements a lazy constraint callback in OPL: it solves the traveling salesman problem by generating subtour elimination constraints on the fly. You may want to use this code as boiler plate."

 

I am aware of TSP example. Previously, I was adding my constraints in the same way. However, doing so requires to re-generate the MP at every iteration. Then, I am not able to continue the branch and cut process ( that means I am not able to capture what Lazy constraint callback function does).

 

Please let me know if you need any other detail. 

#CPLEXOptimizers
#DecisionOptimization

When you export the LP files for the initial master solve and subsequent master solves via masterCplex.exportModel(), do the files look different? Do they look how they are supposed to look?

#CPLEXOptimizers
#DecisionOptimization