Originally posted by: geffer

I try to solve a problem using branch and cut in the CPLEX. Since I am a newer to CPLEX Callback, I have several questions (maybe very simple for others).
1 I read http://orinanobworld.blogspot.sg/2012/08/user-cuts-versus-lazy-constraints.html and start to know the difference between usercut and lazy constraint, if a cut is a constraint that is not part of the original model and does not eliminate any feasible integer solutions, A user cut is simply a cut added by the user,what's difference by addCut and addusercut? I am always confused by differentiating my constraint.
2 For most of condition the best time to add valid constraint is to treat it as normal constraint, if I need to get a best result, is it necessary to code constraint in cut, normal constraint,user cut and lazy constraint separately to acquire the best performance?

Thx
Corky
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: JorisK

Paul Ruben wrote a nice blog post on the differences and usage of lazy constraints and user cuts:

http://orinanobworld.blogspot.nl/2012/08/user-cuts-versus-lazy-constraints.html

In addition, a good application (programmed in Java), can be found here (applying user cuts and lazy constraints to TSP):

http://rma350.scripts.mit.edu/home/?p=116

Finally, the cplex manual in the installation folder of your cplex has also a section on cuts.

Btw, give the forum search a try.

>> 2 For most of condition the best time to add valid constraint is to treat it as normal constraint, if I need to get a best result, is it necessary to code constraint in cut, normal constraint,user cut and lazy constraint separately to acquire the best performance?

I'm not sure what you are saying here. Valid inequalities do not change the outcome of your MIP formulation. So I'm not sure what you mean by "best result". Here is a copy from the java manual, which probably clarifies your question:

===============
This is the lazy constraint callback class. Extensions of this class implement user-written lazy constraint callbacks. These allow you to add lazy constraint to the problem while the problem is being solved with branch-and-cut search. These lazy constraints may contribute to the model formulation and restrict the feasible region of the problem. By contrast, if a constraint to be added during branch-and-cut search does not change the feasible region of the active model but only strengthens the formulation, it is referred to as a user cut. Such constraints should better be added through IloCplex.UserCutCallback because this allows IloCplex potentially to perform more presolve reductions. It is an error, however, to add lazy constraints by means of a user cut callback.

The idea behind lazy constraints is that the LPs that are solved when the MIP is being solved can be kept smaller when these constraints are not included. IloCplex will, however, include a lazy constraint in the LP as soon as it becomes violated. In other words, the solution computed by IloCplex makes sure that all the lazy constraints that have been added are satisfied.

If you use LazyConstraintCallback, you are free to add cuts that may chop off solutions that are otherwise feasible with respect to the model, in contrast to UserCutCallback. In the case of UserCutCallback, you effectively promise CPLEX that you are not adding cuts that reduce the solution space by the callback.
===============
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

"2 For most of condition the best time to add valid constraint is to treat it as normal constraint, if I need to get a best result, is it necessary to code constraint in cut, normal constraint,user cut and lazy constraint separately to acquire the best performance?"

I felt adding a cut as a normal constraint helped in terms of performance. This is when you do a traditional Benders(separated into master and worker models). When added through callbacks as user and lazy cuts, the performance didn't scale up well compared to smaller test cases. YMMV.

Regards,
Vivek.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I'm not sure I understand your second question, but I'll take a shot. These are my personal choices, based on experience but not research:

1. If I know the constraint at modeling time, and it has a reasonable chance of being binding, it goes into the model as a normal constraint.

2. If I know the constraint at modeling time, but it is unlikely to be binding, it goes into the model as a lazy constraint. This usually occurs when the constraint is part of a large collection of constraints, such as subtour elimination constraints.

3. If the constraint its unknown at modeling time, I ads it in a callback. I explained the difference between user cuts and lazy constraints (as I understand it) in my blog post, and it its discussed in the CPLEX docs, so I won't repeat that here.

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

thanks for reply， I learn a lot from your explain
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: geffer

Dear PaulRubin
What I mean performance is modeling time.
I get your point, however, even the same constraint in user cut, there is still great difference in callback and addusercut directly in modeling time, would you mind to tell why and how to select to add cut by callback or addusercut directly ?

Corky
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

We may be using the phrase "modeling time" differently. I'm using it to mean the time (stage) at which you create the model; I have the feeling you're using it to mean elapsed time solving the model.

I'm not sure there is a foolproof rule for deciding between adding a cut as a constraint (before solving), as a lazy constraint (again before solving), or via a callback. Callbacks add processing overhead (since they are called repeatedly), and certain callbacks (specifically the lazy constraint callback) force CPLEX to turn off features such as dual reductions (and, I think, dynamic search) that might otherwise let it solve the problem faster. On the other hand, adding a large number of constraints slows down the time per iteration. In the case of ordinary constraints, they may also increase the density of the constraint matrix, which can further slow things down.

I gave you my rules of thumb in my previous answer. That's how I initially approach a problem. On a case by case basis, if the solution time seems excessive (and if other tricks to speed things up fail), I may switch to a different approach.

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