rasheedja/simplex-method

Implementation of the two-phase simplex method in exact rational arithmetic.

simplex-method's Issues

Adding positivity constraints change the result

Hello,

I have these constraints:

[LEQ {lhs = fromList [(1,1 % 1),(2,1 % 1),(3,0 % 1)], rhs = 1 % 1},LEQ {lhs = fromList [(1,1 % 1),(2,0 % 1),(3,1 % 1)], rhs = 1 % 1}]

and the objective is to maximize the first variable.

I get this result:

Just (Result {objectiveVar = 6, varValMap = fromList [(1,1 % 1),(6,1 % 1)]})

Variables 2 and 3 do not appear in this resut.

Now I add the constraints "variable 2 positive" and "variable 3 positive":

[LEQ {lhs = fromList [(1,1 % 1),(2,1 % 1),(3,0 % 1)], rhs = 1 % 1},LEQ {lhs = fromList [(1,1 % 1),(2,(-1) % 1),(3,0 % 1)], rhs = 0 % 1},LEQ {lhs = fromList [(1,1 % 1),(2,0 % 1),(3,(-1) % 1)], rhs = 0 % 1},LEQ {lhs = fromList [(1,1 % 1),(2,0 % 1),(3,1 % 1)], rhs = 1 % 1}]

Then I get the expected results, with variables 2 and 3 present this time:

Just (Result {objectiveVar = 8, varValMap = fromList [(1,1 % 2),(2,1 % 2),(3,1 % 2),(8,1 % 2)]})

Is it normal? That sounds strange to me, because the positivity constraints should be implicit, no?

Unexpected results for simple (degenerate) cases

Thanks for this, it's quite useful and seems to work in most cases, but there are some weird results I don't quite understand. Here's some things that work as expected:

• minimize x st x>=0, twoPhaseSimplex (Min [(1,1)]) [GEQ [(1,1)] 0): correct 0
• maximize x st x>=0, twoPhaseSimplex (Max [(1,1)]) [GEQ [(1,1)] 0): correct Nothing
• maximize -x st x>=0, twoPhaseSimplex (Max [(1,-1)]) [GEQ [(1,1)] 0): correct 0
• minimize -x st x>=0, twoPhaseSimplex (Min [(1,-1)]) [GEQ [(1,1)] 0): correct Nothing

But if I flip the constraint, either by using LEQ or negating it, the unbounded cases seem to fail:

• maximize x st x<=0, twoPhaseSimplex (Max [(1,1)]) [LEQ [(1,1)] 0): correct 0
• minimize x st x<=0, twoPhaseSimplex (Min [(1,1)]) [LEQ [(1,1)] 0): incorrect 0
• maximize -x st x<=0, twoPhaseSimplex (Max [(1,-1)]) [LEQ [(1,1)] 0): incorrect 0
• minimize x st -x>=0, twoPhaseSimplex (Min [(1,1)]) [GEQ [(1,-1)] 0): incorrect 0

Am I doing something wrong or misinterpreting something? I can reproduce this with various multiple varibles as well, but it only seems to happen when I'm essentially saying to minimize variables that are bounded above (rather than below).