[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re[3]: [Help-glpk] LPP & MIP
From: |
Andrew Makhorin |
Subject: |
Re[3]: [Help-glpk] LPP & MIP |
Date: |
Sat, 31 Jul 2004 07:22:13 +0400 |
>Unfortunately, I don't understand why integer row singleton cannot be
>eliminated. It might (in part) explain why the attached file doesn't work
>(yet). (I began to wrote a longer email then I wanted to verify my
>assumptions then I wrote this piece of code then time goes so fast...)
Not all transformations performed by lpp can be applied to mip. Let, for
example, there be a column singleton, i.e. structural variable x has
non-zero constraint coefficient in the only constraint:
(...) + a * x = b. (1)
In this case the term (a * x) can be thought as a slack variable, and
if, say, a > 0 and x >= 0, we may eliminate this term:
(...) <= b. (2)
However, if x is of integer kind, such transformation cannot be applied,
because the left-hand side in (2) would be restricted to take on only
the values b (when x is 0), b - a (when x is 1), b - 2*a (when x is 2),
etc., while in lp it can take on any value not greater than b.
Andrew Makhorin