Topic
IC4NOTICE: developerWorks Community will be offline May 29-30, 2015 while we upgrade to the latest version of IBM Connections. For more information, read our upgrade FAQ.
13 replies Latest Post - ‏2009-05-18T19:33:36Z by SystemAdmin
SystemAdmin
SystemAdmin
7929 Posts
ACCEPTED ANSWER

Pinned topic Wrong Optimal solution with Cplex 11.2

‏2009-03-28T01:10:25Z |

[alysson said:]

Dear all,

I am really puzzled with the following:

I have an IP model. ( http://www.icmc.usp.br/~alysson/files/share/sol21.lp ) . If I solve this model (I am using Cplex 11.2, interative optimizer, under Ubuntu ), I obtain an "optimal" integer solution with cost 23 ( http://www.icmc.usp.br/~alysson/files/share/SolutionUsingCplexWithCost23.txt ).

HOWEVER, I know of a solution with cost 21 ( http://www.icmc.usp.br/~alysson/files/share/sol21.mst ). Indeed, if I pass this solution to CPLEX as an mst file, Cplex starts using it as the "Best Integer found" ( http://www.icmc.usp.br/~alysson/files/share/ReadingSolutioWithfCost21.txt ).

Am I missing anything ? Any help is appreciated,

Alysson
Updated on 2009-05-18T19:33:36Z at 2009-05-18T19:33:36Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    7929 Posts
    ACCEPTED ANSWER

    Re: Wrong Optimal solution with Cplex 11.2

    ‏2009-03-28T23:39:28Z  in response to SystemAdmin

    [prubin said:]

    I verified this with CPLEX 11.0 (also on Ubuntu).  There are two ways (that I found) to get CPLEX to produce a correct solution (objective = 21) without the hot start:  turn off the presolver; or crank up the simplex feasibility tolerance (1e-9 worked for me).  Turning off the presolver seems to be the faster option.  (Disclaimer:  In both instances, I aborted the run after it found an integer-feasible solution with value 21 but before it exhausted the search tree, so it's possible one or the other option might have led to problems down the road.)

    I ran into a similar problem a while back, with a similar looking MIP model (mine was a set covering problem), in which the symmetry reduction constraints added by CPLEX cut off the optimal solution.  In this case, turning off the symmetry reductions does not help, but it looks like one of the reductions done by the presolver is causing problems.  I'll alert someone in IBM's CPLEX unit about your post; they'll probably want to test your model to see what's going wrong.

    /Paul
    • SystemAdmin
      SystemAdmin
      7929 Posts
      ACCEPTED ANSWER

      Re: Wrong Optimal solution with Cplex 11.2

      ‏2009-03-29T01:18:47Z  in response to SystemAdmin

      [alysson said:]

      Dear Dr. Rubin,

      Thank you for your prompt (as usual) answer! Both ways you suggested worked here as well (CPLEX 11.2). I am really looking forward to hear more about this from people from CPLEX. In the meantime, some additional information:

      - My problem is sort of a makespan minimization with precedence constraints. The time to execute each task x at each machine depends on the worker y assigned to the machine.

      - If I change the last set of constraints

      x_1 + x_2 + ... x_n \leq n*y

      for their disaggregated form:

      x_i \leq y  (for all i),

      then CPLEX finds the optimal solution.


      - I asked a friend to run the example on his CPLEX 10.1.1 installation and he got the correct answer (21).


      Thank you again!

      Alysson
      • SystemAdmin
        SystemAdmin
        7929 Posts
        ACCEPTED ANSWER

        Re: Wrong Optimal solution with Cplex 11.2

        ‏2009-03-29T11:20:16Z  in response to SystemAdmin

        [EdKlotz said:]

        I have an IP model. ( http://www.icmc.usp.br/~alysson/files/share/sol21.lp ) . If I solve this model (I am using Cplex 11.2, interative optimizer, under Ubuntu ), I obtain an "optimal" integer solution with cost 23 ( http://www.icmc.usp.br/~alysson/files/share/SolutionUsingCplexWithCost23.txt ).


        I just ran CPLEX 11.2 with defaults on Fedora Core 4 Linux (I don't have any machines running
        Ubuntu), and it found the solution with objective
        21.  Looking at the output in SolutionUsingCplexWithCost23.txt, you appear to be running
        defaults as well, but I see one line that suggests otherwise:

        Repeating presolve.

        Typically, CPLEX doesn't repeat the presolve by default, and in my default run it did not do so.
        Did you turn on the repeat presolve parameter or set some other non default settings?  If so,
        try just running with defaults and see what happens.  If you did not set any non default parameters,
        try explicitly turning the repeat presolve parameter off explicitly:

        CPLEX>  set pre repeatpresolve 0

        Tell us what happens.    I did try turning this parameter on, but I still got the solution of 21.
        Numerically your model looks pretty reasonable, so this doesn't look like some sort of numerical
        instability or ill conditioning issue. 

                                                                                                              Ed

        • SystemAdmin
          SystemAdmin
          7929 Posts
          ACCEPTED ANSWER

          Re: Wrong Optimal solution with Cplex 11.2

          ‏2009-03-29T23:16:40Z  in response to SystemAdmin

          [alysson said:]

          Thanks for your answer, Dr. Klotz.

          Indeed, I used default parameters. In particular, the repeatpresolve was set at -1 (automatic).

          As you suggested, I forced the repeatpresolve at zero and re-run the test, but still got the same answer: http://www.icmc.usp.br/~alysson/files/share/repeatPreSolveAtZero.txt

          Alysson
          • SystemAdmin
            SystemAdmin
            7929 Posts
            ACCEPTED ANSWER

            Re: Wrong Optimal solution with Cplex 11.2

            ‏2009-03-30T21:47:55Z  in response to SystemAdmin

            [alysson said:]

            This can be completely unrelated, but since it is happening on the same installation, I decided to put here:

            While solving another model ( http://www.icmc.usp.br/~alysson/files/share/negativeTime.lp ) , another curious error appears: at a given point (around 40 minutes of simulation), CPLEX switchs the sign of the elapsed time. This way, no stopping criterium based on time works (a negative time is always less than any set time limit).

            [i] Elapsed time = -1974.64 sec. (tree size = 58.66 MB, solutions = 6)
            798100 111289    infeasible            18.0000      17.0000 30851562    5.56%
            798200 111285      17.0000    8      18.0000      17.0000 30855588    5.56%
            798300 111285      17.0000    10      18.0000      17.0000 30859655    5.56%
            798400 111288      17.0000    4      18.0000      17.0000 30862781    5.56%
            [/i]


            I wonder if it can be a problem of OUR installation. Again, I am running CPLEX 11.2 on a dual-core processor with Ubuntu. 

            Alysson

            • SystemAdmin
              SystemAdmin
              7929 Posts
              ACCEPTED ANSWER

              Re: Wrong Optimal solution with Cplex 11.2

              ‏2009-03-30T21:51:37Z  in response to SystemAdmin

              [alysson said:]

              The complete log file for the simulation mentioned above can be found here:

              http://www.icmc.usp.br/~alysson/files/share/negativeTime.log

              The problem happens around time 2145s.
              • SystemAdmin
                SystemAdmin
                7929 Posts
                ACCEPTED ANSWER

                Re: Wrong Optimal solution with Cplex 11.2

                ‏2009-03-30T22:22:10Z  in response to SystemAdmin

                [alysson said:]

                Below is some input from the sci.op-research forum. Indeed there are some big-M LHS constants and they seem to be causing the problem. I now wonder about the negative time question.


                ------
                Instead of tinkering with tolerances I would suggest to reduce the
                size of your big-M constants. E.g. replace the values you use (100000)
                by 10000. Large Big-M constants can cause quite a few probems.

                ----------------------------------------------------------------
                Erwin Kalvelagen
                Amsterdam Optimization Modeling Group
                erwin.kalvela...@gmail.com
                http://amsterdamoptimization.com
                ----------------------------------------------------------------
                • SystemAdmin
                  SystemAdmin
                  7929 Posts
                  ACCEPTED ANSWER

                  Re: Wrong Optimal solution with Cplex 11.2

                  ‏2009-03-31T05:28:54Z  in response to SystemAdmin

                  [EdKlotz said:]

                  Below is some input from the sci.op-research forum. Indeed there are some big-M LHS constants and they seem to be causing the problem. I now wonder about the negative time question.


                  ------
                  Instead of tinkering with tolerances I would suggest to reduce the
                  size of your big-M constants. E.g. replace the values you use (100000)
                  by 10000. Large Big-M constants can cause quite a few probems.

                  ----------------------------------------------------------------

                  Reducing the size of the big M constraints as much as possible without compromising
                  the meaning of the model is always a good idea, although values of 100000
                  are not exceptionally large. 

                  Regarding the negative timings, Ubuntu Linux is not one of the officially supported CPLEX platforms,
                  so I don't have much help to offer.  It could involve the installation, or it could involve some
                  issue with the Linux kernel Ubuntu uses.  CPLEX measures time by making system calls, so
                  this output probably involves bogus values in the system calls.  You could try working around
                  the problem by setting CPLEX's clocktype parameter to 2 to use wall clock time instead of
                  CPU time, as the latter is the default under Linux.

                  I checked for any other such reports of negative time on any operating system, but I did not
                  find anything. 
                  • SystemAdmin
                    SystemAdmin
                    7929 Posts
                    ACCEPTED ANSWER

                    Re: Wrong Optimal solution with Cplex 11.2

                    ‏2009-03-31T08:08:42Z  in response to SystemAdmin

                    [alysson said:]

                    Dear Dr. Klotz,

                    Thank you again for your answer.

                    I will ask the technical staff of our department to change the linux distribution on the CPLEX machines. Fedora Core 4 seems to be an option. Does ILOG recommend any particular distribution ?

                    (This will need to wait a bit cause right now there are some students running final tests for their thesis, but I will post the results I obtain on the new installation here, as soon as they are available.)

                    Thanks again!

                    Alysson
                    • SystemAdmin
                      SystemAdmin
                      7929 Posts
                      ACCEPTED ANSWER

                      Re: Wrong Optimal solution with Cplex 11.2

                      ‏2009-03-31T09:03:59Z  in response to SystemAdmin

                      [EdKlotz said:]

                      Dear Dr. Klotz,

                      Thank you again for your answer.

                      I will ask the technical staff of our department to change the linux distribution on the CPLEX machines. Fedora Core 4 seems to be an option. Does ILOG recommend any particular distribution ?

                      (This will need to wait a bit cause right now there are some students running final tests for their thesis, but I will post the results I obtain on the new installation here, as soon as they are available.)

                      Thanks again!

                      Alysson

                      http://www.ilog.com/products/cplex/product/platforms.cfm

                      contains a list of officially supported platforms for 11.2

                      Machine: x86
                      OS: Debian 4.0 Red Hat Enterprise Linux 5.0,
                      SUSE Linux Enterprise Server 10
                      C++ compiler: g++ 4.1
                      Java: JDK 5.0, 6.0 

                      Fedora Core should be fine, but ideally you should select from one of the above.

                      Also, regarding the sol21.lp file associated with this thread, I found that setting
                      CPLEX's probing parameter to its most aggressive level of 3 significantly reduced the
                      run time to optimality.  More generally, on fairly difficult models with only a modest
                      number of binary variables, this non default parameter setting often helps.



                      • SystemAdmin
                        SystemAdmin
                        7929 Posts
                        ACCEPTED ANSWER

                        Re: Wrong Optimal solution with Cplex 11.2

                        ‏2009-04-09T20:56:04Z  in response to SystemAdmin

                        [alysson said:]

                        Thank you again for the answer. I will sugest the installation of Red Hat and, if we cannot get it, some version of Fedora.

                        Concerning the suggestion about the parameters, thank you again. I will make some tests on my set of instances.

                        Best regards,

                        Alysson
                        • SystemAdmin
                          SystemAdmin
                          7929 Posts
                          ACCEPTED ANSWER

                          Re: Wrong Optimal solution with Cplex 11.2

                          ‏2009-04-17T01:51:30Z  in response to SystemAdmin

                          [plr said:]

                          Hi, all.

                          I also have the problem of getting a negative elapsed time with my model ( http://www.cs.nott.ac.uk/~plr/negativeTime2.lp ). It only happens with specific instances, not all of them.
                          I am running CPLEX 11.2.0 on CentOS 5.3, which is derivative from Red Hat Enterprise 5.
                          I will try to run it on a Debian machine to see if the same problem occurs and post the results here.

                          Cheers,
                          Pedro
                          • SystemAdmin
                            SystemAdmin
                            7929 Posts
                            ACCEPTED ANSWER

                            Re: Wrong Optimal solution with Cplex 11.2

                            ‏2009-05-18T19:33:36Z  in response to SystemAdmin

                            [notdarkyet said:]

                            I tested your problem under openSuSE x64 with CPLEX 11.2.1 and a solution with value 21 is found even when turning on presolve repeat and all cuts set to aggressively. So the cutoff of the optimal solution doesn't occur with this OS.
                            But it takes quite a lot of nodes to prove optimality, I interrupted the run at
                            666600 50174      20.8571    12      21.0000      20.8571 13001274    0.68%

                            With a drastically reduced big-M (to 33), probing level 3, cuts selectively set to 2 and mip emphasis 3 the problem is solved to optimality in short time (though it takes more nodes to find the solution with 21 than with default params):
                                  0    0      10.5417  205      55.0000      Cuts: 92    20049  80.83%
                                  0    0      10.5417  208      55.0000      Cuts: 93    20277  80.83%
                            *    0+    0                          31.0000      10.5417    20277  65.99%
                                  0    2      11.0000  174      31.0000      11.0000    20277  64.52%
                            Elapsed time =  13.85 sec. (tree size =  0.00 MB, solutions = 3)
                                100    43      21.7895    42      31.0000      13.0000    68964  58.06%
                            *  140+  59                          29.0000      14.0000    88280  51.72%
                            *  160+  66                          24.0000      15.0000    95661  37.50%
                                200    62      17.0000    44      24.0000      17.0000  102955  29.17%
                            *  230+  67                          23.0000      17.0000  111843  26.09%
                                300    84      18.0000    40      23.0000      18.0000  136399  21.74%
                            *  340+  59                          22.0000      18.0000  147523  18.18%
                            *  360+    0                          21.0000      21.0000  151129    0.00%

                            GUB cover cuts applied:  83
                            Clique cuts applied:  160
                            Cover cuts applied:  129
                            Implied bound cuts applied:  2
                            Mixed integer rounding cuts applied:  159
                            Zero-half cuts applied:  1

                            Solution pool: 8 solutions saved.

                            MIP - Integer optimal solution:  Objective =  2.1000000000e+01
                            Solution time =  50.86 sec.  Iterations = 151129  Nodes = 360


                            The negative time measurement occured to me, too - under Ubuntu. I did not observe this under SuSE, so there seems to be a flaw in the time measuring system calls of Ubuntu.
                            A negative time looks strange, though we all would be happy if problems were solved before we stated them!
                            Ralf