Originally posted by: SystemAdmin

Hi all,

I am trying to solve a problem with a similar procedure as the one you used in BendersATSP.java. In my code, I am using the following commands to define the callback:

...
model.use(new PathLazyConsCallback(cplex, z, u));
...

public static class PathLazyConsCallback extends IloCplex.LazyConstraintCallback {
...
System.out.println(pathConstraint);
add(pathConstraint);
}

I am also using:

cplex.setParam(IloCplex.BooleanParam.PreInd, false);
cplex.setParam(IloCplex.IntParam.Threads, 1);
cplex.setParam(IloCplex.IntParam.MIPSearch, IloCplex.MIPSearch.Traditional);
cplex.setParam(IloCplex.IntParam.Reduce, 0);

Basically, PathLazyConsCallback triggers a sequence of shortest path problems (SPP), it finds several cuts and then, it add those to the model as lazy constraints. So far, I have performed several tests and it seems to be adding the cuts.

I have the following problem, though:

I am solving an instance with an integer optimal solution = 105 (I know this because I also solved it using a different formulation). What is happening is that CLPEX finds an integer solution at the root of the B&B tree with an objective value of 40. I am guessing that it is possible, since at the beginning of the B&B tree the PathLazyConsCallback procedure hasn't been called, so none of the lazy constraints has being included. It is giving me the following output:

Nodes Cuts/
Node Left Objective IInf Best Integer Best Node ItCnt Gap Variable B NodeID Parent Depth

• 0+ 0 40.0000 27 ---

0 0 0.0000 40 40.0000 0.0000 27 100.00%

After this, it triggers the callback, solves the SPP, finds the cuts and it adds the cuts. The output that I get is something like this:

Cut test:

cut found:

---

1, 19, 3
IloRange : -2.0 <= 1.0*u1,3 - 1.0*z1 - 1.0*z19 - 1.0*z3 <= infinity

cut found:

---

1, 14, 4
IloRange : -2.0 <= 1.0*u1,4 - 1.0*z1 - 1.0*z14 - 1.0*z4 <= infinity

cut found:

---

1, 6, 7
IloRange : -2.0 <= 1.0*u1,7 - 1.0*z1 - 1.0*z6 - 1.0*z7 <= infinity
So far so good. The problem is that I think CPLEX is keeping 40.000 as the best integer solution, even though it is infeasible. Therefore, it is cutting all the other branches by bound if the solutions of those have an objective larger that 40 (most of those branches have larger solutions as their feasible sets are smaller due to the lazy constraints), and hence it is returning a final solution that is not feasible.

I would like to know if you have any ideas that could help

Thanks a lot

Cheers

--Jose.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

The output lines

Nodes                                         Cuts/ 
   Node  Left     Objective  IInf  Best Integer     Best Node   ItCnt     Gap         Variable B NodeID Parent  Depth
 
*     0+    0                           40.0000                     27     --- 
      0     0        0.0000    40       40.0000        0.0000       27  100.00%

tell that CPLEX has found a solution with objective function value of 40 and this solution was accepted. The callback invocations you see are for subsequent integer feasible solutions.
Are you sure that your callback was not invoked for the solution with objective function value 40? Is it possible that the callback was invoked but did not find any violated cut? If you add something like

System.out.println("Callback invoked");

as first line to the callback's main() method, do you see any output from the callback before this line appears in the output

*     0+    0                           40.0000

What version of CPLEX do you use?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

This is what I get:

Clique table members: 170.
MIP emphasis: balance optimality and feasibility.
MIP search method: traditional branch-and-cut.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 0.00 sec.

Nodes Cuts/
Node Left Objective IInf Best Integer Best Node ItCnt Gap Variable B NodeID Parent Depth

• 0+ 0 40.0000 27 ---

0 0 0.0000 40 40.0000 0.0000 27 100.00%
Callback invoked

So What I see is that it is invoking the callback after the integer solution is found

I am using version 12.1.0
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi,

I tried everything I can but I cannot manage to make CPLEX do the callback for the first node. This is what I am getting:


Clique table members: 170.
MIP emphasis: balance optimality and feasibility.
MIP search method: traditional branch-and-cut.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 0.00 sec.

Nodes Cuts/
Node Left Objective IInf Best Integer Best Node ItCnt Gap Variable B NodeID Parent Depth



• 0+ 0 40.0000 27 ---

0 0 0.0000 40 40.0000 0.0000 27 100.00%
Callback invoked


I honestly don't know what to try now. Any suggestions?

Thanks
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

This might be a bug in version 12.1. Could you export your model to a SAV file (cplex.exportModel("model.sav")) and post it here? If you don't want to post it in public could you send it to daniel(dot)junglas(at)de(dot)ibm(dot)com? Please also specify as detailed as possible what kind of computer you are using.
To work around or fix the problem I see too possibilities:
1. Upgrade to a more recent version of CPLEX, like 12.3 or 12.4.
2. In addition to the lazy constraint callback register an incumbent callback. That should be called for this early solution. In the incumbent callback run the same separation algorithm. If the separation algorithm finds a violated cut then reject the incumbent. The incumbent callback does not allow you to add the cut to the model but you may store it in a global list and pull it from that list the next time the lazy constraint callback is invoked. From the lazy constraint callback you can then add the cut.
Does the incumbent callback get invoked on this initial solution on which the lazy constraint callback is not invoked?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Obviously, another workaround would be to disable heuristics. Maybe, heuristic solutions are not that important for solving your models and you can live with it...

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi all,

Thanks for your comments. I ran the code in my personal computer which has a newer version of CPLEX and it worked perfectly!. Apparently, as you mentioned, it was a bug in the old version. Gosh, it took me forever to finally get this. Thanks a lot!.

I still have another question. It is more of a functionality question of the user cuts. For me it is still not clear what is the main difference between the LazyConstraintCallback and the UserCutCallback. I read somewhere that one of those is applied only when an integer solution is found, and the other is applied at each node. Am I correct? In which cases is better to use lazy callbacks rather than cut callbacks?

Thanks again.

-Jose
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

The definition is:
A lazy constraint may cut off integer feasible solutions.
A (user) cut may only cut off fractional solutions but must not cut off integer feasible solutions.
So a lazy constraint callback is explicitly allowed to add constraints that cut off integer feasible solutions.

The cut callback is invoked at each node while the lazy constraint callback is invoked only when an integer feasible solution is found. If your separated constraints may cut off integer feasible solutions then you should use a lazy constraint callback, otherwise a cut callback may suffice.
#CPLEXOptimizers
#DecisionOptimization