Originally posted by: Ibrahim_Capar

Dear all,

I have a maximization problem with following structure:

Max cX
subject to:
   AX + DY <=b
    X>=0, Y >=0 and integer.

I coded the problem using C++ and CPLEX 12.7.1. I followed the structure in ``ilobendersatsp.cpp." For CPLEX settings, I have following commands:

cplex.setParam(IloCplex::Param::Parallel, 1);
cplex.setParam(IloCplex::Param::Preprocessing::Presolve, IloFalse);
cplex.setParam(IloCplex::Param::Threads, 1);
cplex.setParam(IloCplex::Param::MIP::Strategy::Search, IloCplex::Traditional);
cplex.use(BendersLazyCallback(env, ...)); //ILOLAZYCONSTRAINTCALLBACK

Below, I provide cuts generated for a small example:

(1)      Obj: 330     BestSol:330     Sol: [-0, -0, 1, -0, 1, -0, -0, -0]
(2)      Obj: 30     BestSol:165.3     Sol: [1, 1, 0, 0, 0, 0, 0, 0]
(3)      Obj: 30     BestSol:165.3     Sol: [1, 1, 0, 0, 0, 0, 0, 0]
(4)      Obj: 150     BestSol:165.3     Sol: [0, 1, 1, -0, -0, -0, -0, -0]
(5)      Obj: 100     BestSol:165.3     Sol: [0, 1, 1, -0, -0, -0, -0, -0]
(6)      Obj: 150     BestSol:150.521     Sol: [0, 1, -0, -0, 1, -0, -0, -0]
(7)      Obj: 125     BestSol:150.521     Sol: [0, 1, -0, -0, 1, -0, -0, -0]
(8)      Obj: 140     BestSol:146.875     Sol: [1, 0, 1, -0, 0, -0, -0, -0]
(9)      Obj: 140     BestSol:140     Sol: [1, 0, 0, -0, 1, -0, -0, -0]
(10)      Obj: 130     BestSol:130     Sol: [1, 0, 1, -0, 0, 0, 0, 0]

Notice that (2) and (3) are identical solutions, but lazy constraint callback is invoked twice.  Also in (4) and (5), for the same solution, there are two different objectives.

My question is this. What parameters should I include so that the callback is only invoked when the master problem is optimal?

Thank you in advance,
Ibrahim

Originally posted by: dominiqs81

If you want to separate Benders cuts only on optimal master solutions you don't need a callback: just solve the master with .solve(), query the optimal solution, separate the cut, add it to master and repeat.

P.S. how do you query the solution value that you report with "Obj:"?

Originally posted by: Ibrahim_Capar

If I add the constraint after solve() method, the problem needs to restart from the beginning. Which is not desirable. I want to add the cut just before the master problem ends while it is in the memory.

You can get the current objective value at a given node by using getObjValue().  getBestObjValue() will return the currently best known bound.

Originally posted by: dominiqs81

If you want to solve a model with Benders with a single tree (i.e. without restarts) then you need to separate each candidate integer solution found by the solver via a callback. Having the lazy callback be called only on the optimal master solution is not correct (and not possible).

Originally posted by: Ibrahim_Capar

''you need to separate each candidate integer solution found by the solver via a callback.''

That is my question. How can I do that? Which callback I need to use? 

Originally posted by: dominiqs81

You need to use the lazy callback, exactly as you did in the original post. Do you get wrong answers out of that?

Originally posted by: Ibrahim_Capar

I guess I did not understand your comment completely. 

Do you mean I have two options? These are:

Option one:

Solve the master problem to optimality. Then, generate the cut and resolve the problem the beginning with an additional constraint. 

Option two:

Use the lazycallback, but you have no control when the lazy constraint is called. 

PS: Implementation of lazy callback finding the optimal solution to the original problem. So no problem there.

Originally posted by: dominiqs81

Yes, you have the two options as you describe, and you implemented the latter.

Originally posted by: Ibrahim_Capar

Would we have better control with new cut method that comes with CPLEX 12.8?
 

I've experimented with the new "generic" cuts, and I don't think there's anything there that will help you.

The real question here is not one tree v. "classic" (solve to optimality, then cut) Benders. It's why you're apparently seeing repeats of the same proposed incumbent when you are running single-threaded. (This would not be a huge shock with multiple threads, as threads are not notified when other threads spit up Benders cuts.)

First, just to be clear, have you checked that the second and third calls to the callback passed in exactly the same master solution? It's a little hard to tell from your output, although I assume so.

Second, did you check that the cut generated at step (2) is actually violated by the incumbent (by more than rounding tolerance)?

Third, when you invoke add() in the lazy constraint callback, do you use the single argument version or the two argument version (second argument being the cut management parameter). If it's the two argument version, might you have made the cut purgeable? If yes, and if (2) and (3) occur some distance apart, maybe the cut from (2) was purged before (3) happened? (Seems unlikely, but then so does the output.)

Originally posted by: Ibrahim_Capar

Paul,
Thank you for your feedback. I added `thisEnv.getImpl()' and `getSolutionSource()'. `thisEnv.getImpl()' always returns the same value, thus, I assume it is the same master problem.  That is said, after adding `getSolutionSource()', I noticed that cuts (2) and (3) in the original post are due to heuristic incumbent solutions. Hence I turned off the heuristic in  CPLEX (cplex.setParam(IloCplex::Param::MIP::Strategy::HeuristicFreq, -1);.)

The table above presents incoming solutions to the lazy callback after the implementation. The value '111' in `getSolutionSource()' is CPX_CALLBACK_MIP_INCUMBENT_NODESOLN. Solutions 1, 2, 3 are added when the master problem is optimal hence they are good. Solutions 4, 5, 6 are not the optimal solution for the master problem. The solution 7 is.

In addition, I still continue to observe identical solutions invoking the lazy callback, i.e., solution 5 and 6. Moreover, cuts generated for solution 4, 5, 6 are not violated by the solution 3 or solution 7. Similarly, solutions 4, 5, 6 do not violate any constraints.

Finally, I use `add()' with a single parameter, hence, CPLEX should not purge any constraint.  

Thanks again,
Ibrahim

Ibo,

I don't think I'm understanding everything you said above. First, what do you mean by solutions 1, 2, 3 and 7 being optimal but 4-6 not being optimal in the master? Are you referring to their objective values v. the best current bounds? If so, I'm not sure what significance that has.

Second, are you adding feasibility cuts (in which case I assume solutions 2 and 3 were infeasible), optimality cuts, or a mix of the two? If it's a mix, it would help to know which solutions triggered optimality cuts and which triggered feasibility cuts.

Third, were any of those solutions accepted by the callback, or did it generate a cut for every one of them?

Paul

Originally posted by: Ibrahim_Capar

Paul,

In a traditional Bender's decomposition, the subproblem is invoked after solving the master problem to the optimality. In this example, I wanted to emphasize that solutions 1, 2, 3, and 7 were the optimal solution when the lazy callbacks invoked. Overall, this information does not have much value.

All the cuts generated are optimality cuts. (The problem is always feasible.) At each iteration, the lazy callback creates an optimality cut. 

Thanks,

Ibrahim

it might be informative to print out the cut generated each time, and in particular to look at the cut generated at step 5 to see whether solution 6 (identical to 5) actually violates it (by more than EpRHS).

Originally posted by: Ibrahim_Capar

The cuts generated after solution 5 is not violated by solution 6. Specifically, the added constraint is in LHS<=RHS format, and solution 6 satisfies the constraint at equality, LHS = RHS.

So if solutions 5 and 6 are identical, as indicated in your table (same binary vector, same objective value), then solution 5 does not violate the cut -- which means the cut is incorrect. The value of the surrogate variable (the variable in the master problem that represents cX) should be larger than the actual value of cX for that Y, and also larger than what the cut allows the surrogate to be for that Y. Check the coding of the cut generator.

Originally posted by: VKV7_Anulark_Naber

I implemented Benders' optimality cuts as lazy constraints (only) following the example "BendersATSP2.java" and I also encountered the same problem as Ibrahim. The same lazy constraints were added to the root node 4 times without branching and finally gave an optimal integer solution which I know for sure that it was not feasible wrt lazy constraints.

By debugging my Java code, the first cut was correct, but it did not cut off the first candidate, because the same candidate still came back the second time and yielded the same cut again.

To further check if the cut was correct, I manually copied the first cut and added to the exported master.lp, fix the corresponding variables to those of the first candidate, and solved it using cplex interactively. It turned out that the candidate violated the cut, because the modified model was infeasible. However, it was not the same result given by cplex API.

Are there explanation to that? Am I missing something here? I would appreciate any help. Thanks in advance.

It is expected that you may have to separate the same cut more than once, especially when the incumbent came from a heuristic or when using multiple threads.

There are situations in which CPLEX cannot store the cut you separated for technical reasons. It of course still rejects the incumbent but it may come back with the same incumbent again.

Do you get correct results if you keep separating the same cut? Or do you get incorrect results even in that case?

Originally posted by: VKV7_Anulark_Naber

OK. But it seems to me that the heuristic algorithm appears to find the same incumbent again and again, while ignoring the previous incumbent that was rejected. See output 1 below.

When I changed HeuristicFreq to -1, no incumbent was found, and the final solution is infeasible, for no lazy constraints were found. See output 2 below.

With another implementation as BendersATSP.java, it worked fine. What is the difference between the two implementations.

--------------------------output 1 -------------------------------------

Lazy constraint(s) or lazy constraint callback is present.
    Disabling dual reductions (CPX_PARAM_REDUCE) in presolve.
    Disabling non-linear reductions (CPX_PARAM_PRELINEAR) in presolve.
Tried aggregator 1 time.
MIP Presolve eliminated 49 rows and 22 columns.
MIP Presolve modified 14 coefficients.
Reduced MIP has 278 rows, 165 columns, and 815 nonzeros.
Reduced MIP has 164 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.62 ticks)
Candidate Objective 29.5
Subproblem Objective 56.07272727272727
IloRange  : 20.303496503496497 <= (1.0*eta - 35.769230769230774*x_11_8 + 35.769230769230774*y_11_8 - 31.0*y_10_10 + 31.0*x_10_10 - 31.0*y_10_7 + 31.0*x_10_7 - 31.0*y_10_6 + 31.0*x_10_6 - 31.0*y_10_5 + 31.0*x_10_5 - 31.0*y_10_4 + 31.0*x_10_4 - 31.0*y_10_3 + 31.0*x_10_3 - 31.0*y_10_2 + 31.0*x_10_2 - 77.5*y_9_10 + 77.5*x_9_10 - 77.5*y_9_9 + 77.5*x_9_9 - 41.730769230769226*y_9_8 + 41.730769230769226*x_9_8 - 77.5*y_9_7 + 77.5*x_9_7 - 77.5*y_9_6 + 77.5*x_9_6 - 77.5*y_9_5 + 77.5*x_9_5 - 77.5*y_9_4 + 77.5*x_9_4 - 35.769230769230774*y_8_10 + 35.769230769230774*x_8_10 - 35.769230769230774*y_8_9 + 35.769230769230774*x_8_9 - 35.769230769230774*y_8_7 + 35.769230769230774*x_8_7 - 35.769230769230774*y_8_6 + 35.769230769230774*x_8_6 - 35.769230769230774*y_8_5 + 35.769230769230774*x_8_5 - 35.769230769230774*y_8_4 + 35.769230769230774*x_8_4 - 35.769230769230774*y_8_3 + 35.769230769230774*x_8_3 - 77.5*y_7_9 + 77.5*x_7_9 - 41.730769230769226*y_7_8 + 41.730769230769226*x_7_8 - 77.5*y_7_7 + 77.5*x_7_7 - 77.5*y_7_6 + 77.5*x_7_6 - 77.5*y_7_5 + 77.5*x_7_5 - 77.5*y_7_4 + 77.5*x_7_4 - 77.5*y_7_3 + 77.5*x_7_3 - 155.0*y_4_9 + 155.0*x_4_9 - 119.23076923076923*y_4_8 + 119.23076923076923*x_4_8 - 155.0*y_4_7 + 155.0*x_4_7 - 155.0*y_4_6 + 155.0*x_4_6 - 155.0*y_4_5 + 155.0*x_4_5 - 155.0*y_4_4 + 155.0*x_4_4 - 155.0*y_4_3 + 155.0*x_4_3 - 155.0*y_4_2 + 155.0*x_4_2 - 42.27272727272727*y_3_9 + 42.27272727272727*x_3_9 - 6.503496503496502*y_3_8 + 6.503496503496502*x_3_8 - 42.27272727272727*y_3_6 + 42.27272727272727*x_3_6 - 42.27272727272727*y_3_5 + 42.27272727272727*x_3_5 - 42.27272727272727*y_3_4 + 42.27272727272727*x_3_4 - 42.27272727272727*y_3_3 + 42.27272727272727*x_3_3 - 42.27272727272727*y_3_2 + 42.27272727272727*x_3_2 - 42.27272727272727*y_3_1 + 42.27272727272727*x_3_1) <= infinity
Candidate Objective 29.5
Subproblem Objective 56.07272727272727
IloRange  : 20.303496503496497 <= (1.0*eta - 35.769230769230774*x_11_8 + 35.769230769230774*y_11_8 - 31.0*y_10_10 + 31.0*x_10_10 - 31.0*y_10_7 + 31.0*x_10_7 - 31.0*y_10_6 + 31.0*x_10_6 - 31.0*y_10_5 + 31.0*x_10_5 - 31.0*y_10_4 + 31.0*x_10_4 - 31.0*y_10_3 + 31.0*x_10_3 - 31.0*y_10_2 + 31.0*x_10_2 - 77.5*y_9_10 + 77.5*x_9_10 - 77.5*y_9_9 + 77.5*x_9_9 - 41.730769230769226*y_9_8 + 41.730769230769226*x_9_8 - 77.5*y_9_7 + 77.5*x_9_7 - 77.5*y_9_6 + 77.5*x_9_6 - 77.5*y_9_5 + 77.5*x_9_5 - 77.5*y_9_4 + 77.5*x_9_4 - 35.769230769230774*y_8_10 + 35.769230769230774*x_8_10 - 35.769230769230774*y_8_9 + 35.769230769230774*x_8_9 - 35.769230769230774*y_8_7 + 35.769230769230774*x_8_7 - 35.769230769230774*y_8_6 + 35.769230769230774*x_8_6 - 35.769230769230774*y_8_5 + 35.769230769230774*x_8_5 - 35.769230769230774*y_8_4 + 35.769230769230774*x_8_4 - 35.769230769230774*y_8_3 + 35.769230769230774*x_8_3 - 77.5*y_7_9 + 77.5*x_7_9 - 41.730769230769226*y_7_8 + 41.730769230769226*x_7_8 - 77.5*y_7_7 + 77.5*x_7_7 - 77.5*y_7_6 + 77.5*x_7_6 - 77.5*y_7_5 + 77.5*x_7_5 - 77.5*y_7_4 + 77.5*x_7_4 - 77.5*y_7_3 + 77.5*x_7_3 - 155.0*y_4_9 + 155.0*x_4_9 - 119.23076923076923*y_4_8 + 119.23076923076923*x_4_8 - 155.0*y_4_7 + 155.0*x_4_7 - 155.0*y_4_6 + 155.0*x_4_6 - 155.0*y_4_5 + 155.0*x_4_5 - 155.0*y_4_4 + 155.0*x_4_4 - 155.0*y_4_3 + 155.0*x_4_3 - 155.0*y_4_2 + 155.0*x_4_2 - 42.27272727272727*y_3_9 + 42.27272727272727*x_3_9 - 6.503496503496502*y_3_8 + 6.503496503496502*x_3_8 - 42.27272727272727*y_3_6 + 42.27272727272727*x_3_6 - 42.27272727272727*y_3_5 + 42.27272727272727*x_3_5 - 42.27272727272727*y_3_4 + 42.27272727272727*x_3_4 - 42.27272727272727*y_3_3 + 42.27272727272727*x_3_3 - 42.27272727272727*y_3_2 + 42.27272727272727*x_3_2 - 42.27272727272727*y_3_1 + 42.27272727272727*x_3_1) <= infinity
Candidate Objective 29.5
Subproblem Objective 56.07272727272727
IloRange  : 20.303496503496497 <= (1.0*eta - 35.769230769230774*x_11_8 + 35.769230769230774*y_11_8 - 31.0*y_10_10 + 31.0*x_10_10 - 31.0*y_10_7 + 31.0*x_10_7 - 31.0*y_10_6 + 31.0*x_10_6 - 31.0*y_10_5 + 31.0*x_10_5 - 31.0*y_10_4 + 31.0*x_10_4 - 31.0*y_10_3 + 31.0*x_10_3 - 31.0*y_10_2 + 31.0*x_10_2 - 77.5*y_9_10 + 77.5*x_9_10 - 77.5*y_9_9 + 77.5*x_9_9 - 41.730769230769226*y_9_8 + 41.730769230769226*x_9_8 - 77.5*y_9_7 + 77.5*x_9_7 - 77.5*y_9_6 + 77.5*x_9_6 - 77.5*y_9_5 + 77.5*x_9_5 - 77.5*y_9_4 + 77.5*x_9_4 - 35.769230769230774*y_8_10 + 35.769230769230774*x_8_10 - 35.769230769230774*y_8_9 + 35.769230769230774*x_8_9 - 35.769230769230774*y_8_7 + 35.769230769230774*x_8_7 - 35.769230769230774*y_8_6 + 35.769230769230774*x_8_6 - 35.769230769230774*y_8_5 + 35.769230769230774*x_8_5 - 35.769230769230774*y_8_4 + 35.769230769230774*x_8_4 - 35.769230769230774*y_8_3 + 35.769230769230774*x_8_3 - 77.5*y_7_9 + 77.5*x_7_9 - 41.730769230769226*y_7_8 + 41.730769230769226*x_7_8 - 77.5*y_7_7 + 77.5*x_7_7 - 77.5*y_7_6 + 77.5*x_7_6 - 77.5*y_7_5 + 77.5*x_7_5 - 77.5*y_7_4 + 77.5*x_7_4 - 77.5*y_7_3 + 77.5*x_7_3 - 155.0*y_4_9 + 155.0*x_4_9 - 119.23076923076923*y_4_8 + 119.23076923076923*x_4_8 - 155.0*y_4_7 + 155.0*x_4_7 - 155.0*y_4_6 + 155.0*x_4_6 - 155.0*y_4_5 + 155.0*x_4_5 - 155.0*y_4_4 + 155.0*x_4_4 - 155.0*y_4_3 + 155.0*x_4_3 - 155.0*y_4_2 + 155.0*x_4_2 - 42.27272727272727*y_3_9 + 42.27272727272727*x_3_9 - 6.503496503496502*y_3_8 + 6.503496503496502*x_3_8 - 42.27272727272727*y_3_6 + 42.27272727272727*x_3_6 - 42.27272727272727*y_3_5 + 42.27272727272727*x_3_5 - 42.27272727272727*y_3_4 + 42.27272727272727*x_3_4 - 42.27272727272727*y_3_3 + 42.27272727272727*x_3_3 - 42.27272727272727*y_3_2 + 42.27272727272727*x_3_2 - 42.27272727272727*y_3_1 + 42.27272727272727*x_3_1) <= infinity
Candidate Objective 29.5
Subproblem Objective 56.07272727272727
IloRange  : 20.303496503496497 <= (1.0*eta - 35.769230769230774*x_11_8 + 35.769230769230774*y_11_8 - 31.0*y_10_10 + 31.0*x_10_10 - 31.0*y_10_7 + 31.0*x_10_7 - 31.0*y_10_6 + 31.0*x_10_6 - 31.0*y_10_5 + 31.0*x_10_5 - 31.0*y_10_4 + 31.0*x_10_4 - 31.0*y_10_3 + 31.0*x_10_3 - 31.0*y_10_2 + 31.0*x_10_2 - 77.5*y_9_10 + 77.5*x_9_10 - 77.5*y_9_9 + 77.5*x_9_9 - 41.730769230769226*y_9_8 + 41.730769230769226*x_9_8 - 77.5*y_9_7 + 77.5*x_9_7 - 77.5*y_9_6 + 77.5*x_9_6 - 77.5*y_9_5 + 77.5*x_9_5 - 77.5*y_9_4 + 77.5*x_9_4 - 35.769230769230774*y_8_10 + 35.769230769230774*x_8_10 - 35.769230769230774*y_8_9 + 35.769230769230774*x_8_9 - 35.769230769230774*y_8_7 + 35.769230769230774*x_8_7 - 35.769230769230774*y_8_6 + 35.769230769230774*x_8_6 - 35.769230769230774*y_8_5 + 35.769230769230774*x_8_5 - 35.769230769230774*y_8_4 + 35.769230769230774*x_8_4 - 35.769230769230774*y_8_3 + 35.769230769230774*x_8_3 - 77.5*y_7_9 + 77.5*x_7_9 - 41.730769230769226*y_7_8 + 41.730769230769226*x_7_8 - 77.5*y_7_7 + 77.5*x_7_7 - 77.5*y_7_6 + 77.5*x_7_6 - 77.5*y_7_5 + 77.5*x_7_5 - 77.5*y_7_4 + 77.5*x_7_4 - 77.5*y_7_3 + 77.5*x_7_3 - 155.0*y_4_9 + 155.0*x_4_9 - 119.23076923076923*y_4_8 + 119.23076923076923*x_4_8 - 155.0*y_4_7 + 155.0*x_4_7 - 155.0*y_4_6 + 155.0*x_4_6 - 155.0*y_4_5 + 155.0*x_4_5 - 155.0*y_4_4 + 155.0*x_4_4 - 155.0*y_4_3 + 155.0*x_4_3 - 155.0*y_4_2 + 155.0*x_4_2 - 42.27272727272727*y_3_9 + 42.27272727272727*x_3_9 - 6.503496503496502*y_3_8 + 6.503496503496502*x_3_8 - 42.27272727272727*y_3_6 + 42.27272727272727*x_3_6 - 42.27272727272727*y_3_5 + 42.27272727272727*x_3_5 - 42.27272727272727*y_3_4 + 42.27272727272727*x_3_4 - 42.27272727272727*y_3_3 + 42.27272727272727*x_3_3 - 42.27272727272727*y_3_2 + 42.27272727272727*x_3_2 - 42.27272727272727*y_3_1 + 42.27272727272727*x_3_1) <= infinity
Probing time = 0.02 sec. (0.51 ticks)
Tried aggregator 1 time.
Reduced MIP has 278 rows, 165 columns, and 815 nonzeros.
Reduced MIP has 164 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.43 ticks)
Probing time = 0.00 sec. (0.52 ticks)
Clique table members: 624.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.00 sec. (0.23 ticks)

Root node processing (before b&c):
  Real time             =    0.22 sec. (3.79 ticks)
Parallel b&c, 8 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    0.22 sec. (3.79 ticks)

------------------------------ output 2 -----------------------------

Sorry, this looks indeed like a problem but I am not clear about your setup. Are you using a generic callback or a LazyConstraintCallback? Or a different callback in the two cases? In case you use the generic callback, which contexts do you have enabled?

For output2 it clearly seems wrong that no callback is invoked although there is an incumbent.

For output1 I am not clear: you have rejected all candidate solutions, so no incumbent is expected. Did CPLEX stop due to some limit or did it stop and claim the problem infeasible? In the second case, is the model feasible if you explicitly add the separated lazy constraint to the model?

Originally posted by: VKV7_Anulark_Naber

I am using a generic callback only with both outputs. Output 1 is with the default HeuristicFreq and Output 2 is with the HeuristicFreq of -1.

I'm using the same class and method as in "BendersATSP2".So as the contexts:          

         final BendersCallback cb = new BendersCallback(x, y, numThreads, project, eta);
           long contextmask = IloCplex.Callback.Context.Id.Candidate
              | IloCplex.Callback.Context.Id.ThreadUp
              | IloCplex.Callback.Context.Id.ThreadDown;
           master.use(cb, contextmask);
 

In  BendersCallback, a Benders' cut is generated if sub is solved to optimality and if (sub.getObjValue() - FUZZ > context.getCandidateObjective()). if the cut is not null, then   

context.rejectCandidate(cut);

In both outputs, cplex stopped and claimed that an optimal solution has been found with 29.5.

Previously I implemented Benders' cuts using LazyConstraintCallback and it worked fine. The optimal integer solution should be 32.0 and not 29.5 as given in these outputs. I did not report the output, because it took sometime to find an optimal solution. This solution was also confirmed with the full model (without decomposition).
 

It smells like a bug but I cannot reproduce this here. Whatever I tried, callback behavior was always correct. Can you share the offending code? If not here then maybe with daniel(dot)junglas(at)de(dot)ibm(dot)com?

Originally posted by: VKV7_Anulark_Naber

After debugging it again in details, I just found out that my last subproblem was infeasible. Since callback does nothing for infeasible SP, cplex terminated for it thought it has found an optimal solution. So, that was my mistake.

Other than repeated cuts in the preprocessing phase, cplex now gave me the correct optimal solution. So, it has nothing to do with the incorrect result. Thanks for spending time with it.

I have then another question. When the objective value of SP = that of the candidate, the candidate is then an integer feasible point. Here, I printed out those solutions: the first number is the obj. value an integer feasible point just found and the second one is of the incumbent.

new integer feasible solution 33.19892473118279 33.604166666666664
new integer feasible solution 33.19892473118279 33.604166666666664
new integer feasible solution 32.47619047619048 32.998696145124725
new integer feasible solution 32.47619047619048 32.998696145124725
new integer feasible solution 32.19074074074074 32.476190476190446
new integer feasible solution 32.19074074074074 32.476190476190446

- here a new solution is found with 32.19 but it was not stored as an incumbent just yet (shown in the next line).
new integer feasible solution 32.0 32.476190476190446
new integer feasible solution 32.0 32.476190476190446 

- My question is: when would the incumbent of the master problem be updated?

Possibly a silly question (which won't stop me): In your callback, do start with if statements or a switch to execute different logic depending on why the callback was called? Your context mask includes Candidate (which is when you would normally use a lazy constraint callback), ThreadUp and ThreadDown. I was wondering if the cut generation code gets executed on ThreadUp, which I'm pretty sure would be a mistake.

Originally posted by: VKV7_Anulark_Naber

Here is the code which I follow the example BendersATSP2.java

       // setup
       if (context.inThreadUp()) {
          subs[threadNo] = new Benders2(project);
          return;
       }

       // teardown
       if (context.inThreadDown()) {
          subs[threadNo] = null;
          return;
 

From debugging, ThreadUp and ThreadDown will not generate cuts.
 

Originally posted by: VKV7_Anulark_Naber

Now, I am coming back to the issue of incumbents once again. This was posted last year but was not replied.

The followings are the output from the generic callback for Benders. I used a warnstart "heuristic" which gave the first incumbent, and so on. 

------------------------------------

The lines reporting a better incumbent found are from the java code below (adapted from BendersATSP2.java). Since the lines seem to be printed twice, I would like to make sure that my further actions will not be repeated, wasting runtimes. My questions are:

1. Why is the incumbent not updated the first time (this is a one-thread run)? Daniel once replied that the incumbent may not be stored immediately, what not? When cut is null, an integer feasible solution is found. Shouldn't a better solution be stored as incumbent?

2. Would the subproblem be solved repeatedly in order to get to those two line prints?

3. Can I avoid the repetition?

4. What does  context.rejectCandidate(cut); do beside adding cut as a lazy constraint?

Any clarifications would be appreciated. Thank you. 

------------------------------ 

        …

        }

           … further actions...

        }

This unforunately is a know issue. Currently it may indeed happen that the callback is invoked twice for the same incumbent candidate (provided it is not rejected by the first callback invocation). The reason for this is technical, internal, and cannot be avoided at the moment: for each incumbent candidate there is a long chain of tests for feasibility. One of these tests is not aware of the fact that a previous test already checked the candidate with the callback and thus invokes the callback again. Unfortunately, there is no way for you to tell whether it is the same incumbent or not. Inside CPLEX there is no additional overhead, CPLEX does not resolve a sub-problem or anything. It still checks the same vector. The only overhead comes from your callback because it has to check the same vector twice.

I increased the internal priority of this issue getting fixed.

context.rejectCandidate(cut) rejects the incumbent and adds any cuts that were provided. It should not do anything else.

Originally posted by: VKV7_Anulark_Naber

That does not sound so bad. Thank you very much., Daniel.