[Help-glpk] Re: MIP rounding

[Andrew Makhorin]

Thank you for your information.

>I recently found a strange behavior in GLPK. When I input the following
>problem :
>
>Minimize
>obj: c
>Subject To
>cst: x - 1000000.0 c <= 0
>Bounds
>0.5 <= x
>Binaries
>c
>End
>
>Whose solution is c = 1, x = 0.5. (min = 1)
>GLPK is quite happy to answer c = 0, x = 0.5. (min = 0 !)
>
>I understand that the large (1e6) coefficient is the cause of the
>problem (the relaxed having solution c=5e-7, x=0.5, and c being
>assimilated as the integer 0), but a basic check for feasibility would
>be nice (or trying to solve the LP with integer variables fixed to
>their optimal values).

This is a common difficulty that arises due to "big M". In fact, one
could think that c = 0, x = 0.5 is wrong answer, because then the
constraint x - 1e6 c <= 0 is violated with the absolute error 0.5.
However, absolute error is not an adequate measure of infeasibility,
because it can be made arbitrary small or large simply by scaling
constraint coefficients. Thus, scaling the constraint in order to
normalize constraint coefficients we have 1e-6 x - c <= 0, in which
case the absolute error is 0.5e-6. Although in your case it is obvious
how to obtain the answer which is mathematically correct, it is
impossible in general case, if the problem is ill-conditioned and
inexact arithmetic is used, because actually the solver finds the
solution of some slightly perturbed problem, not the original one.

>btw, when asked to output an MPS file for this problem, glpsol omits the
>'RHS' part (which is empty) which is problem for some solvers (SBB,
>LP_SOLVE).

I consulted the "IBM Optimization Library Guide and Reference" (it is
publically available on the internet). In the section "Passing your
model using MPS format", subsection "Order of records" there is the
phrase: "The RHS, RANGES, and BOUNDS sections are optional." (In fact,
the RHS section was mandatory only in old versions of the MPS format
where the BOUNDS section was not used, i.e. all structural variables
could be only non-negative.)

Andrew Makhorin