Our great sponsors
-
-
WorkOS
The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.
-
-
OptaPlanner
Java Constraint Solver to solve vehicle routing, employee rostering, task assignment, maintenance scheduling, conference scheduling and other planning problems.
-
-
python-mip
Python-MIP: collection of Python tools for the modeling and solution of Mixed-Integer Linear programs
-
-
InfluxDB
Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.
-
-
I use JuMP as modeling language. For MILP i am usually using Gurobi or SCIP. For ILP problems have have been looking in to the exact solver https://gitlab.com/JoD/exact which seems quiet promising.
For NLP i usually go with either https://worhp.de/ or just IpOpt.
The last time I tried to optimise something I ended up with a column generation formulation: so I was wanting to rapidly iterate between LP solves of the (restricted) master problem & solves of auxiliary problems through hand written problem-specific algorithms taking shadow prices from the master problem dual solution as inputs. Then the auxiliary solution would contribute new variables into the master problem.
I needed shadow prices defined using the master problem dual solution. In my problem instances I would very often run into scenarios where the primal (and hence also dual) master LP problem had a unique objective value but the dual solutions at which that maxima was attained were non-unique. I learned that it only makes sense to talk about shadow prices in some allowable range for each dual decision variable, but LP solvers generally don't give you an API to extract much information about this from the current internal state of the simplex algorithm [0]. I read a bunch of LP solver documentation and the best one I found discussing this kind of stuff was the section in MOSEK's manual about sensitivity analysis[1]. This was for a hobby project, not business, so I didn't try out MOSEK, even though it is looks very modestly priced compared to other commercial packages.
What I did find, however, was that some time during the last few years, scipy.optimize grew an LP solver interface, and even better, Matt Haberland contributed a python implementation of an interior-point LP solver straight into scipy [2][3]. I found that Haberland & co's open source interior point LP solver produced dual solutions that tended to be more stable and more useful for shadow prices in my problems than a bunch of the other open source LP solvers I tried (including the various other LP backends exposed by scipy.optimize.linprog).
[0] a paper I found very helpful in understand what was going on was Jansen, de Jong, Roos, Terlaky (1997) "Sensitivity analysis in linear programming: just be careful!". In 1997 they got 5 commercial LP solvers to perform a sensitivity analysis on an illustrative toy problem, and although the solvers all agreed on the optimal objective value, none of them agreed with each other on the sensitivity analysis.
[1] https://docs.mosek.com/9.2/pythonapi/sensitivity-shared.html
[2] https://github.com/scipy/scipy/pull/7123
[3] https://docs.scipy.org/doc/scipy/reference/generated/scipy.o...
I have been using OSQP [1] quite a bit in a project where I needed to solve many quadratic programs (QPs). When I started the project, OSQP didn't exist yet; I ended up using both cvxopt and MOSEK; both were frustratingly slow.
After I picked up the project again a year later, I stumbled across the then new OSQP. OSQP blew both cvxopt and MOSEK out of the water (up to 10 times faster) in terms of speed and quality of the solutions. Plus the C interface was quite easy to use and super easy (as far as numerics C code goes) to integrate into my larger project.
[1] https://osqp.org/
Optaplanner facinates me, but I have no idea what I could be using it for and the learning curve seems quite heavy
https://www.optaplanner.org/
CPLEX (by IBM). The documentation can be a bit thin sometimes. But its fast. Most benchmarks place it ahead of the google cloud products.
For fun I made this Golomb ruler solver using cplex: https://github.com/strateos/golomb-solver
I've been using CBC via python-mip (https://github.com/coin-or/python-mip). It's great because it's got a super clean interface (milp variables/expressions/constraints), the code is quite accessible, and it's low overhead which makes it good for solving many very small problems.
Community sentiment seems to be beginning to shift toward favouring the HiGHS solver (https://github.com/ERGO-Code/HiGHS) over CBC. Something I'm keeping a close eye on.
nextmv seems to pitch itself as a generic solving ("decision automation") platform or something (unclear). But it seems that the only fleshed out product offering is for vehicle routing, based on the docs. Are there plans to offer, for instance, a solver binary that can be used to solve generic problems?
Also all the github repos under https://github.com/nextmv-io are private, so links from docs are 404.
I've been using CBC via python-mip (https://github.com/coin-or/python-mip). It's great because it's got a super clean interface (milp variables/expressions/constraints), the code is quite accessible, and it's low overhead which makes it good for solving many very small problems.
Community sentiment seems to be beginning to shift toward favouring the HiGHS solver (https://github.com/ERGO-Code/HiGHS) over CBC. Something I'm keeping a close eye on.
nextmv seems to pitch itself as a generic solving ("decision automation") platform or something (unclear). But it seems that the only fleshed out product offering is for vehicle routing, based on the docs. Are there plans to offer, for instance, a solver binary that can be used to solve generic problems?
Also all the github repos under https://github.com/nextmv-io are private, so links from docs are 404.
I actually just finished implementing an extremely simple Integer Linear Program solver in Python as an educational exercise, wrapping scipy's linprog function to solve the linear relaxation. It has an expression syntax so you don't have to specify the matrix and vectors for the standard form, and it does branch-and-cut on the linear relaxation
https://github.com/cwpearson/csips
I use Minizinc in a personal toy project (https://gitlab.com/dustin-space/meal-scheduler), and GECODE or Google's ortools solver at the backend. It's used for meal planning. Unfortunately it's way way slower than I'd hope. I suspect I just have the domain not modeled efficiently. Maybe if I had a few days to put into it, and learn how to properly debug the CSP solver step by step, it might help...
Optimisation solvers are complex and incredibly powerful pieces of software. However, there are lots of different options and choosing which to use can be a daunting task.
There are some open source options ([COIN](https://www.coin-or.org/), [OR-tools](https://developers.google.com/optimization), [Minion](https://constraintmodelling.org/minion/), [CVXPY](https://www.cvxpy.org/)) and other commercial offerings ([gurobi](https://www.gurobi.com/), [Mosek](https://www.mosek.com/)), other people write their own for thiner specifics purposes. Some [benchmarks](http://plato.asu.edu/bench.html.) are maintained by Hans Mittelmannt.
Personally, I have used OR-tools, maintained by a team at Google, for vehicle routing optimisation and found it powerful but poorly documented with an inconsistent API. I've also used R's [optim](https://www.rdocumentation.org/packages/stats/versions/3.6.2...) function and [lpsolve](https://cran.r-project.org/web/packages/lpSolve/index.html) for linear and integer problems.