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)
Keywords: mixed integer linear programming, rounding errors, mixed integer rounding
$offText
Set
i / 1*20 /
ii(i) / 2*19 /;
Scalar s / 6 /;
Variable
obj
x(i);
Integer Variable x;
Equation
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';
);
```