Discover the best of the web!
Learn more about Digg by taking the tour.
The GNU Linear Programming Kit, Part 1: Introduction to linear optimization
128.ibm.com — The GNU Linear Programming Kit is a powerful, proven tool for solving numeric problems with multiple constraints. This article introduces GLPK, the glpsol client utility, and the GNU MathProg language to solve the problem of optimizing the operations for Giapetto's Woodcarving, Inc., a fictional toy manufacturer.
3monkeys- 423 diggs
- digg it
- jonnyeh, on 10/12/2007, -1/+8Linear Programming (or LP) is not 'programming' in the computer science sense. It's a field of study for optimizing systems. It works based on variables, constraints, and an objective function.
http://en.wikipedia.org/wiki/Linear_programming
Also, most computer programs for solving large LP problems are VERY expensive, does anyone know if glpk is as capable as those? (e.g. LINDO)- trigger0219, on 10/12/2007, -0/+1Since these can be represented as matrices, and then solving, simply AX=b, I'd assume pushing some of this to the GPU would be beneficial.
(note: I'm not sure, they might have) - SuperSloth, on 10/12/2007, -0/+2trigger:
http://www.gpgpu.org/ - tallest, on 10/12/2007, -0/+1@trigger0219
http://www.cs.umd.edu/~jjung/research/cholgpu/index.html
might answer your question (not my work)
[edit] SpuerSloth was faster than I - BrewmasterC, on 10/12/2007, -0/+3Commercial LP solver benchmarks:
http://plato.asu.edu/ftp/lpcom.html
Free LP solver benchmarks:
http://plato.asu.edu/ftp/lpfree.html
It looks like the GNULP beat the others on:
NAME ROWS COLS NONZERO_ENTRIES
nsct2 23004 14981 686396
dano3mip_lp 3203 13873 79656
And was slower than many on:
NAME ROWS COLS NONZERO_ENTRIES
pds-40 66845 212859 605678
So just from glancing at that I would say the GNULP solver is ok on dense stuff, but needs some work on sparse constraint matrices. - drlog, on 10/12/2007, -0/+1Ive been using ILOG CPLEX, lp_solve and GLPK. From experience, CPLEX is the best but also very expensive and not open. GLPK is *VERY* good but not the best.
I tried writing my own once...it worked for small problems but didn't scale :(
- trigger0219, on 10/12/2007, -0/+1Since these can be represented as matrices, and then solving, simply AX=b, I'd assume pushing some of this to the GPU would be beneficial.
- antheo, on 10/12/2007, -0/+1
Thanks for the pointer. I'd like to see how the GNU Linear programming kit compares to ILOG CPLEX: http://www.ilog.com/products/optimization/- cogit0, on 10/12/2007, -1/+2(tempted to make some dereferencing pointers joke, but refrains)
- Xalorous, on 10/12/2007, -0/+2optimization is awesome. nice toolkit. better than using spreadsheet and solver function.
- thedude603, on 10/12/2007, -0/+0Optimization is great indeed ($$$$). Anyone know of any open source INTEGER programmers? I work for a financial software company, we use a proprietary IP written 10+ years ago in APL, its powerful but we're re-writing in C# and are forced to use a COM Interop in order to maintain the old code.
- oooohan, on 10/12/2007, -0/+0glpk can do basic branch-and-bound for IP, IIRC. This won't be of much use for very large scale problems. You may also be interested in SYMPHONY from COIN-OR (http://www.coin-or.org/), which has, or will, implement cuts in addition to branch-and-bound.
- aiiee, on 10/12/2007, -0/+2Last time I worked with linear programming ( about 20 years ago ) there was a PC app called "What's Best!" by an outfit called General Optimization :) Don't know if they're still around, but the price was about $60 and it worked well enough for what I wanted at the time.
- Moly, on 10/12/2007, -0/+1Yeah, but does it support Karmarkar's algorithm?
© Digg Inc. 2008 —
Content posted by