Topic
  • 23 replies
  • Latest Post - ‏2014-02-15T12:16:04Z by revolt
revolt
revolt
44 Posts

Pinned topic Incumbent cbk returns the same solution multiple times

‏2012-04-26T07:50:16Z |
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
Updated on 2013-02-26T19:28:08Z at 2013-02-26T19:28:08Z by SystemAdmin
  • revolt
    revolt
    44 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2012-04-26T08:20:25Z  
    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?
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2012-04-26T09:02:44Z  
    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.
  • revolt
    revolt
    44 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2012-04-26T12:44:39Z  
    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.
    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
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2012-04-26T13:42:34Z  
    • revolt
    • ‏2012-04-26T12:44:39Z
    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
    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?
  • revolt
    revolt
    44 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2012-04-26T14:55:46Z  
    When I run your code I get the following output:
    <pre class="jive-pre"> 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. </pre>
    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?
    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.
    Updated on 2014-03-24T23:03:17Z at 2014-03-24T23:03:17Z by iron-man
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2012-04-26T20:02:20Z  
    • revolt
    • ‏2012-04-26T14:55:46Z
    Yes, the start solution is correct.
    The lazy constraint that is violated by the rejected solution is the constraint:
    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">lazyConstrViolated = vals[3] > 0 && vals[5] > 4992.0; //or with other words: lazyConstrSatisfied = vals[3] <= 0 || vals[5] <= 4992.0; </pre>
    This constraint is violated by the solution
    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">incumbCbk @ Node0. ( 1 0 0 1 0 5005 0 52 0 0 0 18 60 0 0 13 ) = vals / reject. </pre>
    but it is satisfied by the solution
    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">incumbCbk @ Node2. ( 1 0 0 1 0 4992 0 0 104 0 60 0 8 0 0 0 ) = vals / accept. </pre>
    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.
    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
  • revolt
    revolt
    44 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2012-04-27T08:56:57Z  
    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
    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.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2012-04-27T09:25:33Z  
    • revolt
    • ‏2012-04-27T08:56:57Z
    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.
    Yes, exactly. But if you use a lazy constraint callback, then you do no longer need an incumbent or branch callback.
  • revolt
    revolt
    44 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2012-05-02T16:12:47Z  
    Yes, exactly. But if you use a lazy constraint callback, then you do no longer need an incumbent or branch callback.
    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:

    protected double[] getLBs(IloNumVar[] var) throws IloException
    Returns the current lower bounds for an array of variables. The bounds may be different from the bounds the variables have in the active model, since branching or bound strengthening may have been applied to them. The corresponding solution values from getValues may violate these bounds at a node where a new incumbent has been found because the bounds are tightened when an incumbent is found.

    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
    
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2012-05-03T09:59:02Z  
    • revolt
    • ‏2012-05-02T16:12:47Z
    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:

    protected double[] getLBs(IloNumVar[] var) throws IloException
    Returns the current lower bounds for an array of variables. The bounds may be different from the bounds the variables have in the active model, since branching or bound strengthening may have been applied to them. The corresponding solution values from getValues may violate these bounds at a node where a new incumbent has been found because the bounds are tightened when an incumbent is found.

    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.

    <pre class="jive-pre"> 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. </pre>

    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:
    <pre class="jive-pre"> CPLEX Parameter File Version 12.4.0.0 CPX_PARAM_EPOPT 1.00000000000000e-09 CPX_PARAM_EPINT 1.00000000000000e-06 </pre>
    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
  • revolt
    revolt
    44 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2012-05-03T11:56:55Z  
    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
    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...
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2012-05-03T12:14:41Z  
    • revolt
    • ‏2012-05-03T11:56:55Z
    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...
    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
  • revolt
    revolt
    44 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2012-05-03T13:24:06Z  
    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
    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
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2012-05-03T13:33:05Z  
    • revolt
    • ‏2012-05-03T13:24:06Z
    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
    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
  • revolt
    revolt
    44 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2013-02-25T14:11:55Z  
    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
    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 !
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2013-02-25T15:35:45Z  
    • revolt
    • ‏2013-02-25T14:11:55Z
    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.

    <pre class="jive-pre"> 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(); } } } </pre>

    Compiling and running the program yields:
    <pre class="jive-pre"> 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.") </pre>

    According to the documentation the parameters are not too big !
    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?
  • revolt
    revolt
    44 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2013-02-26T15:00:08Z  
    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?
    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.
  • revolt
    revolt
    44 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2013-02-26T16:37:55Z  
    • revolt
    • ‏2013-02-26T15:00:08Z
    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.
    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).
    Updated on 2014-03-24T22:37:18Z at 2014-03-24T22:37:18Z by iron-man
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2013-02-26T16:52:47Z  
    • revolt
    • ‏2013-02-26T16:37:55Z
    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
    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">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)); </pre>
    yields the output "EpOpt = 1e-9" and does not throw an exception (in openjdk-7 and oracle-jdk-7).
    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)
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2013-02-26T19:28:08Z  
    • revolt
    • ‏2013-02-26T16:37:55Z
    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
    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">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)); </pre>
    yields the output "EpOpt = 1e-9" and does not throw an exception (in openjdk-7 and oracle-jdk-7).
    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.
  • revolt
    revolt
    44 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2014-02-13T22:58:14Z  
    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
    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

  • DanielJunglas
    DanielJunglas
    1579 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2014-02-14T16:18:36Z  
    • revolt
    • ‏2014-02-13T22:58:14Z
    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

    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.

  • revolt
    revolt
    44 Posts

    Re: Incumbent cbk returns the same solution multiple times

    ‏2014-02-15T12:16:04Z  

    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.

    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!