[Help-glpk] Re: determining fixed variables

[Andrew Makhorin]

>I was wondering how I could use GLPK to determine
>the variables (if any) whose values are fixed by the
>constraints.
>
>For example, given the problem:
>
>maximize a
>subject to:
> a + b = 1
> a + b + c = 1
>
>I'd like to deduce that c = 0.

Using glpk api you can determine all such variables by solving your
problem with different objectives:

   minimize x[1]

   maximize x[1]

   minimize x[2]

   maximize x[2]

   etc.

If abs(min x[j] - max x[j]) < eps, x[j] is implicitly fixed.

Another way is to use glpk lp presolver (see glplpp.c). However, there
are few chances that *all* such variables will be identified.

>On the MIP side, given the binary ILP problem:
>
>maximize ...
>subject to:
>  a + b + c = 2
>  a + b + d = 1
>
>is it possible for GLPK to deduce that d = 0?
>
>Is it possible to find all fixed variables for an LP
>problem? for an MIP problem?

Theoretically, the same technique can be used as for lp, i.e. solving
mip with different objectives.