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.
GNU Linear Programming Kit
11–20 of 29 posts
Re: GNU Linear Programming Kit
#12Earlier quoted context omitted.
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 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.
Re: GNU Linear Programming Kit
#13Would 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 t…
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.
Re: GNU Linear Programming Kit
#14Earlier quoted context omitted.
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 t…
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.
Yea...if you're an OR/Applied Math guru, there is some magical stuff you can do.
Re: GNU Linear Programming Kit
#15Earlier quoted context omitted.
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 t…
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.
Re: GNU Linear Programming Kit
#16Earlier quoted context omitted.
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.
What are the constraint matrix dimensions and density of the matrix, objective and right hand sides? Can you email me at mb@primaldual.io ?
Re: GNU Linear Programming Kit
#17It'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.
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
Re: GNU Linear Programming Kit
#18Earlier quoted context omitted.
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?
Re: GNU Linear Programming Kit
#19Earlier quoted context omitted.
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.
Re: GNU Linear Programming Kit
#20GLPK 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.