Originally posted by: toths

We implemented a delayed constraint generation algorithm using CPLEX Concert Technology. We followed this approach because the size of the class of constraints that we had for a 0-1 programming problem was enormous. As a result, generating them prior to optimization was extremely time-consuming. Moreover, these constraints were very "lazy". In the delayed constraint generation algorithm, the constraints are created "on the fly" only if violations occur at nodes that have the potential to produce an optimal solution. Violations are found by a detection algorithm that also creates the inequalities to prevent the violations. The new inequalities are added to the problem as global cuts. While the cutting plane algorithm works fine, it is not as fast as we had expected given our experience of using this family of inequalities as "lazy constraints" in CPLEX. While the lazy constraint approach does not eliminate the burden of generating all the inequalities upfront, it speeds up the solution process by one order of magnitude for our problem instances. The number of lazy constraints applied are typically in the range of 0.01-1% of the full set. This, I thought could mean that if we used the delayed constraint generation approach, we could cut formulation time (which is basically the run time for the detection algorithm) by 2-4 magnitudes in addition to cutting the solution time by one magnitude. This did not happen for some reason after we implemented the approach in CPLEX. One of the reasons appears to be that the delayed constraint generation approach generates many more constraints than what is applied via the lazy constraint approach for the very same problem. How can that be? Is there a difference in the behavior of the lazy constraints vs. the delayed constraint generation method that I am not aware of (apart from that the former requires the entire constraint pool to be identified upfront whereas the latter doesn't)?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

One major difference between lazy constraints and a lazy constraint callback (in which you generate the lazy constraints on the fly) is that the latter is not compatible with dynamic search, which is automatically disabled if control callbacks are used. This could be one part of the performance degradation that you observe.

But you also mentioned that the number of constraints added through your callback is much larger than the number of lazy constraints that CPLEX would add if the constraints were given upfront. This is strange. CPLEX inspects the lazy constraint table at the same time when it calls the lazy constraint cut callback. So, there should be no difference. One source of a difference could be the tolerances. During regular cut separation for fractional x vectors, CPLEX only adds a lazy constraint if it is violated by at least 0.1. For integer solutions, CPLEX adds a lazy constraint if it is violated by at least the feasibility tolerance (which is 1e-6 by default). Maybe, you are always generating cuts in your lazy constraint callback if they are violated by just a small amount, even if the x vector in question is fractional.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: toths

Thanks again for a very helpful response. I attached two node logs (complied in one text file), as requested, that might help you identify if it is the disabling of dynamic search or something else that causes the problem. The text file starts with the logs that correspond to the Lazy run. The logs of the Lazy Cut Callback run are separated by a ********************START********** remark. As you can see both approach solved the problem to a target gap of 0.05%. The Lazy approach took 18.19 seconds whereas the Lazy Cut Callback took 9375.91 seconds to reach this gap. The former used 10, the latter used 541 cuts. On average (n=200), the Lazy Cut Callback applied 5.41 times more cuts than the Lazy approach. The max factor was 54.1 and the min was 1.39. This is, of course, not to say that the Cut Callback was slower overall. If both formulation and solution times are considered, the Cut Callback is somewhat faster in most problems. The problem is with this "somewhat" because we expected that it would perform 100-10,000 times faster than the Lazy approach.

I am somewhat confused to hear that there is a possibility that a cut callback is triggered even if the x vector is fractional at a node. My understanding was that CPLEX handled these triggers internally: the callback would be triggered only if CPLEX found an integer-feasible solution with an objective function value exceeding that of the incumbent node. Otherwise, there is no chance that the node in question can provide an optimal solution. Am I missing something? We did not realize that the user had the ability to control when a cut callback is triggered.

The tolerances can well explain the problem. But again, we did not know that we could control this. Can one relax the feasibility tolerance only for the cut callback and leave it at default for the regular constraints?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

First of all, you are using opportunistic parallel mode. This means that two runs of the same binary with the same parameter settings on the same problem data can produce different paths through the search tree and hence very different performance (even though the final objective value will be the same).
I guess you have explicitly set the "threads" parameter to 4, which will implicitly switch to opportunistic parallel. If you want to have deterministic parallel runs (which might be slightly slower but give reproducible results), you also need to set the "parallel mode" parameter to 1.

Indeed, the run with lazy constraints is using dynamic search, while the run with a lazy constraint callback is using traditional branch-and-cut. This is no surprise, as control callbacks are not compatible with dynamic search.
This may or may not explain the big difference in run-time. You can simply find out whether this is the case by using traditional branch-and-cut for your lazy constraint approach: just set the "MIPSearch" parameter to CPX_MIPSEARCH_TRADITIONAL.

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> Tobias Achterberg wrote:
> First of all, you are using opportunistic parallel mode. This means that two runs of the same binary with the same parameter settings on the same problem data can produce different paths through the search tree and hence very different performance (even though the final objective value will be the same).
> I guess you have explicitly set the "threads" parameter to 4, which will implicitly switch to opportunistic parallel. If you want to have deterministic parallel runs (which might be slightly slower but give reproducible results), you also need to set the "parallel mode" parameter to 1.
>
> Indeed, the run with lazy constraints is using dynamic search, while the run with a lazy constraint callback is using traditional branch-and-cut. This is no surprise, as control callbacks are not compatible with dynamic search.
> This may or may not explain the big difference in run-time. You can simply find out whether this is the case by using traditional branch-and-cut for your lazy constraint approach: just set the "MIPSearch" parameter to CPX_MIPSEARCH_TRADITIONAL.
>
> Tobias

Based on these logs, I believe that dynamic search vs. traditional branch and cut is the primary
contributor to the big difference in run time. However, I see a few other aspects of these runs
that may contribute as well:

1) These runs depend heavily on heuristics for solutions. Each feasible solution with a + sign
suffixed to the node number at which the solution was found indicates that heuristics, not branching,
found a solution. Given their heuristic nature, changes in the path of the branching can affect
the heuristics. In both your runs, I only saw heuristically found solutions.

2) The runs are to a finite MIP gap rather than too optimality. While the second run still would have been slower, the results would have been much different if you had set the MIP gap to .0008 instead of .0005; the second run would have finished in about 4 minutes. Particularly when combined
with heuristics, setting to an arbitrary MIP gap can increase performance variability on a model
if the optimizer is configured so that the two runs don't follow the same path.
With this in mind, as a test you might want to try running to optimality with heuristics disabled,
along with Tobi's recommendation to do both runs with traditional branch and cut. While you
probably won't want to use these settings in your final production runs, this should help you
better assess whether the difference in performance involves the lazy constraint callback.

Ed
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: toths

I am aware of the opportunistic nature of parallel processing. I am also aware of the fact that many, if not most, of the solutions are found via heuristics rather than branch-and-bound. Finally, I know that setting a target optimality gap can have a huge impact on relative solution times. However, I have to stress that we solved 206 problems. Among these, there wasn't one where the number of constraints applied by the Lazy Cut Callback did not exceed, by far, the number of constraints applied by the Lazy approach. Solving the problems to 0 gaps is not an option because only 8 of the 206 can be solved to proven optimality within reasonable time frames (i.e., in a few days).

The source of our problem could be something that I had just found out: we were using IloCplex.CutCallback instead of IloCplex.LazyConstraintCallback. The trigger mechanism is totally different for the two since in one case the cuts never change the integral feasible region and in the other they potentially do. While CPLEX can trigger a cut callback liberally, it has to trigger the lazy constraint callbacks every time an integer feasible solution candidate is found. One would think that using the cut callback by mistake would lead to less, and not more constraints, and that the objective function value would be super-optimal.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: toths

Quick update: Changing the IloCplex.CutCallback to IloCplex.LazyConstraintCallback did not change the number of constraints applied or the speed for a few test problems.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

This is expected.
How LazyConstraintCallback and UserCutCallback operate is a little confusing: In C callable library there is no lazy-constraint callback. There only is a cut-callback. Both, LazyConstraintCallback and UserCutCallback, map to this single cut-callback.
Using lazy constraint requires you to tweak some presolve settings, using user cuts requires you to tweak some (other) presolve settings (see the user manual). Using LazyConstraintCallback or UserCutCallback in Java just wraps around the C cut-callback and performs the required presolve setting tweaks for you. Apart from that there is no difference in the two callbacks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I don't know if you have the time for that but you may want to try a technique that Paul Rubin has advertised several times on this Forum.
The idea is to use an IncumbentCallback together with a LazyConstraintCallback. In addition, you will need a global queue of separated lazy constraints which is initially empty.
In the IncumbentCallback you check the incumbent solution offered by CPLEX and separate lazy constraints for it. If you do not find any violated lazy constraints then you just accept the incumbent. Otherwise you put all separated lazy constraints into the global queue.
In the LazyConstraintCallback you do not separate constraints as you did before. Instead you just pick constraints from the global queue and add these constraints.
This has the potential to generate much fewer constraints.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: toths

As per your suggestions, we checked if the extra cuts in the LazyConstraintCallback could be caused by the disabling of dynamic search. We solved 4 problems to optimality with both the ordinary Lazy approach and with the LazyConstraintCallBack. We set the thread limit to 1, switched off the heuristics and switched off the dynamic search for the Lazy approach. The number of cuts generated by the LazyConstraintCallback is still much higher than that of the ordinary Lazy. It was 71 cuts vs. 28 in the first, 39 vs. 12 in the second, 30 vs. 15 in the third and 14 vs. 4 in the fourth problem. Can we conclude that the "strange" behavior is not caused by the disabling of dynamic search? Our next step is going to be to check if the IncumbentCallback would help. Any comments on tolerances?

BTW, the search does not appear to be deterministic even if only one thread is used and the heuristics are switched off. Solving the exact same problem to optimality twice on the same machine, same resources etc w/o heuristics and w/o parallel processing still leads to slightly different search paths...
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

That the search on one thread is not deterministic is very suspicious. Are you sure about that? Is it possible that something is wrong with your callback that causes the non-deterministic behavior?
How big is your code and how big is your example? Could you share a small example that exhibits the non-deterministic behavior (I think you still have my email address in case you do not want to post the stuff here)? I really do not see how a single-threaded run can be non-deterministic.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> dju358 wrote:
> I really do not see how a single-threaded run can be non-deterministic.

Could the second run be hot-starting from the first one?

/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

Not in this case. I think we resolved that issue offline: There was no non-deterministic behavior. The different log files were produced on different machines and therefore different log files are expected.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: toths

Yes, this has been resolved. I thought that the logs were from the same machine but they weren't. Sorry.
#CPLEXOptimizers
#DecisionOptimization