Re: [Help-glpk] Confused by error messages

[Michael Hennebry]

On Tue, 3 Apr 2007, Andrew Makhorin wrote:

> The error appears due to very large coefficients in some constraints
> in your instance. In particular:
>
> OL1_MEMv1n1__MEMv0n1: + 4878963.5 d_MEMv1n1__MEMv0n1
> + 4878963.5 c_MEMv1n1__MEMv0n1 + X_MEMv0n1 - W_MEMv1n1 - X_MEMv1n1 >= 0
> OL1_ADDv0n1__MEMv0n1: + 4878963.5 d_ADDv0n1__MEMv0n1
> + 4878963.5 c_ADDv0n1__MEMv0n1 + X_MEMv0n1 - W_ADDv0n1 - X_ADDv0n1 >= 0
> OL1_PBRv0n1__MEMv0n1: + 4878963.5 d_PBRv0n1__MEMv0n1
> + 4878963.5 c_PBRv0n1__MEMv0n1 + X_MEMv0n1 - W_PBRv0n1 - X_PBRv0n1 >= 0
>
> Since c_MEMv1n1__MEMv0n1, c_ADDv0n1__MEMv0n1, etc. are binary
> variables, any error in their values within a tolerance about 1e-5
> (that is tol_int) gives the error in residuals about 4878963.5 * 1e-5 =
> = 48.8 that is just reported by the glpk solver.
>
> Your model is badly formulated, and I think many solvers would have
> numeric difficulties on solving it. You could try decreasing tol_int
> to, say, 1e-8; however, a much better and reliable way would be
> reformulating the model to get rid of such large coefficients.

It looks like something generated by the big-M method.
If you have a lower bound on X_MEMv0n1 - W_MEMv1n1 - X_MEMv1n1,
the big-M in the first constraint can be reduced to the negative
of the bound
If all its variables are binary,
only 4 out of 32 combinations are infeasible.
The first constraint could be replaced
by 4 constraints with unit coefficients.
The convex hull would probably require more,
but would likely be worth it.

-- 
Mike   address@hidden
"Finally, mount the partition, not the virgin."  --  Charles Curley