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

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
    ACCEPTED ANSWER

    Re: Incumbent cbk returns the same solution multiple times

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

    Re: Incumbent cbk returns the same solution multiple times

    ‏2012-04-26T09:02:44Z  in response to revolt
    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
      ACCEPTED ANSWER

      Re: Incumbent cbk returns the same solution multiple times

      ‏2012-04-26T12:44:39Z  in response to SystemAdmin
      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
        ACCEPTED ANSWER

        Re: Incumbent cbk returns the same solution multiple times

        ‏2012-04-26T13:42:34Z  in response to revolt
        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
          ACCEPTED ANSWER

          Re: Incumbent cbk returns the same solution multiple times

          ‏2012-04-26T14:55:46Z  in response to SystemAdmin
          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
            ACCEPTED ANSWER

            Re: Incumbent cbk returns the same solution multiple times

            ‏2012-04-26T20:02:20Z  in response to revolt
            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
              ACCEPTED ANSWER

              Re: Incumbent cbk returns the same solution multiple times

              ‏2012-04-27T08:56:57Z  in response to SystemAdmin
              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
                ACCEPTED ANSWER

                Re: Incumbent cbk returns the same solution multiple times

                ‏2012-04-27T09:25:33Z  in response to revolt
                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
                  ACCEPTED ANSWER

                  Re: Incumbent cbk returns the same solution multiple times

                  ‏2012-05-02T16:12:47Z  in response to SystemAdmin
                  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
                    ACCEPTED ANSWER

                    Re: Incumbent cbk returns the same solution multiple times

                    ‏2012-05-03T09:59:02Z  in response to revolt
                    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
                      ACCEPTED ANSWER

                      Re: Incumbent cbk returns the same solution multiple times

                      ‏2012-05-03T11:56:55Z  in response to SystemAdmin
                      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
                        ACCEPTED ANSWER

                        Re: Incumbent cbk returns the same solution multiple times

                        ‏2012-05-03T12:14:41Z  in response to revolt
                        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
                          ACCEPTED ANSWER

                          Re: Incumbent cbk returns the same solution multiple times

                          ‏2012-05-03T13:24:06Z  in response to SystemAdmin
                          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
                            ACCEPTED ANSWER

                            Re: Incumbent cbk returns the same solution multiple times

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

                              Re: Incumbent cbk returns the same solution multiple times

                              ‏2013-02-25T14:11:55Z  in response to SystemAdmin
                              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
                                ACCEPTED ANSWER

                                Re: Incumbent cbk returns the same solution multiple times

                                ‏2013-02-25T15:35:45Z  in response to revolt
                                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
                                  ACCEPTED ANSWER

                                  Re: Incumbent cbk returns the same solution multiple times

                                  ‏2013-02-26T15:00:08Z  in response to SystemAdmin
                                  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
                                    ACCEPTED ANSWER

                                    Re: Incumbent cbk returns the same solution multiple times

                                    ‏2013-02-26T16:37:55Z  in response to 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).
                                    Updated on 2014-03-24T22:37:18Z at 2014-03-24T22:37:18Z by iron-man
                                    • SystemAdmin
                                      SystemAdmin
                                      7929 Posts
                                      ACCEPTED ANSWER

                                      Re: Incumbent cbk returns the same solution multiple times

                                      ‏2013-02-26T16:52:47Z  in response to revolt
                                      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
                                      ACCEPTED ANSWER

                                      Re: Incumbent cbk returns the same solution multiple times

                                      ‏2013-02-26T19:28:08Z  in response to revolt
                                      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
                          ACCEPTED ANSWER

                          Re: Incumbent cbk returns the same solution multiple times

                          ‏2014-02-13T22:58:14Z  in response to SystemAdmin
                          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
                            1377 Posts
                            ACCEPTED ANSWER

                            Re: Incumbent cbk returns the same solution multiple times

                            ‏2014-02-14T16:18:36Z  in response to revolt

                            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
                              ACCEPTED ANSWER

                              Re: Incumbent cbk returns the same solution multiple times

                              ‏2014-02-15T12:16:04Z  in response to DanielJunglas

                              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!