Topic
9 replies Latest Post - ‏2013-03-19T19:08:30Z by SystemAdmin
SystemAdmin
SystemAdmin
7929 Posts
ACCEPTED ANSWER

Pinned topic Negative Gap

‏2013-03-08T17:59:12Z |
I solved this small, very tight MIP problem (.sav is attached) using cplex 12.5 (64bits) and got negative gap, i.e. 0bj of integer solution (29) < that of lp solution (30). I saw in one of the threads, so I thought it was some rounding error of coefficients that makes the problem ill conditioned and tried to make them more accurate but didn't work. Then I used cplex 12.4 (64bits) and cplex 12.5 (32bits) to solve the same original .sav file, and they both gave me correct answer, i.e. integer = lp solution (30). This is the only instance i had such a negative gap problem out of more than 3000 instance-model. Is this a bug or did I do something wrong? Thanks all in advance.
Updated on 2013-03-19T19:08:30Z at 2013-03-19T19:08:30Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    7929 Posts
    ACCEPTED ANSWER

    Re: Negative Gap

    ‏2013-03-08T21:59:56Z  in response to SystemAdmin
    What OS and what machine do you use for the 12.5/64bit run that produces the 29 integer optimal solution?
    I just tried on an Intel Core 2 Duo with Linux and got an integer optimal solution of 30.
    • SystemAdmin
      SystemAdmin
      7929 Posts
      ACCEPTED ANSWER

      Re: Negative Gap

      ‏2013-03-09T09:58:30Z  in response to SystemAdmin
      Windows 7-64bits on Intel Core i7-3779@3.4GHz, 16GB RAM. Its log file is attached.
      • SystemAdmin
        SystemAdmin
        7929 Posts
        ACCEPTED ANSWER

        Re: Negative Gap

        ‏2013-03-09T10:00:02Z  in response to SystemAdmin
        sorry, mistyped; it should be 3770 not 3779.
        • T_O
          T_O
          443 Posts
          ACCEPTED ANSWER

          Re: Negative Gap

          ‏2013-03-09T10:24:15Z  in response to SystemAdmin
          Same result here (Cplex 12.5, Windows 7 64-bit, 16 GB Ram, i7 3520M @ 2,9GHz).

          Also happens after writing/reading an (r)lp file.

          Best regards,
          Thomas
          • T_O
            T_O
            443 Posts
            ACCEPTED ANSWER

            Re: Negative Gap

            ‏2013-03-09T10:27:17Z  in response to T_O
            CPLEX> dis sol qual
            Incumbent solution:
            MILP objective                                2.9000000000e+001
            MILP solution norm |x| (Total, Max)           2.03580e+003 2.90000e+001
            MILP solution error (Ax=b) (Total, Max)       1.96732e-013 1.42109e-014
            MILP x bound error (Total, Max)               0.00000e+000 0.00000e+000
            MILP x integrality error (Total, Max)         0.00000e+000 0.00000e+000
            MILP slack bound error (Total, Max)           1.93000e+002 1.20000e+001
            CPLEX>
            


            MST attached.

            Attachments

            Updated on 2014-03-24T22:36:05Z at 2014-03-24T22:36:05Z by iron-man
      • SystemAdmin
        SystemAdmin
        7929 Posts
        ACCEPTED ANSWER

        Re: Negative Gap

        ‏2013-03-11T06:34:20Z  in response to SystemAdmin
        Thanks, I reproduced the problem here.
        We are investigating.
  • SystemAdmin
    SystemAdmin
    7929 Posts
    ACCEPTED ANSWER

    Re: Negative Gap

    ‏2013-03-11T03:21:10Z  in response to SystemAdmin
    Same result here (CPLEX 12.5, Linux Mint 64 bit). I matched Thomas's results, including the large slack bound errors. Kappa statistics had 100% of the bases stable.

    Turning off presolve eliminated the problem. In fact, turning off just repeat presolve fixed it.

    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)