4 ms·
Minimize your cloud costs with GLPK and Haskell
- raverbashing 14y agoVery insightful Linear Programming is one of those things that's usually underrated (and sometimes overrated) But I would probably not use Haskell and just create the problem as a text file in whatever format GLPK accepts - probably a derivative of 'the standart format' (which is bad for very complex problems, still)
- yummyfajitas 14y agoI didn't know glpk takes text input. I'd write the program anyway, however - the text file would actually be quite large. This problem has 15 variables and 27 constraints (if I counted correctly). Your plain text input to glpk would be at least 43 lines long (counting the objective function), compared to about 30 lines of haskell. If your usage pattern varied daily (e.g., one pattern for monday, a different one for tuesday), your input would become even bigger. The only modification to the haskell code would be: main = do printLPSolution (Map.fromList [ ("mon_0", 12.2), ("mon_1", 25.1), ("mon_2", 53.5), ("tues_0", 15.8), ("tues_1", 33.9), ("tues_2", 76.2), ... ])
- raverbashing 14y agoYes Here's the docs for the language glpk uses http://www.cs.unb.ca/~bremner/docs/glpk/gmpl.pdf http://www.cs.unb.ca/~bremner/docs/glpk/gmpl.pdf Yeah, with 15 (effective) variables it's better to write in some higher level way. And there's always the canonical way, but that's awful to write by hand, like k00.v00 + K01.v01 + K02.v02 + k03.v03 < C0 k10.v10 + K11.v11 + K12.v12 + k13.v13 < C1
- DennisP 14y agoI used it for a problem recently, and just wrote code to generate the text file for me.
- larrydag 14y agoglpk takes text input, csv input, and certain database inputs.
- Peaker 14y agoPlease insert a newline somewhere in there so your alignment doesn't throw off all the code to the right-most 1/4 of the screen...
- lrem 14y agoIs this considered a nice Haskell style for this kind of programs? If so, I prefer how LP looks in Python. If someone is interested, my presentation slides: http://www-sop.inria.fr/members/Remigiusz.Modrzejewski/presentations/python_2012.pdf http://www-sop.inria.fr/members/Remigiusz.Modrzejewski/prese... Note this presentation was given to an audience that mostly knew ILP and has used it before for combinatorial optimization, so I'm not gentle with theory. It's just to show that Python is a little nicer than Java to do it.
- tome 14y agoYour Python DSL looks very nice. There's no reason a Haskell one couldn't look equally nice.
- dons 14y agoIndeed, with type information you can do quite sophisticated embedded DSLs that heavily reuse the host language's infrastructure for variables, control and types. So no need for the LpVariable stuff, for example, and you get type safety. An example of an SMT solver DSL, which: * reuses Haskell's type checker to check the types of the embedded language, * uses Haskell's polymorphism to add polymorphism to the underlying language * and the host language's variables as target language variables. http://code.haskell.org/~dons/docs/yices-painless/Yices-Painless-Language.html http://code.haskell.org/~dons/docs/yices-painless/Yices-Pain...
- yummyfajitas 14y agoIt's throwaway code written for a blog post, and could certainly be cleaned up. However, Python code to solve the same problem would probably look very similar to the Haskell code. The initial example given in that presentation has only 4 variables and 4 constraints (slide 5), I have 15 and 27. Once you get to bigger problems, python code winds up looking similarly ugly. See lines 14-15 in that presentation. As the problems get bigger, your code isn't representing the LP problem. It's translating a small problem specification into a much bigger LP problem.
- ozataman 14y ago
- ozataman 14y agoThis is great, but the Github literate Haskell code looks so much better (cleaner, syntax highlighting, etc.) than your blog formatting - I found the code fragments impossible to read. The literate Haskell version on Github: https://github.com/stucchio/Cloud-capacity-planning/blob/master/cloud-planning.lhs https://github.com/stucchio/Cloud-capacity-planning/blob/mas...
- spitfire 14y agoCool that they're using Haskell for something. But this would be much better done in Mathematica, Octave, R or Macsyma. It's an operations research optimization problem and all of those environments have packages for OR.
- yummyfajitas 14y agoWhy would it be better in one of those languages? I'd be very surprised if it was as easy to set up the problem in R or Macsyma. In those languages, you'd probably need to write loops to generate your constraints (but maybe I'm wrong, I'm no R-expert). But I'd love to see code proving me wrong.
- larrydag 14y agoThere are packages in R that use GLPK api calls so it would be made simpler. See Rglpk http://cran.r-project.org/web/packages/Rglpk/index.html http://cran.r-project.org/web/packages/Rglpk/index.html. But if one is originally coding in a particular langauge (in this case Haskell) then I would think coding within that language would be easier.
- Ralith 14y agoThe blog post demonstrates a package in Haskell that uses GLPK API calls to make things simpler.
- hazov 14y agoI do not know about the other languages, but in Octave there's a function called glpk that you can use and it accepts problems in the standard form. I tend to use clp these days but glpk is a good LP solver as well.
- spitfire 14y agoWell, my experience is in mathematica. Which has operations research functions built right in. Point being, there are systems where this is already a solve problem, where you can get your answer in a minute or two. So you'd simply do Minimize[function, {variables/constraints}] and then get on with your day.
- larrydag 14y agoIf others are interested in Linear Programming or more specifically the science of Operations Research you can look to Michael Trick's OR Blogroll. http://www.google.com/reader/shared/user/13121408505873356820/label/ORBlogRoll http://www.google.com/reader/shared/user/1312140850587335682...