[Haskell-cafe] Linear programming in Haskell

[Alberto Ruiz]

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 at gmail.com <mailto:wasserman.louis at gmail.com>
> http://profiles.google.com/wasserman.louis
> 
> 
> On Wed, Feb 24, 2010 at 4:07 AM, Alberto Ruiz <aruiz at um.es 
> <mailto:aruiz at 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
> 
> 
>