[Haskell-cafe] Linear programming in Haskell

[Louis Wasserman]

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

main = print =<< glpSolveVars mipDefaults lp

This requires GLPK to be installed, like below.

Louis Wasserman
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> 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
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100225/c1274c91/attachment.html