GNU Linear Programming Kit | Hacker News Reader

GNU Linear Programming Kit

en.wikibooks.org

87 pointsdvfjsdhgfv28 comments

It'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.

I 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.

I 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.

> 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.

Several 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?

That sounds like far too much to deal with.

I 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.

The 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.

Gurobi 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.

What are the constraint matrix dimensions and density of the matrix, objective and right hand sides? Can you email me at mb@primaldual.io ?

Give MSFT's Z3 a try too.

Thanks for the tip... I'll check it out.

MIPCL (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), MIPCL is very performant: http://plato.asu.edu/ftp/milp.html

GLPK 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.

I 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.

For 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

cvxpy 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.

I never understood why it is called linear 'programming'. Why programming instead of optimization ?

Googling "linear programming etymology" returns https://mathoverflow.net/questions/145077/why-are-optimizati...

Programming 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.

Would this be useful in solving the kinds of constraints found in ECAD layout?

Can 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.

There 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.

Bonus 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.

Y not touch the sparse matrix of that system?

Because that'd be equivalent to computing the convolution explicitly. The whole approach is based on tricking Overlapp-Add to support compactly supported interpolation kernels between representative convolution kernels. Easiest would be bilinear interpolation between between the surrounding representative kernels, which mostly translated to using the bilinear weights before using the fft convolution, and deferring the summation of the interpolation to be fused with the addition done due to overlap-add.

Yea...if you're an OR/Applied Math guru, there is some magical stuff you can do.

Unlikely. Most interesting problems in ECAD are non-linear.

Reply on news.ycombinator.com