Topic
14 replies Latest Post - ‏2013-03-05T14:38:57Z by SystemAdmin
SystemAdmin
SystemAdmin
7929 Posts
ACCEPTED ANSWER

Pinned topic Unbound status, but integer solution is found

‏2013-02-22T14:08:48Z |
Hi
I've got this log output from cplex showing that an optimal solution is found at the root node, but cplexstatus = 2 (unbound). Where did it go wrong? How do I get the integer solution found at the root?
Thanks.

Tried aggregator 2 times.
...
Tried aggregator 3 times.
...
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.20 sec. (60.78 ticks)

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

  • 0+ 0 69.0000 63.0000 1156 8.70%
Found incumbent of value 69.000000 after 0.64 sec. (170.50 ticks)
0 0 64.0000 247 69.0000 64.0000 1156 7.25%
  • 0+ 0 68.0000 64.0000 1472 5.88%
Found incumbent of value 68.000000 after 1.05 sec. (297.13 ticks)
0 0 64.0000 249 68.0000 Cuts: 938 1472 5.88%
0 0 64.0000 34 68.0000 Cuts: 27 1568 5.88%
  • 0+ 0 65.0000 64.0000 1568 1.54%
Found incumbent of value 65.000000 after 1.29 sec. (406.54 ticks)
0 0 64.0000 84 65.0000 Cuts: 42 1754 1.54%

Repeating presolve.
Tried aggregator 4 times.
...

Root node processing (before b&c):
Real time = 1.36 sec. (382.25 ticks)
Parallel b&c, 8 threads:
Real time = 0.00 sec. (0.00 ticks)
Sync time (average) = 0.00 sec.
Wait time (average) = 0.00 sec.

Total (root+branch&cut) = 1.36 sec. (382.25 ticks)
Updated on 2013-03-05T14:38:57Z at 2013-03-05T14:38:57Z by SystemAdmin
  • T_O
    T_O
    440 Posts
    ACCEPTED ANSWER

    Re: Unbound status, but integer solution is found

    ‏2013-02-22T16:31:55Z  in response to SystemAdmin
    Could you post a sav-file from your model? Status 2 sounds a little strange as CPLEX gives a MIP-gap.

    Best regards,
    Thomas
    • SystemAdmin
      SystemAdmin
      7929 Posts
      ACCEPTED ANSWER

      Re: Unbound status, but integer solution is found

      ‏2013-02-22T17:08:46Z  in response to T_O
      Here it is. A different problem but the same symptom. Thanks.
      • gangulo
        gangulo
        34 Posts
        ACCEPTED ANSWER

        Re: Unbound status, but integer solution is found

        ‏2013-02-22T19:12:44Z  in response to SystemAdmin
        I've been experimenting a similar behavior with CPLEX 12.5 (Linux 64-bit) in some problems. In my case, somes MIPs are declared unbounded, which I know cannot happen. I see on the screen that the LP relaxation is solved to optimality, incumbents are found, and the gap decreases to 0. However, if I query the solution status, it returns 118 (CPXMIP_UNBOUNDED). On the other hand, I can query the objective value without issues. The problems are generated internally in my code, but if I save the problem to a file and read it again, CPLEX finds an optimal solution and reports status optimal!

        I took the problem posted above and tried to solve it. Again, I see the root node solved to optimality, but the problem is declared unbounded. If I relax it to an LP, an optimal solution is found. Strangely, if I read the original file and write it in LP format, then the problem goes away!

        I hope somebody can help us with these issues.
        • SystemAdmin
          SystemAdmin
          7929 Posts
          ACCEPTED ANSWER

          Re: Unbound status, but integer solution is found

          ‏2013-02-22T20:40:06Z  in response to gangulo
          Any time exporting a problem to LP format produces markedly different results from solving it internally (or exporting a SAV file), you should suspect numerical instability in the problem. A SAV file is a faithful representation of the problem being solved in your code, but conversion to and from ASCII to produce an LP file cause some truncation errors that subtly change the problem.

          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: Unbound status, but integer solution is found

          ‏2013-03-01T09:58:57Z  in response to gangulo
          Does the problem persist if you disable repeated presolve ([CPX_PARAM_REPEATPRESOLVE|http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.cplex.help%2FCPLEX%2FParameters%2Ftopics%2FRepeatPresolve.html) = 0)?
          • SystemAdmin
            SystemAdmin
            7929 Posts
            ACCEPTED ANSWER

            Re: Unbound status, but integer solution is found

            ‏2013-03-01T11:55:22Z  in response to SystemAdmin
            Thanks, Daniel. Yes, the problem is solved, but cplex took longer to solve. Is there any work around not to disable presolve, as I need to set the same cplex parameters for all instances?
            • SystemAdmin
              SystemAdmin
              7929 Posts
              ACCEPTED ANSWER

              Re: Unbound status, but integer solution is found

              ‏2013-03-01T12:35:45Z  in response to SystemAdmin
              Did you disable presolve (CPX_PARAM_PREIND) or repeated presolve (CPX_PARAM_REPEATPRESOLVE)?
              It is only repeated presolve that needs to be disabled, not presolve itself.
              I did not yet get to the bottom of the problem so I don't have a better work around. You may try to enable numerical emphasis but that would require to change a parameter for each model as well.
              • SystemAdmin
                SystemAdmin
                7929 Posts
                ACCEPTED ANSWER

                Re: Unbound status, but integer solution is found

                ‏2013-03-01T12:48:31Z  in response to SystemAdmin
                I only disabled RepeatPresolve (set to 0); its log is attached in the file.

                Below is the log output with RepeatPresolve.

                ++++ Log Output from cplex solver ++++

                === Begin 1st solve === Memory Usage 57649240 bytes
                Tried aggregator 3 times.
                MIP Presolve eliminated 1144 rows and 252 columns.
                MIP Presolve modified 844 coefficients.
                Aggregator did 207 substitutions.
                Reduced MIP has 5968 rows, 2290 columns, and 18261 nonzeros.
                Reduced MIP has 1235 binaries, 0 generals, 0 SOSs, and 0 indicators.
                Presolve time = 0.11 sec. (21.02 ticks)
                Probing fixed 20 vars, tightened 144 bounds.
                Probing changed sense of 11 constraints.
                Probing time = 0.31 sec. (37.45 ticks)
                Cover probing fixed 0 vars, tightened 45 bounds.
                Tried aggregator 2 times.
                MIP Presolve eliminated 260 rows and 75 columns.
                MIP Presolve modified 363 coefficients.
                Aggregator did 42 substitutions.
                Reduced MIP has 5666 rows, 2173 columns, and 17281 nonzeros.
                Reduced MIP has 1164 binaries, 77 generals, 0 SOSs, and 0 indicators.
                Presolve time = 0.12 sec. (21.86 ticks)
                Probing fixed 1 vars, tightened 6 bounds.
                Probing time = 0.23 sec. (12.29 ticks)
                Cover probing fixed 0 vars, tightened 7 bounds.
                Clique table members: 13300.
                Tightened 1 constraints.
                MIP emphasis: balance optimality and feasibility.
                MIP search method: dynamic search.
                Parallel mode: deterministic, using up to 2 threads.
                Root relaxation solution time = 3.50 sec. (338.49 ticks)

                Nodes Cuts/
                Node Left Objective IInf Best Integer Best Bound ItCnt Gap

                0 0 41.0000 435 41.0000 2925
                0 0 41.0000 257 Cuts: 112 3667
                0 0 41.0000 372 Cuts: 378 4820
                0 0 41.0000 304 Cuts: 44 5316
                0 0 41.0000 307 Cuts: 577 5980
                • 0+ 0 42.0000 41.0000 5980 2.38%
                Found incumbent of value 42.000000 after 19.31 sec. (1952.35 ticks)

                Repeating presolve.
                Tried aggregator 4 times.
                MIP Presolve eliminated 4371 rows and 1521 columns.
                MIP Presolve modified 636 coefficients.
                Aggregator did 223 substitutions.
                Reduced MIP has 1072 rows, 429 columns, and 3065 nonzeros.
                Reduced MIP has 218 binaries, 3 generals, 0 SOSs, and 0 indicators.
                Presolve time = 0.09 sec. (23.44 ticks)
                Represolve time = 0.23 sec. (34.23 ticks)

                Root node processing (before b&c):
                Real time = 19.42 sec. (1951.52 ticks)
                Parallel b&c, 2 threads:
                Real time = 0.00 sec. (0.00 ticks)
                Sync time (average) = 0.00 sec.
                Wait time (average) = 0.00 sec.

                Total (root+branch&cut) = 19.42 sec. (1951.52 ticks)
                1st status: Unbounded 2

                === End of all solves === Memory Usage 57649432 bytes
                ++++ Terminated with cplex status = 2

                • SystemAdmin
                  SystemAdmin
                  7929 Posts
                  ACCEPTED ANSWER

                  Re: Unbound status, but integer solution is found

                  ‏2013-03-04T13:34:07Z  in response to SystemAdmin
                  By now we have confirmed that the issue is indeed with repeated presolve and the only work around available at the moment is to disable repeated presolve.
                  • SystemAdmin
                    SystemAdmin
                    7929 Posts
                    ACCEPTED ANSWER

                    Re: Unbound status, but integer solution is found

                    ‏2013-03-04T14:18:49Z  in response to SystemAdmin
                    Thanks, Daniel.
                  • SystemAdmin
                    SystemAdmin
                    7929 Posts
                    ACCEPTED ANSWER

                    Re: Unbound status, but integer solution is found

                    ‏2013-03-05T14:38:57Z  in response to SystemAdmin
                    Indeed, the issue is caused due to repeated presolve and then being able to prove optimality in probing or some other presolve reductions.

                    It will be fixed in a future release (but unfortunately, it was too late for the CPLEX 12.5.0.1 release). For now, you either need to disable repeated presolve, or just tweak the status yourself: if it says infeasible but there is an incumbent, then the correct status is "optimal". For the unbounded case, it is less clear. It could still be unbounded. You would need to query the best (i.e., dual) bound and check whether this is finite.
                    Tobias
      • T_O
        T_O
        440 Posts
        ACCEPTED ANSWER

        Re: Unbound status, but integer solution is found

        ‏2013-02-22T21:52:42Z  in response to SystemAdmin
        That's strange. If I disable either primal or dual reductions or the complete presolver or if I set the presolver application limit to 1, I obtain an optimal solution. I think one of the CPLEX-people should have a look at it.

        Best regards,
        Thomas
        • SystemAdmin
          SystemAdmin
          7929 Posts
          ACCEPTED ANSWER

          Re: Unbound status, but integer solution is found

          ‏2013-02-23T09:56:56Z  in response to T_O
          I should also mention that the same problem could also be solved by OPL IDE x64 which read in the original input data, created a model, and solved it using all default settings. When I compared its log file with that of the cplex x64 (with unbound status), there were differences in probing results, leading to different end results.
          • SystemAdmin
            SystemAdmin
            7929 Posts
            ACCEPTED ANSWER

            Re: Unbound status, but integer solution is found

            ‏2013-03-01T09:00:30Z  in response to SystemAdmin
            Could you please attach the two log files.
            This way we can check whether we reproduce the exact same issue here.