[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[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


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 

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?
2) Is an operation needed to get rid of said duplicate rows in the constraint 
3) If so, is a function that has such an effect available in glpk?


reply via email to

[Prev in Thread] Current Thread [Next in Thread]