6 ms·
GNU Linear Programming Kit
- 6thaccount2 7y agoIt's really good to have GLPK & Open Solver (COIN OR Project) available for the public. The commercial solvers (CPLEX, GUROBI, XPRESS) might be significantly more robust and fster, but they are unbelievably expensive even for a non-commercial license. Open-Solver allows me to prototype on small models without getting a loan.
- sansnomme 7y agoGive MSFT's Z3 a try too.
- 6thaccount2 7y agoThanks for the tip... I'll check it out.
- spsx 7y agoI believe they are all free for academic use. There is also SCIP, one of the fastest academic solvers but you also need a license for commercial use, although I think the license is much cheaper than CPLEX and Gurobi.
- 6thaccount2 7y agoI work at a non-profit and not a University, so I can't use them for free. My very nice, but slightly used car cost me less money and it has been driven over an hour per day for 7 years. That makes those solvers very hard for me to justify outside of production where the license costs are worth every darn penny.
- spsx 7y agoI totally agree. But if you are a non-profit you might be able to get a SCIP license for free, you just have to contact the people behind it. But if a moderate performance improvement is not that important for you then GLPK is definetly the best option.
- 6thaccount2 7y agoThe problems we solve (and the timeframe we're under) are among the hardest in the OR sector. Not using CPLEX or GUROBI isn't an option. GUROBI has some benchmarks on their site that are illuminating.
- mrcode007 7y agoWhat are the constraint matrix dimensions and density of the matrix, objective and right hand sides? Can you email me at mb@primaldual.io ?
- shaklee3 7y agoGurobi also got caught cheating in some benchmarks and were pulled from them. It's a shame, because they really are the fastest in most tests.
- derefr 7y ago> I work at a non-profit and not a University, so I can't use them for free. What’s required to qualify for an academic license? Could you split your nonprofit into a business aspect, and then a walled-off research aspect (funded by the business aspect) that by itself fits the definition of academia by which these companies judge? Or, more simply, could your nonprofit partner with a University on R&D, with the University acquiring a license to the solver and then retaining you as a project volunteer (on loan from your nonprofit) to use the solver? Presumably, one difference in both cases is that the output of the solver would need to be published in the form of a scientific paper, as well as being used in your nonprofit’s development.
- leethargo 7y agoSeveral of the solvers require that you have an academic email (or even IP) adress. If you don't but still think you qualify, I guess one would need to contact them and go through some work-around, possibly every year to renew?
- 6thaccount2 7y agoThat sounds like far too much to deal with.
- wolfgke 7y agoMIPCL (http://www.mipcl-cpp.appspot.com/ http://www.mipcl-cpp.appspot.com/) is a very fast and free (as beer, but not open source) solver for (Mixed-)Integer Linear Programs ((M)ILPs). EDIT: In Hans Mittelman's benchmark of MILP solvers (http://plato.asu.edu/bench.html http://plato.asu.edu/bench.html), MIPCL is very performant: http://plato.asu.edu/ftp/milp.html http://plato.asu.edu/ftp/milp.html
- analognoise 7y agoWould this be useful in solving the kinds of constraints found in ECAD layout?
- dbcurtis 7y agoUnlikely. Most interesting problems in ECAD are non-linear.
- 6thaccount2 7y agoCan the problem be formulated in a linear way? When doing optimization you have a function that you are trying to minimize like the cost of dispatching power plants. If there is no exponents or trig functions (and whatever else that could make it non-linear) you can solve the problem while adding constraints. GLPK can also do mixed-integer linear programming where some variables are integers like (0,1). If you need to optimize something that is nonlinear, that requires something else I think, but read the doc.
- graycat 7y agoThere is nearly no end of triple tricky clever ways to take a particular optimization problem, exploit its special structure, and have linear programming still be the main part of the solution.
- 6thaccount2 7y agoYea...if you're an OR/Applied Math guru, there is some magical stuff you can do.
- namibj 7y agoBonus if you can use Subspace-BB (Barzilai-Borwein) on what is left after activating your constraints. That stuff is magical. Also because you can throw it at linear systems that are actually FFT-based time/space variant convolutions or similar things where you never, ever want so much as touch the sparse matrix of that linear system.
- theirixhn 7y agoI had used GLPK a few years ago for solving a constrained MIP problem programmatically and liked it a lot. It has a C interface and uses an easy-to-use MathProg language. When you look at your data and problems from the point of view of linear optimization theory, GLPK becomes a really handy tool.
- sevensor 7y agoGLPK really came through for me once. I was working with some academic code that had been written in Python. The Python was writing AMPL scripts and then invoking a commercial solver on them. I bound to GLPK using CFFI and replaced all of the AMPL with direct calls into the library. The performance improvement was about 4 orders of magnitude.
- arithma 7y agoFor a course at uni (am not a practitioner in this domain in any measurement) we used cvxpy (and there was cvxopt for the matlab inclined). Are those within the ballpark of what you need to do? -- Am adding this response as both: -1 Hey maybe you didn't know about this -2 A question: Is CVXpy even in the same domain as those other tools listed here in the replies
- leethargo 7y agocvxpy is only for linear programming (LP), but does not support mixed-integer programming (MIP), so you can only use it for some problems. Also, I think cvxpy might implement an interior point method, not a simplex method, so you don't get a "vertex solution", which often has some nice sparsity attributes.
- AareyBaba 7y agoI never understood why it is called linear 'programming'. Why programming instead of optimization ?
- Arnavion 7y agoGoogling "linear programming etymology" returns https://mathoverflow.net/questions/145077/why-are-optimization-problems-often-called-programs https://mathoverflow.net/questions/145077/why-are-optimizati...
- joey_bob 7y agoProgramming in a general computer science context has been attributed to a shortening of dynamic programming, which as a computer science methodology is derived from the idea behind the optimization method of the same name, which is an advancement in the field of mathematical programming, starting from linear programming, which is described in that link.