How would you use hmatrix? By linear programming I assume he means systems of linear inequalities, as typically solved by the simplex algorithm. I too am interested in this question (and the more general one of nonlinear optimization)! Thanks, Dan On Tue, Feb 16, 2010 at 2:54 PM, Felipe Lessa wrote:

On Tue, Feb 16, 2010 at 01:37:54PM -0600, Louis Wasserman wrote:

...

Is there a nice package out there somewhere with a linear programming implementation? Preferably with a nicely functional interface?

hmatrix?

Cheers,

-- Felipe. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

As far as I can see, you'd use that for systems of linear *equalities*, but for systems of linear *inequalities* with a linear objective function, it's not suitable. I may be wrong though :) On Tue, Feb 16, 2010 at 3:37 PM, Felipe Lessa wrote:

On Tue, Feb 16, 2010 at 03:12:53PM -0500, Daniel Peebles wrote:

...

How would you use hmatrix? By linear programming I assume he means systems of linear inequalities, as typically solved by the simplex algorithm. I too am interested in this question (and the more general one of nonlinear optimization)!

I have never used this part of hmatrix, but does Numeric.LinearAlgebra satisfy your needs? In particular, see linearSolve[1] and linearSolveR[2].

[1] http://hackage.haskell.org/packages/archive/hmatrix/0.8.3.1/doc/html/Numeric... [2] http://hackage.haskell.org/packages/archive/hmatrix/0.8.3.1/doc/html/Numeric...

HTH,

-- Felipe. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Alberto Ruiz wrote:

I think that GSL does not include linear programming solvers, but in the GSL home page there is a reference to the GLPK package:

http://www.gnu.org/software/glpk/glpk.html

I have not used it, but it would be very nice to have a simple Haskell interface to GLPK (or other similar library) in hmatrix or as a separate package. I will take a look at this.

I used GLPK many years ago and I found it excellent. Erik -- ---------------------------------------------------------------------- Erik de Castro Lopo http://www.mega-nerd.com/

Hello Alberto, Thank you! I don't have a problem calling for LP at hand right now, but some time ago I was looking for such a package. Now I know where to look next time :) Greetings, Daniel On Wednesday 24 February 2010 11:07:08 Alberto Ruiz wrote:

I have uploaded to hackage an interface to the simplex algorithm based on GLPK. It is a very early version, it will probably have lots of problems. In the future I would like to add support for integer variables (MIP). Any suggestion is welcome.

Louis Wasserman wrote:

Yo,

Man, I'd never used FFI before, but it's really not as scary as I'd feared.

The FFI is fantastic. We can even use C higher order functions with normal Haskell function arguments... :)

I've implemented a more comprehensive interface to GLPK's simplex solver and -- rather importantly, for my own needs -- its MIP solver. This doesn't depend on hmatrix, and in fact, it doesn't require any matrix or vector manipulation at all -- linear functions are specified as a straight-up Data.Map from an arbitrary variable type to their coefficients.

I like your interface, it is very complete and user friendly. (I used hmatrix because of (my own) laziness, to take advantage of some utilities, but of course it is not really required.) Thanks for your work! Alberto

The library is now available as glpk-hs on hackage.

Example:

import Data.LinearProgram.LPMonad import Data.LinearProgram import Data.LinearProgram.GLPK

objFun :: LinFunc String Int objFun = linCombination [(10, "x1"), (6, "x2"), (4, "x3")]

lp :: LP String Int lp = execLPM $ do setDirection Max setObjective objFun leqTo (varSum ["x1", "x2", "x3"]) 100 leqTo (10 *^ var "x1" ^+^ 4 *& "x2" ^+^ 5 *^ var "x3") 600 -- c *^ var v, c *& v, and linCombination [(c, v)] are all equivalent. -- ^+^ is the addition operation on linear functions. leqTo (linCombination [(2, "x1"), (2, "x2"), (6, "x3")]) 300 varGeq "x1" 0 varBds "x2" 0 50 varGeq "x3" 0 setVarKind "x1" IntVar setVarKind "x2" ContVar

main = print =<< glpSolveVars mipDefaults lp

This requires GLPK to be installed, like below.

Louis Wasserman wasserman.louis@gmail.com mailto:wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis

On Wed, Feb 24, 2010 at 4:07 AM, Alberto Ruiz mailto:aruiz@um.es> wrote:

I have uploaded to hackage an interface to the simplex algorithm based on GLPK. It is a very early version, it will probably have lots of problems. In the future I would like to add support for integer variables (MIP). Any suggestion is welcome.

This is an example taken from "glpk-utils":

http://code.haskell.org/hmatrix/packages/glpk/examples/simplex3.hs

Documentation: http://perception.inf.um.es/~aruiz/hmatrix-glpk/ http://perception.inf.um.es/%7Earuiz/hmatrix-glpk/

Installation:

$ sudo apt-get install libglpk-dev $ cabal update $ cabal install hmatrix-glpk

If hmatrix is not installed we also need

$ sudo apt-get install libgsl0-dev liblapack-dev

I hope it is useful, Alberto

Erik de Castro Lopo wrote:

Alberto Ruiz wrote:

I think that GSL does not include linear programming solvers, but in the GSL home page there is a reference to the GLPK package:

http://www.gnu.org/software/glpk/glpk.html

I have not used it, but it would be very nice to have a simple Haskell interface to GLPK (or other similar library) in hmatrix or as a separate package. I will take a look at this.

I used GLPK many years ago and I found it excellent.

Erik

For reference: any Ord type can be used as a variable. (It's pretty sweet.) However, you have a good point. I just uploaded the newest version, which provides a newVariables monad operation for Enums. (This makes a key assumption that any element of [v..] will compare as greater than or equal to v, and that only the first element is equal to v...but that's true for most Enum implementors, and certainly most of the ones you'd be using as variables.) Now, your method would look like [x1, x2, x3] <- newVariables 3 Alternately, (x1:x2:x3:_) <- newVariables' -- returns an infinite list It's an expensive operation, though -- since I don't track the set of all variables as the LP is built, I need to construct the set of all variables before generating new ones -- so it's recommended that you get all the variables you need in one or two passes. (The new version has a few other neat features, like exporting/importing from CPLEX LP files. I've kind of been overdoing the Haskell lately...) Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis On Sun, Feb 28, 2010 at 5:24 PM, Henning Thielemann < schlepptop@henning-thielemann.de> wrote:

Louis Wasserman schrieb:

Yo,

...

Man, I'd never used FFI before, but it's really not as scary as I'd feared.

I've implemented a more comprehensive interface to GLPK's simplex solver and -- rather importantly, for my own needs -- its MIP solver. This doesn't depend on hmatrix, and in fact, it doesn't require any matrix or vector manipulation at all -- linear functions are specified as a straight-up Data.Map from an arbitrary variable type to their coefficients.

The library is now available as glpk-hs on hackage.

Example:

import Data.LinearProgram.LPMonad import Data.LinearProgram import Data.LinearProgram.GLPK

objFun :: LinFunc String Int objFun = linCombination [(10, "x1"), (6, "x2"), (4, "x3")]

lp :: LP String Int lp = execLPM $ do setDirection Max setObjective objFun leqTo (varSum ["x1", "x2", "x3"]) 100 leqTo (10 *^ var "x1" ^+^ 4 *& "x2" ^+^ 5 *^ var "x3") 600 -- c *^ var v, c *& v, and linCombination [(c, v)] are all equivalent. -- ^+^ is the addition operation on linear functions. leqTo (linCombination [(2, "x1"), (2, "x2"), (6, "x3")]) 300 varGeq "x1" 0 varBds "x2" 0 50 varGeq "x3" 0 setVarKind "x1" IntVar setVarKind "x2" ContVar

Using strings for variable names you cannot check for undefined variables. How about adding a function for generating new variables to your LP monad? The example may then look like

do setDirection Max setObjective objFun x1 <- newVariable x2 <- newVariable x3 <- newVariable

leqTo (varSum [x1,x2,x3]) 100 ...

If you're using the LPM monad, then this is about as easy as that: you use do (x1:x2:x3:_) <- newVariables ...... I mean, run is equivalent to run f = execLPM (newVariables >>= put . f) so...yeah, I think this is a reasonable solution. Alternatively, I'm almost positive there's a monad out there that lets you draw on unique values. It'd look something like type Variable = Int newtype UniqueM a = UniqueM (Variable -> (Variable, a)) -- monad instance, etc. getUnique :: UniqueM Variable getUnique = UniqueM (\ x -> (x+1, x)) Then you can use the LPT monad transformer to construct a linear program around this, just by working in the "LPT Variable c UniqueM" monad. That's actually a nicer solution than my current implementation. I'll do that, then... Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis On Mon, Mar 1, 2010 at 9:29 AM, Henning Thielemann < lemming@henning-thielemann.de> wrote:

On Sun, 28 Feb 2010, Louis Wasserman wrote:

It's an expensive operation, though -- since I don't track the set of all

...

variables as the LP is built, I need to construct the set of all variables before generating new ones -- so it's recommended that you get all the variables you need in one or two passes.

Then you might prefer a single operation that generates all variables and runs an enclosed problem on them:

run :: ([Variable] -> LP a) -> LP a

Use as

run $ \x0:x1:x2:_ -> do ...

Interesting. Do you have any details on this? It seems like it would be hard to express system of linear inequalities as a finite system of linear equations. Thanks, Dan 2010/2/17 Matthias Görgens

...

As far as I can see, you'd use that for systems of linear equalities, but for systems of linear inequalities with a linear objective function, it's not suitable. I may be wrong though :)

There's a linear [1] reduction from one problem to the other and vice versa.

[1] The transformation itself is a linear function, and it takes O(n) time, too.

But, isn't it the case that you can transform any linear inequality into a linear equality and a slack (or excess) variable? That's actually what you *need to do* to turn the problem into the canonical form, so that simplex can handle it.

Yes. The simplex is usually implemented in this form. If you just want to play around with linear programming in Haskell, you could try write an FFI wrapper aruond SCIP (http://scip.zib.de/). (Though the licence of scip is probably not what you want. But there are other solvers available, too.) The domain specific language (and compiler of the same name) ZIMPL may be worth a look for linear programming. (http://zimpl.zib.de/)

The trick is to use only non-negative variables for the equations. (That's considered OK in linear programming. Though you may consider it cheating.) By the way, linear programming over rational numbers is in P.