Originally posted by: revolt

Hi,

I am using CPLEX 12.4 (Linux64) with Java and I want to solve a model with lazy constraints. The lazy constraints are introduced into the model be using only the incumbent callback and the the branch callback and I am using only one thread.

At node 0 CPLEX returns 11 times the same incumbent solution, even though I reject it each time. After the 11th rejection the branch callback is called, so that I can exclude the unwanted incumbent.

Is this normal behavior that CPLEX returns the same incumbent solution multiple times?

Enclosed you find a small example program and the output of the program:

Tried aggregator 1 time. MIP Presolve eliminated 0 rows and 2 columns. Reduced MIP has 6 rows, 14 columns, and 18 nonzeros. Reduced MIP has 3 binaries, 0 generals, 0 SOSs, and 0 indicators. Presolve time =    0,00 sec. Warning: Control callbacks may disable some MIP features. Probing fixed 1 vars, tightened 0 bounds. Probing time =    0,00 sec. Clique table members: 2. MIP emphasis: balance optimality and feasibility. MIP search method: traditional branch-and-cut. Parallel mode: none, using 1 thread. Root relaxation solution time =    0,00 sec. incumbCbk @ Node0. ( 1 0 0 1 0 5005 0 52 0 0 0 18 60 0 0 13 ) = vals  /  reject. Nodes                                         Cuts/  Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap         Variable B NodeID Parent  Depth 0     0        8,0400     0                      8,0400        4 incumbCbk @ Node0. ( 1 0 0 1 0 5005 0 52 0 0 0 18 60 0 0 13 ) = vals  /  reject. incumbCbk @ Node0. ( 1 0 0 1 0 5005 0 52 0 0 0 18 60 0 0 13 ) = vals  /  reject. incumbCbk @ Node0. ( 1 0 0 1 0 5005 0 52 0 0 0 18 60 0 0 13 ) = vals  /  reject. incumbCbk @ Node0. ( 1 0 0 1 0 5005 0 52 0 0 0 18 60 0 0 13 ) = vals  /  reject. incumbCbk @ Node0. ( 1 0 0 1 0 5005 0 52 0 0 0 18 60 0 0 13 ) = vals  /  reject. incumbCbk @ Node0. ( 1 0 0 1 0 5005 0 52 0 0 0 18 60 0 0 13 ) = vals  /  reject. incumbCbk @ Node0. ( 1 0 0 1 0 5005 0 52 0 0 0 18 60 0 0 13 ) = vals  /  reject. incumbCbk @ Node0. ( 1 0 0 1 0 5005 0 52 0 0 0 18 60 0 0 13 ) = vals  /  reject. incumbCbk @ Node0. ( 1 0 0 1 0 5005 0 52 0 0 0 18 60 0 0 13 ) = vals  /  reject. incumbCbk @ Node0. ( 1 0 0 1 0 5005 0 52 0 0 0 18 60 0 0 13 ) = vals  /  reject. branchCbk @ Node0... branched 0     2        8,0400     1                Local Cut: 1        4                                 0             0 Elapsed real time =   0,01 sec. (tree size =  0,00 MB, solutions = 0) incumbCbk @ Node2. ( 1 0 0 1 0 4992 0 0 104 0 60 0 8 0 0 0 ) = vals  /  accept. branchCbk @ Node2... 

do nothing *     1     0      integral     0        8,0400        8,0400        7    0,00%                 X      1      0      1

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: revolt

PS: If I a pass the zero-start solution (all binaries equal 0), then the branch callback is not called at all. If I want to use lazy constraints, do I always need to implement a LazyConstraintCallback or is it sufficient to implement the Incumbent and BranchCallback?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

What you observe is expected. If you just reject an incumbent there is nothing that prevents CPLEX from finding the same incumbent again. If you want to avoid seeing the same incumbent again you need to inject a lazy constraints that cuts off the incumbent you don't want to see again.
Note that incumbents may not only be produced my nodes for which the relaxation is integral. Heuristics may also find feasible solutions and therefore invoke the incumbent callback. And this is what presumably happens during your root node solve. Several heuristics run during the root node and it seems as if they find the same incumbent over and over again, thereby invoking the incumbent callback multiple times before invoking the branch callback for the first time.
If you want to stick with incumbent and branch callback only then you can try to disable heuristics (set parameter CPX_PARAM_HEURFREQ to -1). If you do this then the incumbent callback should only be invoked for nodes for which the relaxation is integral.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: revolt

Thanks for the fast answer!

I have a second question about the example from above. If I give a start solution to CPLEX, then the branch callback will never be called. Thus I can not cut off the rejected incumbent solution by creating two branches that exclude this solution. After I have rejected one and the same incumbent solution for several times, CPLEX simply stops and returns the start solution, even though there exists a better solution (where only one of the continuous variables need to be modified).

Why is the branch callback not called at all? I always thought, that the branch callback should be called at least whenever the node LP is integral and I rejected the integral solution.

As this seems to be false, I guess that I have to implement a lazy constraint callback and can not stick with only incumbent+branchckb. In my case such a lazy cut would be in the best case a face of the convex hull of the conjunction of the feasible region of the branches that I want to create.

(Enclosed you find a minimal example where the above described behavior occurs.)

Sincerely, Johannes Müller
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

When I run your code I get the following output:

incumbCbk @ startSolution.  /  accept 1 of 1 MIP starts provided solutions. MIP start 
'm1' defined initial solution with objective 0.0000. Tried aggregator 1 time. MIP Presolve eliminated 0 rows and 2 columns. Reduced MIP has 6 rows, 14 columns, and 18 nonzeros. Reduced MIP has 3 binaries, 0 generals, 0 SOSs, and 0 indicators. Presolve time =    0.00 sec. Warning: Control callbacks may disable some MIP features. Probing fixed 1 vars, tightened 0 bounds. Probing time =    0.00 sec. Clique table members: 2. MIP emphasis: balance optimality and feasibility. MIP search method: traditional branch-and-cut. Parallel mode: none, using 1 thread. Root relaxation solution time =    0.00 sec.   Nodes                                         Cuts/  Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap         Variable B NodeID Parent  Depth   *     0+    0                            0.0000                      4     --- incumbCbk @ Node0. ( 1 0 0 1 0 5005 0 52 0 0 0 18 60 0 0 13 ) = vals  /  reject. 0     0        8.0400     0        0.0000        8.0400        4     --- incumbCbk @ Node0. ( 1 0 0 1 0 5005 0 52 0 0 0 18 60 0 0 13 ) = vals  /  reject. incumbCbk @ Node0. ( 1 0 0 1 0 5005 0 52 0 0 0 18 60 0 0 13 ) = vals  /  reject. 0     0        8.0400     0        0.0000        0.0000        4    0.00%                        0             0 Elapsed real time =   0.01 sec. (tree size =  0.00 MB, solutions = 1)   Root node processing (before b&c): Real time             =    0.00 Sequential b&c: Real time             =    0.00 ------- Total (root+branch&cut) =    0.00 sec.

As you can see, the incumbent callback accepts the MIP start solution. The MIP start solution has objective function value 0. At the end of the root node the dual bound is also 0. So at the end of the root node primal and dual bound are the same and the problem is solved to optimality: no reason to branch.
How can there be a better solution if the dual bound is 0? Or do you think CPLEX computes the wrong solution for the LP relaxation?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: revolt

Yes, the start solution is correct.
The lazy constraint that is violated by the rejected solution is the constraint:

lazyConstrViolated = vals[3] > 0 && vals[5] > 4992.0;
//or with other words:
lazyConstrSatisfied = vals[3] <= 0 || vals[5] <= 4992.0;

This constraint is violated by the solution

incumbCbk @ Node0. ( 1 0 0 1 0 5005 0 52 0 0 0 18 60 0 0 13 ) = vals  /  reject.

but it is satisfied by the solution

incumbCbk @ Node2. ( 1 0 0 1 0 4992 0 0 104 0 60 0 8 0 0 0 ) = vals  /  accept.

Both solutions have the same objective value (8,0400), as the objective is only depending on the binary variables (the first five variables). Also the binary variables have the same values. Only the continuous variables differ.

I guess that from the perspective of CPLEX both solutions are equivalent and it is left to the user to detect whether it is possible to adjust the continuous variables. Right?

The first solution is rejected by my program, because it violates the lazy constraint, the second solution is not found by cplex, because the branch callback is not called. If you comment out the line "cp.setVectors(...);" in the second example, then the branch callback will be called and the second solution can be found, even though it has the same objective and the same binary values like the fist one.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Ah, yes. This is a subtlety with lazy constraints, which means that in your case, you really need to add a lazy constraint callback. An incumbent and branch callback will not be enough.

The issue is the following: if CPLEX gets an integral LP solution (i.e., all integer variables have integer LP solution values), then it calls the incumbent callback. If this is rejecting the solution, then there are two cases:
1. There is at least one integer variable left that is not fixed (i.e., the lower bound at the node is strictly smaller than the upper bound of the variable). In this case CPLEX just picks one of those not yet fixed variables and branches (I don't know right now whether in this situation the branch callback is called).
2. All integer variables are fixed. In this case, the node is pruned.

So, if it can happen that an LP relaxation with all integer variables fixed still contains feasible and infeasible solutions in its optimal face, then an incumbent and branch callback combination is not sufficient. You really need a lazy constraint callback here.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: revolt

Ok, thanks for the clear answer.

So in my case I could either use the lazy+incumbent+branch cbk. Or, if I decide to use only the incumbent+branch cbk, then I need to proof by myself whether the model with fixed binary variables (to the incumbent solution) contains a feasible solution with respect to the primal and lazy constraints. In the second case, my program would already accept the first solution and modify the continuous variables accordingliy in post processing.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Yes, exactly. But if you use a lazy constraint callback, then you do no longer need an incumbent or branch callback.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: revolt

Ok, thanks. Now I am considering to use LazyCallbacks and I would like to use the lower bounds of the binary variables computed by CPLEX. The documantation says:


What exactly does it mean, if LazyCallback.getLBs returns at the root node, that for example the binary variables b0, b1, and b2 have a lower bound equal to 1? Intuitively I would think, that any following feasible solution must satisfy this tightened bounds. But, as far as I can see it, this is not true, because in the following example, the second solution violates the tightened bounds of the first call of the lazy constraint callback.

IBM ILOG License Manager: 
"IBM ILOG Optimization Suite for Academic Initiative" is accessing CPLEX 12 with option(s): 
"e m b q ". Lazy constraint(s) or lazy constraint callback is present. Disabling dual reductions (CPX_PARAM_REDUCE) in presolve. Disabling non-linear reductions (CPX_PARAM_PRELINEAR) in presolve. Tried aggregator 1 time. Probing time =    0.00 sec. Tried aggregator 1 time. Warning: Control callbacks may disable some MIP features. Presolve time =    0.00 sec. Probing time =    0.00 sec. Clique table members: 3. MIP emphasis: balance optimality and feasibility. MIP search method: traditional branch-and-cut. Parallel mode: none, using 1 thread. Root relaxation solution time =    0.00 sec.   Nodes                                         Cuts/  Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap Variable B NodeID Parent  Depth   0     0      131.5000     1                    131.5000        5 LazyCallback .getValues = ( 1 1 1 0 0 3980 5155 0 0 3111 0 2006 0 2096 0 5030 ) .getLBs    = ( 1 1 1 0 0 3980 0 0 0 0 0 0 0 0 0 0 ) *     0+    0                           38.5000      131.5000        5  241.56% LazyCallback .getValues = ( 1 0 0 0 1 3980 5155 0 0 3111 0 2006 0 2096 0 5030 ) .getLBs    = ( 1 0 0 0 1 3980 0 0 0 0 0 0 0 0 0 0 ) *     0+    0                          125.5000      131.5000        5    4.78% 0     0        cutoff            125.5000      131.5000        5    4.78%                        0             0 Elapsed real time =   0.00 sec. (tree size =  0.00 MB, solutions = 2)   Root node processing (before b&c): Real time             =    0.00 Sequential b&c: Real time             =    0.00 ------- Total (root+branch&cut) =    0.00 sec.

In this example CPLEX even relaxes the tightened bounds between two calls of the LazyCallback and both times the Callback is called at the root node. If the tightened bounds are relaxed during the runtime and even at one and the same node, then I dont know how I can use the information of getLBs.

By the way I noticed, that the following Paramfile is not readable in java-Debug-Mode. CPLEX only accepts it, if I run the java program without debugging:

CPLEX Parameter File Version 12.4.0.0 CPX_PARAM_EPOPT                  1.00000000000000e-09 CPX_PARAM_EPINT                  1.00000000000000e-06

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

This is due to how heuristics are implemented in CPLEX.

If a heuristic finds some solution, then it fixes all integer variables to the solution values and solves the fixed LP relaxation again to get values for the continuous variables. On this sub problem the lazy constraint callback is called, which then sees the "local bounds" to be all fixed for the integer variables.
You can think of this as a temporary dive in the search tree, and the lazy constraint callback is called at the leaf node of this dive where all integer variables are locally fixed. And since the getLBs() method returns the local bounds at the node, you see the fixed bound vectors...

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: revolt

Ok, so in both cases the lazy callback is called from a "leaf node" of the current node (the root node). When I add a local lazy constraint, then it is added to the current (root) node and not to the (for me invisible) leaf node of the root node.

So I always need to keep in mind, that the LBs that are visible from a lazy callback are not bounds for the
current node. They are bounds for the current internal leaf node of the current node. Can you give me an example how or in which cases one can use this LB information?

In my case I can not use it, because if I add a local lazy constraint that is based on the lower bound information, that makes the leaf node infeasible, then the entire current node gets infeasible. This lazy constraints would only be valid for the leaf node, but are not valid for the current node...
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

This issue only arises from heuristics. I don't think that you want to add lazy constraints to cut off heuristic solutions. Namely, the solutions found by heuristics could be completely irrelevant to the tree search and thus any lazy constraint that you add to cut off such a solution is likely to just slow down the nodelp solves.

I think you should just reject solutions from heuristics using an incumbent callback.

We call the lazy constraint callback first, and only if a solution passes this test it will be forwarded to the incumbent callback. This means that in the lazy constraint callback you should check whether the solution came from a heuristic (which is the case if all local bounds of integer variables are fixed, i.e., lb[j] == ub[j] for all integer variables j). If this is the case, just ignore the solution in the lazy constraint callback.
In the incumbent callback, just check every solution as usual and reject the ones that are infeasible.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: revolt

This sounds like a good idea!

In lazy constrarint cbk:
If LB[j] == UB[j] for all integer variables j then the solution comes from a heuristik.

If LB[j] != UB[j] for some integer variable j then I can use the bound information to create lazy constraints for the current node? Or is this information even in this case related to a "leaf node" of the current node?

Many thanks for the clear answers,
Johannes
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

It is exactly as you said. If there is at least one integer variable with lb[j] != ub[j], then the solution came from the search tree (i.e., an integral LP solution of a node relaxation). If lb[j] == ub[j] for all integer variables j, then the solution came from a heuristic, or it came from a node relaxation in which all integers have been fixed (which is very unlikely, and in this case you probably also do not want to generate a lazy constraint).
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: revolt

I just want to note, that the parameter import bug in the java api is still present in CPLEX 12.5. If you start the following Java program, then CPLEX will raise error 1015 two times. I am using the sun java jdk.

import ilog.cplex.IloCplex;   

public 

class CPXJavaAPIParamImportBug 
{ 

public 

static 

void main(String args[]) 
{ IloCplex cp = 

null; 

try 
{ cp = 

new IloCplex(); cp.setParam(IloCplex.DoubleParam.EpOpt, 1e-9); cp.writeParam(
"tmp.prm"); cp.readParam(
"tmp.prm"); 
} 

catch (Exception e) 
{ System.out.println(e + 
"(IloCplex.DoubleParam.EpOpt: \"Any number from 1e-9 to 1e-1; default: 1e-06.\")"); 
} 

finally 
{ 

if (cp != 

null)   cp.end(); 
} cp = 

null; 

try 
{ cp = 

new IloCplex(); cp.setParam(IloCplex.DoubleParam.EpInt, 1e-6); cp.writeParam(
"tmp.prm"); cp.readParam(
"tmp.prm"); 
} 

catch (Exception e) 
{ System.out.println(e + 
"(IloCplex.DoubleParam.EpInt: \"Any number from 0.0 to 0.5; default: 1e-05.\")"); 
} 

finally 
{ 

if (cp != 

null)  cp.end(); 
} 
}   
}

Compiling and running the program yields:

jmueller@calculon:~/workspace/CplexBug$ /opt/jdk1.7.0_13/bin/javac \ > -classpath /opt/cplex125/cplex/lib/cplex.jar CPXJavaAPIParamImportBug.java jmueller@calculon:~/workspace/CplexBug$ /opt/jdk1.7.0_13/bin/java \ > -Djava.library.path=/opt/cplex125/cplex/bin/x86-64_sles10_4.1/ \ > -classpath .:/opt/cplex125/cplex/lib/cplex.jar CPXJavaAPIParamImportBug   ilog.cplex.CpxException: CPLEX Error  1015: Parameter value too big. (IloCplex.DoubleParam.EpOpt: 
"Any number from 1e-9 to 1e-1; default: 1e-06.")   ilog.cplex.CpxException: CPLEX Error  1015: Parameter value too big. (IloCplex.DoubleParam.EpInt: 
"Any number from 0.0 to 0.5; default: 1e-05.")

According to the documentation the parameters are not too big !
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Weird. I cannot reproduce the problem here.
What platform do you use? What is the function that throws the exception? Is it setParam() or readParam()? Do you happen to have a java 1.6 JRE installed? If so, could you test with that and check whether the problem persists?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: revolt

I am using a 64bit PC with an up to date Ubuntu (Kernel 3.2.0-38-generic). The exception is thrown at the readParam lines.

The problem occurs if I use java-7-openjdk-amd64, oracle-jdk1.7.0_13, oracle-jdk1.7.0_09, java-gcj-4.6, or java-gcj-4.4.
There is no exception if I use java-6-openjdk-amd64 or java-6-sun-1.6.0.26.

I also tested it on another machine (64Bit Debian). The problem even occurs, if I compile the .java file with java-6-openjdk-amd64 and then run it with any of the above mentioned JDKs.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: revolt

It seems to be a language problem. If I use java7 and replace the decimal point by a comma in the prm file, then CPLEX accepts it and reads the values correctly (cf. the attached source). The code

cp.setParam(IloCplex.DoubleParam.EpOpt, 1e-9);
cp.writeParam("tmp.prm");
repalceDotByComma("tmp.prm");
cp.setParam(IloCplex.DoubleParam.EpOpt, 1e-7);
cp.readParam("tmp.prm");
System.out.println("EpOpt = "+cp.getParam(IloCplex.DoubleParam.EpOpt));

yields the output "EpOpt = 1e-9" and does not throw an exception (in openjdk-7 and oracle-jdk-7).
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I ran your code with the calls to repalceDotByComma() commented out, and there were no errors. This is on Linux Mint Nadia (fork of Ubuntu Quantal), CPLEX 12.5, Oracle Java 1.7.0_15.

My system is configured for US English. I wonder if your problem might indicate a mismatch between the language Java expects and the language CPLEX expects?

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

Yes, it is a language problem. If the locale is set to something that uses a decimal point different from '.' (for example ',' as in the German locale) then reading a parameter file may fail.
The only work around is to either adjust the parameter file to the locale (like you did) or to change the locale to US style or anything else that uses '.' as a decimal point and ',' as a thousands separator.
I have recorded this as a bug. Thank you for investigating and reporting it.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: revolt

May 3, 2012  in response to revolt

It is exactly as you said. If there is at least one integer variable with lb[j] != ub[j], then the solution came from the search tree (i.e., an integral LP solution of a node relaxation). If lb[j] == ub[j] for all integer variables j, then the solution came from a heuristic, or it came from a node relaxation in which all integers have been fixed (which is very unlikely, and in this case you probably also do not want to generate a lazy constraint).
Tobias

Hi,

it seems that the hack that was proposed by Tobias in May 3, 2012 does not work properly (anymore?):

I found an instance where the first solution that CPLEX sends to the LazyCbk does not satisfy the property lb[j] == ub[j] for all integer variables j, even though it is a heuristic solution. After accepting the solution in the LazyCbk, CPLEX sends the same solution to the IncumentCbk. There, the function getSolutionSource() returns the information, that the solution comes form a heuristic. I can send you a the instance via Email, if you like.

Even though I found an alternative hack by my own, I would like to know whether there is
an "official" workaround, to access the solution source from the LazyCbk. I think that this would be a very nice feature in a future release.

Sincerely, Johannes

#CPLEXOptimizers
#DecisionOptimization

Paul Rubin already filed an RFE with exactly that wish. You can view it here. You can even upvote it to make it more likely that we work on that :-)

As you correctly said, what Tobias suggested was a "hack". There is no guarantee that this always works. Still, I would be interested to take a look at your model and see why the heuristic solution does not have all integer variables fixed. So if you could send the model to daniel(dot)junglas(at)de(dot)ibm(dot)com? Please also include information about your machine and the CPLEX version you use.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: revolt

Daniel has found that it was a numerical issue. I used the following code to check whether the bounds are equal.

        double[] lb = getLBs(binVars);
        double[] ub = getUBs(binVars);
        boolean equalBounds = Arrays.equals(lb, ub);

This test failed, because there was a binary variable i with lb[i]=-0.0 and ub[i]=+0.0, and Arrays.equals() returns false in such a situation. In order to get a more robust test, I will now use the following function.

        protected boolean isHeuristicSolOrFixedNodeSol(IloNumVar[] binVars)
                          throws IloException {
            double[] lb = getLBs(binVars);
            double[] ub = getUBs(binVars);
            for (int i = 0; i < ub.length; i++) {
                if (Math.abs(ub[i]-lb[i]) > 1e-6) return false;
            }
            return true;
        }

With this test, everything works fine again. Thanks Daniel!

#CPLEXOptimizers
#DecisionOptimization