Re: [Haskell-cafe] Linear programming in Haskell
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 ... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear programming in Haskell
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.lo...@gmail.com http://profiles.google.com/wasserman.louis On Mon, Mar 1, 2010 at 9:29 AM, Henning Thielemann lemm...@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 ... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear programming in Haskell
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 $ dosetDirection 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 ... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear programming in Haskell
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.lo...@gmail.com http://profiles.google.com/wasserman.louis On Sun, Feb 28, 2010 at 5:24 PM, Henning Thielemann schlepp...@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 $ dosetDirection 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 ... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
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 $ dosetDirection 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.lo...@gmail.com mailto:wasserman.lo...@gmail.com http://profiles.google.com/wasserman.louis On Wed, Feb 24, 2010 at 4:07 AM, Alberto Ruiz ar...@um.es mailto:ar...@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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear programming in Haskell
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 $ dosetDirection 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.lo...@gmail.com http://profiles.google.com/wasserman.louis On Wed, Feb 24, 2010 at 4:07 AM, Alberto Ruiz ar...@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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear programming in Haskell
On Thursday 18 February 2010 11:26:02 Ozgur Akgun wrote: I've no idea about the GLPK system. But, isn't it the case that you can transform any linear inequality into a linear equality and a slack (or excess) variable? Well yes, but the slack variables are constrained to be nonnegative, which isn't essentially different from having arbitrary inequalities (but it's convenient). The problem doesn't reduce to solving a system of linear equalities (as an illustration of how it's more tricky than linear equalities, the question of whether the problem is in P was settled quite recently, in 1972. (Recently when compared to classical linear algebra :))). Greetings, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear programming in Haskell
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/ 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear programming in Haskell
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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear programming in Haskell
I've no idea about the GLPK system. 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. 2010/2/17 Daniel Peebles pumpkin...@gmail.com 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 matthias.goerg...@googlemail.com 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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Ozgur Akgun ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear programming in Haskell
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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear programming in Haskell
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/) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear programming in Haskell
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. Alberto Daniel Peebles wrote: 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 felipe.le...@gmail.com mailto:felipe.le...@gmail.com 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-LinearAlgebra-Algorithms.html#v%3AlinearSolve [2] http://hackage.haskell.org/packages/archive/hmatrix/0.8.3.1/doc/html/Numeric-LinearAlgebra-LAPACK.html#v%3AlinearSolveR HTH, -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org mailto:Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear programming in Haskell
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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear programming in Haskell
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/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear programming in Haskell
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 matthias.goerg...@googlemail.com 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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear programming in Haskell
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
Re: [Haskell-cafe] Linear programming in Haskell
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 felipe.le...@gmail.comwrote: 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear programming in Haskell
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-LinearAlgebra-Algorithms.html#v%3AlinearSolve [2] http://hackage.haskell.org/packages/archive/hmatrix/0.8.3.1/doc/html/Numeric-LinearAlgebra-LAPACK.html#v%3AlinearSolveR HTH, -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear programming in Haskell
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 felipe.le...@gmail.comwrote: 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-LinearAlgebra-Algorithms.html#v%3AlinearSolve [2] http://hackage.haskell.org/packages/archive/hmatrix/0.8.3.1/doc/html/Numeric-LinearAlgebra-LAPACK.html#v%3AlinearSolveR HTH, -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
