help-glpk
[Top][All Lists]

## [Help-glpk] Newbie - Having trouble with superfluous slack variables?

 From: Pieter Thysebaert Subject: [Help-glpk] Newbie - Having trouble with superfluous slack variables? Date: Thu, 8 Aug 2002 14:59:56 +0200

```Hello,

I'm new to this mailing list.

I've searched the archives but haven't found what I'm looking for.

In my problem (which is an MIP problem), I encounter a situation like this:
for all i in some Set, a linear inequality must hold, where the left hand
side is a sum over "some" structural variables.
The actual variables that appear in this sum vary greatly depending on
several input constants to the problem, and the index variable used in the
sum ranges not between two constants but between the max of several values
and the minimum of several other values.

In other words, it is not clearly visible from the (short but non-standard
form of the) problem formulation what variables will show up in what
inequalities.

So I wrote a C program that translates these equalities into rows of the
constraint matrix (introducing  a new slack variable for each inequality).

However, beacuse the index variable in the sum does not range over the same
fixed set for each inequality, it happens that , for two different values of
the parameter i mentioned above, two inequalities become equivalent.
So I get two equivalent rows in the constraint matrix...

Maybe it's me, but I haven't been able to solve even the simplest problem
which contains said equivalence between two rows of the constraint matrix.

(e.g. minimize z where x1 = z >= 1 and x2 = z >= 1 ends with "PROBLEM HAS NO
FEASIBLE SOLUTION" when I call lpx_simplex()

So I guess my question is:

1) What am I doing wrong?
or
2) Is an operation needed to get rid of said duplicate rows in the constraint
matrix?
3) If so, is a function that has such an effect available in glpk?

Pieter

```