Originally posted by: SystemAdmin

Hi,

I'm stumped on a bug (either mine or CPLEX's, but I'm leaning toward the latter). I'm using 12.4.0.0, Java API.
The problem assigns police cars to nodes ("hotspots"). I'm trying Benders decomposition: the master problem
assigns nodes to cars and the subproblem tries to turn those assignments into valid routes. The best way to e
xplain the problem is with some output, so apologies for the long question. First, the preliminary CPLEX output:

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. Warning: Control callbacks may disable some MIP features. Tried aggregator 1 time. Probing time =    0.00 sec. Tried aggregator 1 time. Presolve time =    0.00 sec. Probing time =    0.00 sec. Clique table members: 70. 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.

This verifies that CPLEX is using single threading, so synchronization of threads cannot be the culprit.

&&& Lazy constraint callback entered ============== Master solution ============== === Patrol decisions (hotspot:decision) === Car 0 (patrol time = 480.0) ->  1:0.0 2:0.0 3:0.0 4:0.0 5:0.0 6:0.0 7:0.0 8:0.0 9:0.0 10:0.0 11:0.0 12:0.0 13:0.0 14:0.0 15:0.0 16:0.0 17:0.0 18:0.0 19:0.0 20:0.0 === Car 1 (patrol time = 480.0) ->  1:0.0 2:0.0 3:0.0 4:0.0 5:0.0 6:0.0 7:0.0 8:0.0 9:0.0 10:0.0 11:0.0 12:0.0 13:0.0 14:0.0 15:0.0 16:0.0 17:0.0 18:0.0 19:0.0 20:0.0 === Car 2 (patrol time = 480.0) ->  1:0.0 2:0.0 3:0.0 4:0.0 5:0.0 6:0.0 7:0.0 8:0.0 9:0.0 10:0.0 11:0.0 12:0.0 13:0.0 14:0.0 15:0.0 16:0.0 17:0.0 18:0.0 19:0.0 20:0.0 === Car 3 (patrol time = 480.0) ->  1:0.0 2:0.0 3:0.0 4:0.0 5:0.0 6:0.0 7:0.0 8:0.0 9:0.0 10:0.0 11:0.0 12:0.0 13:0.0 14:0.0 15:0.0 16:0.0 17:0.0 18:0.0 19:0.0 20:0.0 === Car 4 (patrol time = 480.0) ->  1:0.0 2:0.0 3:0.0 4:0.0 5:0.0 6:0.0 7:0.0 8:0.0 9:0.0 10:0.0 11:0.0 12:0.0 13:0.0 14:0.0 15:0.0 16:0.0 17:0.0 18:0.0 19:0.0 20:0.0 ==============

These are print statements I inserted. Decision entries are binary variables. The initial master problem
incumbent, at the root node, predictably assigns no hotspots to any car but thinks each car is patrolling
for a full shift (480 minutes). The lazy constraint callback will reject this.

&&& Solved the subproblem: result = true, status = Optimal ??? Car 0 has alleged time 480.0, actual time 0.0, patrols: [] !!! Rejecting incumbent with value 2400.0 and adding optimality cut. ??? New cut: IloRange  : -infinity <= (1.0*PatrolTime_0 - 480.0*Patrols_H1_0 - 480.0*Patrols_H2_0 - 480.0*Patrols_H3_0 - 480.0*Patrols_H4_0 - 480.0*Patrols_H5_0 - 480.0*Patrols_H6_0 - 480.0*Patrols_H7_0 - 480.0*Patrols_H8_0 - 480.0*Patrols_H9_0 - 480.0*Patrols_H10_0 - 480.0*Patrols_H11_0 - 480.0*Patrols_H12_0 - 480.0*Patrols_H13_0 - 480.0*Patrols_H14_0 - 480.0*Patrols_H15_0 - 480.0*Patrols_H16_0 - 480.0*Patrols_H17_0 - 480.0*Patrols_H18_0 - 480.0*Patrols_H19_0 - 480.0*Patrols_H20_0) <= 0.0 ??? Adding copy of cut ??? Adding copy of cut ??? Adding copy of cut ??? Adding copy of cut

These are print statements in the lazy constraint callback. It was entered, discovered that the incumbent
overestimated patrol time for car 0, and added an optimality cut. The cut basically says you have to patrol
some spot(s) to have any patrol time, and it is indeed violated by the proposed incumbent. Since all cars
look alike, the cut is added once for each car. (I've confirmed separately that each copy of the cut uses
the proper variables for a different car.)

%%%%% Incumbent callback entered ============== Master solution ============== === Patrol decisions (hotspot:decision) === Car 0 (patrol time = 480.0) ->  1:0.0 2:0.0 3:0.0 4:0.0 5:0.0 6:0.0 7:0.0 8:0.0 9:0.0 10:0.0 11:0.0 12:0.0 13:0.0 14:0.0 15:0.0 16:1.0 17:0.0 18:0.0 19:0.0 20:0.0 === Car 1 (patrol time = 480.0) ->  1:0.0 2:0.0 3:0.0 4:0.0 5:0.0 6:0.0 7:0.0 8:0.0 9:0.0 10:0.0 11:0.0 12:0.0 13:0.0 14:0.0 15:0.0 16:0.0 17:1.0 18:0.0 19:0.0 20:0.0 === Car 2 (patrol time = 480.0) ->  1:0.0 2:0.0 3:0.0 4:0.0 5:0.0 6:0.0 7:0.0 8:0.0 9:0.0 10:0.0 11:0.0 12:0.0 13:0.0 14:0.0 15:0.0 16:0.0 17:0.0 18:1.0 19:0.0 20:0.0 === Car 3 (patrol time = 480.0) ->  1:0.0 2:0.0 3:0.0 4:0.0 5:0.0 6:0.0 7:0.0 8:0.0 9:0.0 10:0.0 11:0.0 12:0.0 13:0.0 14:0.0 15:0.0 16:0.0 17:0.0 18:0.0 19:1.0 20:1.0 === Car 4 (patrol time = 480.0) ->  1:1.0 2:0.0 3:0.0 4:0.0 5:0.0 6:0.0 7:0.0 8:0.0 9:0.0 10:0.0 11:0.0 12:0.0 13:0.0 14:0.0 15:0.0 16:0.0 17:0.0 18:0.0 19:0.0 20:0.0 ==============

Still at the root node, CPLEX now has a new incumbent, with each car patrolling one hotspot (#16 for car 0,
..., #1 for car 4). This satisfies the cuts I just added but still overestimates patrol times, so more
optimality cuts are needed. Note, however, that this output comes not from the lazy constraint callback
but from the incumbent callback (which I added solely for debugging purposes -- the bug also occurs when there
is no incumbent callback).

       Nodes                                         Cuts/  Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap         Variable B NodeID Parent  Depth   *     0     0      integral     0     2400.0000     2400.0000        0    0.00%                        0             0 Elapsed real time =   0.02 sec. (tree size =  0.00 MB, solutions = 1)   User cuts applied:  5   Root node processing (before b&c): Real time             =    0.02 Sequential b&c: Real time             =    0.00 ------- Total (root+branch&cut) =    0.02 sec.

CPLEX now accepts the incorrect incumbent. There is no indication that the lazy constraint callback was entered
a second time. The question is, why not?

Thanks,
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

If I understand correctly you observe the following:
1. CPLEX produces an integral solution and invokes the lazy constraint callback with that solution.
2. The callback produces a cut that is violated by the solution CPLEX found. By how much does the solution violate the cut?
3. CPLEX continuous. It again finds an integral solution. That solution does not violate the cut(s) added in step 2. However, CPLEX fails to invoke the lazy constraint callback for this solution and instead immediately invokes the incumbent callback.
In case my description is correct: Can you please double check that you indeed use 12.4? There was a bug in 12.3 that resulted in exactly the above behavior. This bug is supposed to be fixed for 12.4.
If you are indeed on 12.4 then could you please send me a message to daniel(dot)junglas(at)de(dot)ibm(dot)com so that we can check whether the workaround we had for 12.3 does also help in your case (the workaround is kind of complicated).
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> dju358 wrote:
> If I understand correctly

You do.

> you observe the following:
> 1. CPLEX produces an integral solution and invokes the lazy constraint callback with that solution.
> 2. The callback produces a cut that is violated by the solution CPLEX found. By how much does the solution violate the cut?

The constraint looks like z - sum a_i x_i <= b where z is real (value 480 in the incumbent), the x_i are binary (all zero in the incumbent), the a_i are all equal to 480 (as is b).

> 3. CPLEX continuous. It again finds an integral solution. That solution does not violate the cut(s) added in step 2. However, CPLEX fails to invoke the lazy constraint callback for this solution and instead immediately invokes the incumbent callback.

Yes.

> In case my description is correct: Can you please double check that you indeed use 12.4? There was a bug in 12.3 that resulted in exactly the above behavior. This bug is supposed to be fixed for 12.4.

The interactive optimizer opens by claiming to be 12.4.0.0. Of course, I have no way of knowing if it is lying about its age. :-)

> If you are indeed on 12.4 then could you please send me a message to daniel(dot)junglas(at)de(dot)ibm(dot)com so that we can check whether the workaround we had for 12.3 does also help in your case (the workaround is kind of complicated).

Will do.

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: gangulo

What about applying the fixpack to 12.4.0.1? It solves a similar problem, among others http://www-01.ibm.com/support/docview.wss?uid=swg1RS00947
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Yes, that is exactly the bug I had in mind.
Sorry Paul, I did not notice that you are on 12.4.0.0 while the fix is for 12.4.0.1. Can you try and upgrade to 12.4.0.1? If not, we could still try the workaround I found for that bug.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks to both of you for the tip about the fix pack. It seems to have solved the problem, at least in a couple of test cases I just ran.

Daniel: I used the link Gustavo provided, and I'm sure it's the academic version ("-aca-" in the file names, "Academic" in the readme file). That notwithstanding, it requires a license file (which I haven't had for a while). I downloaded the last academic license file, and CPLEX is running again (until that license dies some time next year). Has anyone pointed this out?

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

No, nobody has reported that yet.
I will notify the appropriate people about this issue.
Thanks for reporting it!
#CPLEXOptimizers
#DecisionOptimization