Originally posted by: Frops

Dear all,

I am implementing Lazy Constraints with callback ILOLAZYCONSTRAINTCALLBACKn, but I have problems because I obtain optimal solutions that do not fullfil some Lazy constraints.

In the callback definition, I search for a violated lazyconstraint and add it to the model.

I keep track of this cuts that are added. My guess would be that the last time that cplex enters the callback, it would not find any violated cut, so the feasible solution would be the optimal. But that is not happening, the last enter to the callback, I do find a violated cut, and add it, next step optimal solution is found.

I have checked and I think I am sure the cut found is violated fot the solution proposed.

I think to actually debug the code, it would be useful to have a way to extract the lazy constraints that are added to the model (something similar to cplex.exportModel()), which I have read it does not work with added cuts in the callback. 

I checked this post: https://www.ibm.com/developerworks/community/forums/html/topic?id=11e0b4c4-0c98-4601-b4fd-4840114bdaab

To discard the thread-safe problem, I set  cplex.setParam(IloCplex::Threads,1);, even I think my callback would be thread safe.

Is that enough?

Any other suggestions?

Thanks in advanced,

Setting IloCplex::Threads to 1 should eliminate any thread-safety problems. If you problem reproduces in single-threaded mode then it is a good idea to debug in single-threaded mode.

Can you check whether the solution returns as optimal was ever presented in a callback invocation? Or is this a solution that the callback never saw?

By the way, which version of CPLEX do you use?

One thing that may help debugging this:

Since you are using C++ you can make use of templates. If you implement your separation routine as a template, then you can use it from the callback as well as from top-level for the supposedly optimal solution. This allows you to check easily whether the solution proposed by CPLEX violates any lazy constraint.

Here is a code skeleton for this (untested but should work):

#include <iostream>
#include <ilcplex/ilocplex.h>

// This is the separation function.
// It is implemented as a template so that it can be invoked to separate
// a current solution from a callback as well as a solution claimed as
// optimal by IloCplex.
// The argument 'v' is either a callback instance or an IloCplex instance
// (basically it can be anything that provides a ::getValue() method).
template<typename T>
IloRange separate(T *v, IloNumVarArray x)
{
   // The callback separates one very simple constraint
   //    x[0] <= 1.0
   // If the constraint is violated, the function returns the violated
   // constraint. If the constraint is not violated then the function
   // returns an empty constraint.
   if ( v->getValue(x[0]) > 1.1 )
      return IloRange(v->getEnv(), -IloInfinity, x[0], 1.0);
   else
      return IloRange();
}

ILOLAZYCONSTRAINTCALLBACK1(MyCallback, IloNumVarArray, x) {
   IloRange r = separate(this, x);
   if ( r.getImpl() ) {
      // Found a violated constraint -> add it.
      add(r);
   }
}

int
main(void)
{
   IloEnv env;
   IloModel model(env);
   IloNumVarArray x(env); x.add(IloNumVar(env, 0, 1));
   IloCplex cplex(model);

   cplex.use(MyCallback(env, x));
   cplex.solve();

   IloRange r = separate(&cplex, x);
   if ( r.getImpl() )
      std::cerr << "Solution violates a lazy constraint!" << std::endl;

   env.end();
}

Originally posted by: Frops

Dear DanielJunglas,

Thanks very much for your guidance.

• My CPLEX version is: 12.6.
• I'm working in a single-threaded mode
• I have implemented your suggestion with templates
  • The results show that the optimal solution returned by cplex.solve() contains violated lazy constraints. That should not be possible, right?
• I now will try to check if the optimal solution returned was ever presented in the callback invocation before.

Any comment or suggestion is very appreciated.

Thanks again,

You are right, this should not happen. Two things:

1. Are you aware of the fact that you may have to separate the same constraint multiple times? In other words, if you separate a lazy constraint in your callback then it may happen (although it is quite unlikely) that later the callback is presented a solution that again violates that constraint and you have to separate that constraint again. How exactly are you separating your constraints? If you are just looking them up in a table and if the lookup skips over constraints that were found to be violated then this may be your issue.
2. Note that the constant term in a lazy constraint's linear expression should be zero, i.e., if 'range' is the constraint you add then range.getExpr().getConstant() should be 0. Can you double check that this is the case for your constraints?

Originally posted by: Frops

Dear DanielJunglas,

Thanks again. 

My latest updates are:

1. I checked and the solution returned as optimal was presented before at the callback invocation. Also, I think that that should not be...
2. I checked and cplex always enters the callback with a feasible solution (never with unbounded LP)
3. I foced IloCplex::CutManagement purgeable=UseCutForce, so I avoid CPLEX purging some added lazy constraints

Regarding your questions:

1. I do not have a lookup table. I do have a condition that I checked again each time, if it is not fulfilled, I can build a new lazy constraints. So, that should not be a problem. I would add the same constraint again and again, if necessary.
2. I was not aware of this condition, I am going to check immediately. 

Thanks a lot for your help.

Best,

Originally posted by: Frops

Continuing the answer:

2. Note that the constant term in a lazy constraint's linear expression should be zero, i.e., if 'range' is the constraint you add then range.getExpr().getConstant() should be 0. Can you double check that this is the case for your constraints?

I was not aware of this condition, I have just checked. 

I needed to slightly change the code: 'r' is my constraint.

IloExpr rexpr=IloExpr(r.getExpr()); 

rexpr.getConstant()

And the constant term of the lazy constraint is always zero.

Continue with my debugging. 

Thanks again,

One more thing to check: By how much does the solution violate your lazy constraints? Are the constraints violated significantly or are they violated only by a small epsilon?

Originally posted by: Frops

Dear DanielJunglas,

Thanks for your help.

I do impose that constraints are violated significantly, an epsilon of 0.2.

I have slightly modified how I do find lazy constraints. I was being more demanding than needed.

Now: In some instances I get that the returned optimal solution was already explored and sometimes not.

Continuing my debbug.

Thanks again,

Sorry, I have no more ideas what could go wrong here. Could you provide a minimal code sample reproducing the issue and either post that here or send it to daniel(dot)junglas(at)de(dot)ibm(dot)com?

Unless you already tried that, you could also check whether the problem goes away when switching to the most recent version of CPLEX.

Originally posted by: nlp7

For archiving purposes let me just mention a similar problem :

During a lazy callback I was trying to fix some binary variables. This cannot be done with the add method as equality constraint, e.g. add(binary == 0.0), as my optimal solution was violating the fixations. Instead I had to write the constraint as inequality to work.

That seems odd. Did you check for binary!=0 in every invocation of the callback or did you assume that once you added binary==0 all solutions passed to the callback would satisfy this condition?

Originally posted by: Frops

Dear Daniel,

Thanks for your suggestions. 

I am sorry, but I must say it was my mistake.

Debugging the code, I finally discovered that at some given cases I found a violated lazy constraint, but I was adding an implementation of that constraint with an error, that the solution was already satisfying.

Sorry for the inconveniences, and thanks for your help.

Originally posted by: nlp7

I just checked the final optimal solution of the problem, and it was clearly violating the lazy cut (`binary` value was 1.0).

After I changed the cut to `add(binary <= 0.0)` it worked (meaning that in my final optimal solution the value of the `binary` was 0.0).

Seemed weird to me as well, that is why I posted it.