[Haskell-cafe] Linear programming in Haskell

[Daniel Schüssler]

On Thursday 18 February 2010 11:26:02 Ozgur Akgun wrote:
> I've no idea about the GLPK system.
> 
> But, isn't it the case that you can transform any linear inequality into a
> linear equality and a slack (or excess) variable?

Well yes, but the slack variables are constrained to be nonnegative, which 
isn't essentially different from having arbitrary inequalities (but it's  
convenient). The problem doesn't reduce to solving a system of linear 
equalities (as an illustration of how it's more tricky than linear equalities, 
the question of whether the problem is in P was settled quite recently, in 
1972. ("Recently" when compared to classical linear algebra :))).

Greetings,
Daniel