[Haskell-cafe] Linear programming in Haskell

[Louis Wasserman]

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 at gmail.com
http://profiles.google.com/wasserman.louis


On Sun, Feb 28, 2010 at 5:24 PM, Henning Thielemann <
schlepptop at 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
>  ...
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100228/2a3b3e73/attachment.html