Originally posted by: JorisK

Dear,

I have implemented a MIP model (cplex 12.4, Java). The model is a variation on the Price collecting TSP. I have to solve this model relatively frequently, each time with a different objective (constraints remain the same). Hence, instead of rebuilding the entire model, I simply change the objective:

IloLinearNumExpr objExpr=pricingProblem.linearNumExpr();
....
obj.setExpr(objExpr); //obj is an IloObjective

Next, I re-invoke pricingProblem.solve();

One difficulty in the model is subtour elimination. To perform subtour elimination, I have written a LazyConstraintCallback which separates the cuts and adds them to the model. For a single invocation of the MIP model this works great: first the model finds a solution which violates the subtour constraints, next, cuts are generated and added to the model, resulting in a new solution which no longer violates the subtour constraints. However, when I subsequently change the objective and resolve the model, it might happen that the EXACT same cuts are being generated. I checked this behavior by exporting the MIP model and solving it using the interactive solver. Indeed, the solution was in violation with the subtour constraints I generated previously. Are these LazyConstraints somehow lost? It seems that they are still there, but are not being applied for some reason?
Any suggestions on how to troubleshoot this?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: JorisK

Dear,

I did some additional testing: I added a small check to my separator to detect whether it has returned a specific lazy constraint during an earlier invocation. Two tests have been conducted:

Test 1: if a duplicate cut is detected (i.e. the lazy constraint has been generated before), it is not returned again. Result: the MIP solution violates the corresponding subtour constraint.

Test 2: if a duplicate cut is detected, NO new lazy constraint is generated, but the OLD one is returned instead. Result: a correct MIP solution which does not violate the constraints.

I get the impression that the Lazy Constraints I add are somehow 'consumed' when a violation is detected?

Test 3: After solving my MIP model, I change the objective. Next, BEFORE I invoke the solve() method, I re-add all the Lazy Constraints I generated earlier using the addLazyConstraints(myLazyConstraints) function. The result is rather interesting: If I run Test 1 it indeed informs me that it would generate a duplicate constraint. However, even though I do not return any constraints, I still obtain a valid integer solution which does not violate any constraints! So it seems that the LazyConstraintCallback invokes the separator BEFORE it actually checks whether any of the previously generated Lazy Constraints are violated!

I hope this helps to troubleshoot the issue.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I'm not sure when you say "before" if you mean earlier in this call to solve(), or in a previous call to solve().

When you modify the objective function, you effectively create a new model from the perspective of CPLEX. I would expect CPLEX to delete all cuts created in callbacks during the previous solve. Since you are only changing the objective, subtour elimination constraints remain valid, but CPLEX does not know that they are subtour elimination constraints. They're just lazy constraints, and lazy constraints can be based on the objective function (and thus rendered invalid when the objective function changes).

So you should expect to rediscover the subtour constraints each time, unless (as in your third option) you add them to the model between solves. (Cuts added in callbacks are not added to the model; they're held separately.)

I hope that answers your question.

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

I think you already found the answer: What you need to do is what you did in test 3. Like Paul said, the lazy constraints are discarded if you change the model.
A rough outline of separation of lazy constraints at a feasible solution is:

int fractional = 0;
do {
   separateConstraintsFromLazyConstraintPool();
   invokeLazyConstraintCallback();
   if ( numberOfSeparatedConstraints > 0 ) {
     resolve ();
     fractional = updateFractional(); /* Test if new solution is still integral. */
   }
} while (!fractional);

As you can see, there is no resolve() between separation of constraints from the pool and the callback. Hence, if your callback can find constraints that are already contained in the pool then it will find them even though CPLEX has already picked them up from the pool (but has not yet applied them).
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

ADDENDUM: CPLEX will not add the same cut/constraint twice, so it should do no harm (other than wasted CPU cycles) if the callback separates a cut/constraint that is already contained in the the pool. Only one instance of this cut/constraint will be added.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: JorisK

Dear Daniel Junglas & Paul Rubin: as always, thank you for your replies. Glad to see this is not one of my programming errors :)

>Like Paul said, the lazy constraints are discarded if you change the model.
Isn't this a bit strange if only the objective of the model changes? After all (as Paul remarked), the polyhedron over which cplex optimizes doesn't change, so the cuts must still be valid.

>As you can see, there is no resolve() between separation of constraints from the pool and the callback.
Sometimes cut separation can be computationally expensive. Wouldn't it make sense to make the invokeLazyConstraintCallback() depend on the result of separateConstraintsFromLazyConstraintPool() (see code below)? Quite possible, cuts which are already present in the LazyConstraintPool already cut of the current integral solution; separating additional (possibly duplicate) cuts seems quite redundant (and expensive).

-Would it be possible to add the following to the relevant sections of the cplex manual:
-Cuts are removed when the model changes (this should be made more accurate, i.e. when what changes (objective/constraints/constants...?)).
-Your pseudo code sample
-The LazyConstraint callback might find constraints that are already contained in the pool because CPLEX has not applied them yet.

code
int fractional = 0;
do {
separateConstraintsFromLazyConstraintPool();

if(numberOfSeparatedConstraints = 0)
invokeLazyConstraintCallback();

if ( numberOfSeparatedConstraints > 0 ) {
resolve ();
fractional = updateFractional(); /* Test if new solution is still integral. */
}
} while (!fractional);
[/code]
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks, I have made a note to get documentation improved.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: UserCplex

In response to SystemAdmin
 

>>ADDENDUM: CPLEX will not add the same cut/constraint twice, so it should do no harm (other than wasted CPU cycles) if the callback separates a cut/constraint that is already contained in the the pool. Only one instance of this cut/constraint will be added.

 

Hello,

 

I am bumping this up as I am facing a situation where I am going to be using the lazy cut pool.

 

I have a model for which at present, I have a mylazycutcallback() function that exactly separates and adds lazy cuts at candidate integer solutions. Violated lazy cuts are added within this callback function using the following:

 

CPXcutcallbackadd(lp.Env(), cbdata, wherefrom, lprow->num, lprow->rhs[0], lprow->sense[0], lprow->rmatind, lprow->rmatval, CPX_USECUT_FORCE);

From documentation: https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.5.1/ilog.odms.cplex.help/refcallablelibrary/html/functions/CPXcutcallbackadd.html

 

I gather that the usage of CPX_USECUT_FORCE above ensures that further in the Branch and Bound Tree (BBTree) this cut explicitly remains in the LP relaxation.

 

Now, instead of waiting until hitting a candidate integer solution, I am looking to run a heuristic generator of these lazy cuts at different (not necessarily candidate integer) nodes. Below is assuming that populating the lazy cut pool is possible within the tree and not just before a call to CPXmipopt().

My questions are:

 

(1)Is there any suggested callback function within which I should run this heuristic generator of lazy cuts?

(2)Within this heuristic generator, (based on documentation at https://www.ibm.com/support/knowledgecenter/SSSA5P_12.9.0/ilog.odms.cplex.help/refcallablelibrary/mipapi/addlazyconstraints.html), I plan to use the CPXaddlazyconstraints function to populate the identified cuts into the lazy cut pool. Is this the right way to populate the pool?

(3)Because this is a heuristic that is based on the current fractional/integer node solution, the identified lazy cuts need not be violated by the current solution (fractional or integer). So, is there any suggested stopping strategy within a callback? Otherwise, this will run into an infinite loop based on my current understanding.

(4)Because this is a heuristic, the identified lazy cuts can be duplicates of pre-existing cuts that were added to the lazy cut pool somewhere else in the BBTree. Is it more efficient for the user to check this using his own data structures to prevent duplication before calling CPXaddlazyconstraints or is whatever the user does going to be less efficient than optimized CPLEX duplication prevention or space bloat of the lazy cut pool? This is specifically why I quoted the CPLEX respose from the earlier post to the beginning of my post. That is, can the user be guaranteed that he need not do duplication check before calling CPXaddlazyconstraints() since even if a duplicate constraint is added, CPLEX is likely to be more efficient in detecting and discarding it?

(5)

I quote the following from CPLEX documentation:

>>Lazy constraints are only (and always) checked when an integer-feasible solution candidate has been identified, and of course, any of these constraints that turn out to be violated will then be applied to the full model.

If I understand correctly, at a candidate integer solution, the current integer solution is checked against each constraint of the pool, and the violated constraints (say 2 lazy constraints from the pool of currently say 10 constraints) will be added to the model. The size of the pool reduces to 8. What determines whether these 2 added constraints remain in the model or not? In other words, CPXcutcallbackadd() has an int purgeable argument, while CPXaddlazyconstraints() does not. How does CPLEX treat these two types of lazy constraints -- one added via the former function and the other via the latter function -- how are they similar, how are they different? Am I right in assuming that CPXaddlazyconstraints() populates a pool and once a violation of a constraint in this pool is found, the violated cut is added for all remaining LPs encountered in the BBTree even at nodes that are not related to the node at which the cut was found violated ?

 

Thank you.

 

#CPLEXOptimizers
#DecisionOptimization

Hello,
next time, please start a new thread. Continuing on a 7 year old discussion with something that is rather different makes it hard to find things when searching.

Now for your questions:

1. Calling CPXaddlazyconstraints() while the optimization is running is an error. Thus you cannot call this from a callback. You can only call this function before you start the optimization. However, what you can do is to register a lazy constraint callback and a user cut callback. Then store the constraints that your heuristic separates in a global queue and  inject them from the cut callback (or from the lazy constraint callback if they are violated there). Note that injecting lazy constraint from a cut callback is only fine if you additionally have a lazy constraint callback registered (which may be empty but CPLEX needs that to recognize that you potentially inject lazy constraints).
2. Lazy constraints in the static pool indeed have no purgeable flag. CPLEX treats them the way it thinks is best. However, an integer feasible solution presented to a lazy constraint callback should never violate a lazy constraint from the static pool.

#CPLEXOptimizers
#DecisionOptimization