LPSolve solution to simple MILP is violating constraints.

Question

I have the following MILP program:

min: delta;

M = 1000;

/* First */
p        <= delta + y1 M;
-p       <= delta + y1 M;
2p - 10  <= delta + y1 M;
-2p + 10 <= delta + y1 M;
p + 7    <= delta + y1 M;
-p - 7   <= delta + y1 M;

/* Second */
p - 4    <= delta + y2 M;
-p + 4   <= delta + y2 M;
2p - 2   <= delta + y2 M;
-2p + 2  <= delta + y2 M;
p + 1    <= delta + y2 M;
-p-1     <= delta + y2 M;

y1 + y2  <= 1;
p >= 0;
bin y1,y2;

The idea is that when $y_1 = 1$, the large constant $M$ basically "turns off" the first set of constraints.

According to lpsolve, the optimal is at $$\delta = p = y1 = y2 = 0$$

Obviously this is not a solution since $$p + 1 <= 0 + 0 * 1000$$ is not true.

I have tried adjusting the tolerance parameters (EPSB,EPSD,EPSEL,EPS Int) as well as the constant $$M$$ without any luck.

Answer 1

Could be that the required tolerance in declaring a variable as integer in the solver is high, i.e., 0.001 is considered close enough to zero after the relaxation is solved. With that value on $y_2$, the constraint is feasible. As a post-processing step in the solver, the binary variables are rounded, and now the solution is no longer feasible.

I don't know if that is exactly the case here, but it is a very common phenomena. Weak tolerances combined with large big-M constants and post-processing of solution.