Originally posted by: Tulkas

Since I know my problem well, I've decided to implement a few additional dynamical deduction algorithms thanks to a branch callback. Given a node, and current LBs/UBs, I can indeed fix some new bounds. All my variables being booleans, I thus write something like this:

getBranch(newVars_1, newBounds_1, newDirections_1, 0);
getBranch(newVars_2, newBounds_2, newDirections_2, 1);

...

// variables[currentIndex] = 0.0 with respect to the first branch
newVars_1.add(variables[currentIndex]);
newBounds_1.add(0.0);
directions_1.add(IloCplex::BranchDown);

...

// variables[anotherIndex] = 1.0 with respect to the first branch
newVars_1.add(variables[anotherIndex]);
newBounds_1.add(1.0);
directions_1.add(IloCplex::BranchUp);

...

makeBranch(newVars_1, newBounds_1, newDirections_1, getObjValue(), 0);
makeBranch(newVars_2, newBounds_2, newDirections_2, getObjValue(), 0);

It works in fact very well if I do not post any lazy contraint... In this later case, I sometimes have variables whose lower bound is greater than its upper bounds, i.e. lb = 1.0 / ub = 0.0 !

NB:

• My lazyconstraints implements some strict dominance rules and thus delete some feasible integer solutions.
• If I use lazyconstraints only, it works !
• If I use branch callback only, it works !
• If I use both, bounds inconsistency appear...
• I'm not 100% sure this problem comes from either my branch callback or my lazy constraints...

Do you have an idea ?

Thanks a lot !
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Tulkas

Another remark : it perfectly works if my lazy constraints are added as classical constraints, i.e. model.add(IloRange(...)). I may thus have misunderstood lazy constraints.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Tulkas

Please ignore my last post. It does not work so fine finally !
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Do you post the lazy constraints from a callback or do you add them prior to calling solve()?
At which point do you observe the conflicting bounds?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Tulkas

I add them prior to calling solve().

I observe conflicting bounds at the very begining of the branch callback. I just call getLBs(...) and getUBs(...) and check consistency before calling makebranch(...) one or twice.

For the moment, I have substituded cplex.addLazyConstraint(cons) by model.add(cons) and inconsistencies appear more rarely, but still appear ! I mean from an instance to another ;-)

Some recent observation :
1) If I reverse the two callings of makebranch, the problem diseappear... It nevertheless does not convince me !
2) If I turn preprocessing off, calling cplex.setParam(solver.PreInd, 0);, then itt also disappear ! Could it be a problem between presolved variables and problem variables or something like this ?

Thanks a lot !
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

When you do

// variables[currentIndex] = 0.0 with respect to the first branch
newVars_1.add(variables[currentIndex]);
newBounds_1.add(0.0);
directions_1.add(IloCplex::BranchDown);

(which sets ub=0), do you check that CPLEX does not try to do a BranchUp on that variable at the same time (which would set lb=1)? In other words, do you check that currentIndex is not yet contained in newVars_1? getBranch() may have returned an array that already contains this variable. In that case you want to remove CPLEX's branching decision on that variable.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Tulkas

for(int i=0; i < newVars_1.getSize(); ++i)
if(newVars_1[i].getId() == variablescurrentIndex.getId())
std::cout << "PROBLEM !!!";

My prompt is empty :(
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Just to be extra-sure, could you please add something like this right before the call to makeBranch() (and similarly for newVars_2):

std::set<IloInt> mark1;
for (IloInt i = 0; i < newVars_1.getSize(); ++i) {
   IloNumVar v = newVars_1[i];
   if (mark1.find(v.getId()) != std::set<IloInt>::end()) {
      std::cerr << "Duplicate variable " << v << std::endl;
      ::abort();
   }
   else
      mark1.insert(v.getId());
}

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Tulkas

I never reach breakpoints at :
std::cerr << "Duplicate variable " << v << std::endl;
(for both newVars_1 and newvars_2)

Nevertheless ! I might have found !

// I protect variables I might handle through branch callbacks.
cplex.protectVariables(decisionVariables);

It seems to work, even with "lazy constraints implementation".

Could it be right or it is probably "luck" ?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Tulkas

If cplex.protectVariables(decisionVariables); works (I'm refering to my question above). It means that my problems were coming from the fact that I attempt to read variables which were aggegated by presolve algorithms or something like this. In that case, shouldn't I have caught an PresolvedVariableException exception ? I also tried to set IloCplex::PreLinear to 0 without success. I was thinking it let cplex translate variables from the presolved problem to the original problem. Am I wrong ?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

It may indeed be the case that you are trying to branch on variables that have been fixed by presolve. To check that you should check BranchCallbackI::getLB() and BranchCallbackI::getUB() for the respective variable before you add it to newVars_1 or newVars_2. Make sure that those bounds do not conflict with the branching decision you are planning to take.
As far as I can tell makeBranch() will not throw an exception if you branch on a variable that has been fixed by presolve.
PreLinear has nothing to do with the type of model. In Concert all callbacks always operate on the original model (never on the presolved model).
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Tulkas

So it seems to be luck :( I indeed call BranchCallbackI::getLB() and BranchCallbackI::getUB() before any operation. What I retrieve from these methods is corrupted, i.e lb > ub. My deduction algorithms even work ONLY with these bounds.

For instance if x_1 == 1 && x_2 == 0 => x_3 <- 1 (it's naturally much more complicated in reality). I write something like this:

getLBs(lb, variables);
getUBs(ub, variables);
if(lb[x_1] > 1 - EPSILON && ub[x_2] < EPSILON) // if lb > ub, I perform bad deductions ;S
{
newVars.add(x_3);
newBounds.add(1.0);
newDirections.add(BranchUp);
}

To sum up:
1) I use LBs and UBs of current node,
2) I use the branching variables chosen by CPLEX,
=> I update LBs and UBs as if branching was already done with respect to branch 0 and branch 1 independently (I only consider getBranchType() == BranchOnVariable) and try to fix more variables on these branches...
3) I never perform branching up and branching down on the same variables
4) I've checked that I do not perform bad deductions. I compare any deductions to known optimal solutions. If LBs and UBs of this node are compatible with one of these solutions S (this node could lead to S), I compare my deductions to S. I'm therefore sure I'm not implicitely pruning a branch leading to S !
5) I prune nodes when my deductions are conflicting with current fixed variables because it means there is not feasible solutions beyond. Once again, I checked I never prune a node leading to an optimal solution.

What could it be so ?

Thanks !
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Tulkas

For information, what disturbs me about presolved and original variables is in the documentation:

"Protected variables in presolve reductions
Describes the interaction of protected variables and presolve.

A final facility that modifies the set of reductions performed by presolve is the CPXcopyprotected routine. The user provides as input a list of variables in the original problem that should survive presolve (that is, should exist in the presolved model). Presolve will avoid reductions that remove those variables, with one exception. If a protected variable can be fixed, presolve will still remove it from the problem. This command is useful in cases where the user wants to explicitly control some aspect of the branch & cut process (for example, through the branch callback) using knowledge about those variables."
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Tulkas

With a bit more details...

getLBs(lb, variables);
getUBs(ub, variables);
if(lbx_1 > 1 - EPSILON && ubx_2 < EPSILON && )
{

if(ubx_3 < EPSILON)
prune();

if(lbx_3 <= EPSILON)
{
newVars.add(x_3);
newBounds.add(1.0);
newDirections.add(BranchUp);
}

}
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

This code fragment looks wrong:

if(ub[x_3] < EPSILON)
   prune();
 
if(lb[x_3] <= EPSILON)
{
   newVars.add(x_3);
   newBounds.add(1.0);
   newDirections.add(BranchUp);
}

If ub and lb are both 0 for x_3 then you will call prune() and makeBranch() at the same node (which is an error, see documentation of prune()).
Do you check that not both bounds for x_3 are 0? Does the problem persist if you immediately 'return' after calling 'prune()'?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Tulkas

I just forget an "else" when writing my message. I cannot call both makeBranch and prune in my callback.

if(ub[x_3] < EPSILON)
prune();

else if(lb[x_3] <= EPSILON)
{
newVars.add(x_3);
newBounds.add(1.0);
newDirections.add(BranchUp);
}
#CPLEXOptimizers
#DecisionOptimization