Re: [Haskell-cafe] Linear programming in Haskell

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