badmip.gms : Rounding Problems in MIPs

Description

Most mixed-integer solvers are based on linear programming engines
which use floating-point arithmetic. Occasionally, this leads
to wrong solutions. Many MIP solvers failed on this example.

Neumaier and Shcherbina have suggested procedures to overcome
this problem. It should be the MIP below has a feasible space
which is one single point only and the relaxed solution is far
away from the integer solution. Most MIP codes will fail when
the upper bound of the variables are large. In practice, this
can be overcome by using tight upper bounds on integer variables
to get a good relaxation. Looking at the relaxed problem
will give more insight.

Reference

  • Neumaier, A, and Shcherbina, O, Safe Bounds in Linear and Mixed-Integer Programming. Mathematical Programming A to appear, (2003).

Small Model of Type : MIP


Category : GAMS Model library


Main file : badmip.gms

$title Rounding Problems in MIPs (BADMIP,SEQ=290)

$ontext

Most mixed-integer solvers are based on linear programming engines
which use floating-point arithmetic. Occasionally, this leads
to wrong solutions. Many MIP solvers failed on this example.

Neumaier and Shcherbina have suggested procedures to overcome
this problem. It should be the MIP below has a feasible space
which is one single point only and the relaxed solution is far
away from the integer solution. Most MIP codes will fail when
the upper bound of the variables are large. In practice, this
can be overcome by using tight upper bounds on integer variables
to get a good relaxation. Looking at the relaxed problem
will give more insight.


Neumaier, A, and Shcherbina, O, Safe Bounds in Linear and
Mixed-Integer Programming. Mathematical Programming A to appear,
(2003)

$offtext

sets i     / 1*20 /
     ii(i) / 2*19 /;

scalar s / 6 /;
variables obj x(i); integer variable x;
equations eq1, eq2(i), eq3, defobj;

eq1..  (s+1)*x('1') - x('2') =g= s - 1;

eq2(ii(i))..  -s*x(i-1) + (s+1)*x(i) - x(i+1) =g= power(-1,ord(i))*(s+1);

eq3.. -s*x('18') - (3*s-1)*x('19') + 3*x('20') =g= -(5*s-7);

defobj.. obj =e= - x('20');

model m /all /;

x.up(i)$(ord(i) <= 13) = 10;
x.up(i)$(ord(i) >= 14) = 1e6;

m.limcol=0; m.limrow=0;

solve m using mip min obj;

parameter sol(i) single point solution
          diff(i) difference with known solution;

sol(i) = round(2-mod(ord(i),2));

if(m.modelstat = %modelstat.Optimal% or
   m.modelstat = %modelstat.IntegerSolution%,
   diff(i) = round(x.l(i)-sol(i),6);
   if(card(diff)=0,
      display 'the correct solution was found -- congratulations'
   else
      display 'the solution is incorrect', sol;
      abort$1 'MIP found wrong solution' );
else
   solve m using rmip min obj;
   abort$1 'MIP failed' );