Implementing linear programming on the web
April 20, 2021 6:01 AM Subscribe
Some years ago, we developed an Excel tool that uses the Solver add-in. Now we have to redesign the tool and port it to the web. What are the options in terms of linear programming routines/libraries/modules etc.?
The optimisation (linear programming, LP) problems solved by our tool use the simplex algorithm and fit within the limits of the Excel Solver (typically less than 50 decision variables). It has input forms for data, the user presses the "Optimise" button, the tool does its calculations and it outputs results and charts. The LP model is quite simple. The version made in Excel uses VBA and the integration of the Solver add-in is straigthforward. Now we have to write specifications for the new version, which will be entirely redesigned and developed by a third party as a website (making it a standalone app for tablets/smartphones is not being considered right now). The tool is highly specific, targeted at people with no math/science/computer background at all, and we do not expect a huge traffic (on the magnitude of tens of hits per day, not thousands). Using it will be free (sort of) for users, and it won't be for academic purposes (so it's non-academic and non-commercial).
What we need is a LP library that will replace the Excel Solver to do more or less the same thing: read a linear model, output the optimal solution (or a message if no solution is found) and a sensitivity analysis.
- the library will be installed on the website server and accessible through whatever is used to develop a modern web interface (javascript, PHP etc.).
- it has to be of professional quality, ie it should be sturdy, reliable, and well documented (ie we don't want to hunt down answers in remote corners of the internet on how to do/fix stuff)
- it should be preferably free (as beer) but paying for a one-time license is possible.
The project is in its early stages, so it's mostly an exploratory question for now. There are lots of LP libraries and tools out there, from free to highly expensive ones (we're working with Xpress on other projects so we know how costly those things are), and... it's a little overwhelming, so I'd appreciate some pointers about where to start, at least about what we should pay attention to when choosing such a library.
The optimisation (linear programming, LP) problems solved by our tool use the simplex algorithm and fit within the limits of the Excel Solver (typically less than 50 decision variables). It has input forms for data, the user presses the "Optimise" button, the tool does its calculations and it outputs results and charts. The LP model is quite simple. The version made in Excel uses VBA and the integration of the Solver add-in is straigthforward. Now we have to write specifications for the new version, which will be entirely redesigned and developed by a third party as a website (making it a standalone app for tablets/smartphones is not being considered right now). The tool is highly specific, targeted at people with no math/science/computer background at all, and we do not expect a huge traffic (on the magnitude of tens of hits per day, not thousands). Using it will be free (sort of) for users, and it won't be for academic purposes (so it's non-academic and non-commercial).
What we need is a LP library that will replace the Excel Solver to do more or less the same thing: read a linear model, output the optimal solution (or a message if no solution is found) and a sensitivity analysis.
- the library will be installed on the website server and accessible through whatever is used to develop a modern web interface (javascript, PHP etc.).
- it has to be of professional quality, ie it should be sturdy, reliable, and well documented (ie we don't want to hunt down answers in remote corners of the internet on how to do/fix stuff)
- it should be preferably free (as beer) but paying for a one-time license is possible.
The project is in its early stages, so it's mostly an exploratory question for now. There are lots of LP libraries and tools out there, from free to highly expensive ones (we're working with Xpress on other projects so we know how costly those things are), and... it's a little overwhelming, so I'd appreciate some pointers about where to start, at least about what we should pay attention to when choosing such a library.
Prototype using Python in Jupyter Notebooks with the benefits you can port your implementation to Julia, a language that uses the proven and lightweight/performant Fortran libraries.
Plus also MS Research's calc.ts, re-implementing the Excel execution engine in TypeScript (previously).
posted by k3ninho at 8:32 AM on April 20, 2021 [2 favorites]
Plus also MS Research's calc.ts, re-implementing the Excel execution engine in TypeScript (previously).
posted by k3ninho at 8:32 AM on April 20, 2021 [2 favorites]
Virtually anything you pick for the backend server will have a linear programming library. The LIBSVM and LIBLINEAR pages have a list of implementations in different languages (but, for instance, it doesn't tell you about sklearn for Python, just that the officially distribution has Python bindings which sklearn is (I believe) wrapping).
I would figure out your top choices for building the website and then make sure that whatever library is available for those languages is performant enough.
posted by hoyland at 9:56 AM on April 20, 2021 [1 favorite]
I would figure out your top choices for building the website and then make sure that whatever library is available for those languages is performant enough.
posted by hoyland at 9:56 AM on April 20, 2021 [1 favorite]
Since your LP solving needs are very modest, with very tiny problem sizes, any reasonably mature LP solver should do the job.
The Python ecosystem may be a decent choice: python is an expressive, high level language - suitable for rapid prototyping, has been used for both web development and scientific/numerical computing communities for a couple of decades.
To rapid prototype, one option is PuLP. Problems can be described using a python modelling language (example). PuLP comes bundled with bindings to the open source COIN-OR CBC mixed integer solver, which you can use to solve LPs. PuLP is BSD licensed and the CBC solver uses the eclipse license.
Another Python library that wraps LP/MIP solvers is mip. Uses eclipse license. Similarly to PuLP it has a python based modelling language for describing problems (example) and comes bundled and integrated with the same underlying CBC solver.
To integrate into a web app, if the backend of the app is built using python (e.g. flask web framework or similar) then pulp or mip could be imported as a library. If your models are simple and very quick to solve you could directly construct the problem and call the solver from a http request handler, and block (wait) until the solver spits out the result, then respond back to the frontend/user. If your problems were hard for the solver to solve, and took a minute or more, this design might be a poor user experience, and you might need to put together something much more complicated (worker processing queue of jobs with some way to communicate progress back to the waiting user). I suspect your problems would solve instantly if they have only ~50 decision variables.
If the rest of the web app is built using different tech stack, another option could be to build a tiny python backend web service that exposes a "solve" API that accepts a description of the problem to solve, solves it, then responds with the solution (or infeasible).
One aspect of the design would be deciding if you want this web service to accept problems described in a domain-agnostic LP modelling format (e.g. data describing objective function, decision variables, constraints, i.e. something like MPS format ) or a domain-specific modelling format -- e.g. if your tool solves catfood blending optimisation problems, then a domain specific format would accept input data about catfood blending and the backend service would internally embed the logic of converting the domain specific parameters into your catfood blending model, then solving it. If you go with the former approach then you can potentially reuse the web service to solve LPs for other kinds of problems, but then you need to figure out where else in your system your domain-specific model would live.
posted by are-coral-made at 12:17 PM on April 20, 2021 [2 favorites]
The Python ecosystem may be a decent choice: python is an expressive, high level language - suitable for rapid prototyping, has been used for both web development and scientific/numerical computing communities for a couple of decades.
To rapid prototype, one option is PuLP. Problems can be described using a python modelling language (example). PuLP comes bundled with bindings to the open source COIN-OR CBC mixed integer solver, which you can use to solve LPs. PuLP is BSD licensed and the CBC solver uses the eclipse license.
Another Python library that wraps LP/MIP solvers is mip. Uses eclipse license. Similarly to PuLP it has a python based modelling language for describing problems (example) and comes bundled and integrated with the same underlying CBC solver.
To integrate into a web app, if the backend of the app is built using python (e.g. flask web framework or similar) then pulp or mip could be imported as a library. If your models are simple and very quick to solve you could directly construct the problem and call the solver from a http request handler, and block (wait) until the solver spits out the result, then respond back to the frontend/user. If your problems were hard for the solver to solve, and took a minute or more, this design might be a poor user experience, and you might need to put together something much more complicated (worker processing queue of jobs with some way to communicate progress back to the waiting user). I suspect your problems would solve instantly if they have only ~50 decision variables.
If the rest of the web app is built using different tech stack, another option could be to build a tiny python backend web service that exposes a "solve" API that accepts a description of the problem to solve, solves it, then responds with the solution (or infeasible).
One aspect of the design would be deciding if you want this web service to accept problems described in a domain-agnostic LP modelling format (e.g. data describing objective function, decision variables, constraints, i.e. something like MPS format ) or a domain-specific modelling format -- e.g. if your tool solves catfood blending optimisation problems, then a domain specific format would accept input data about catfood blending and the backend service would internally embed the logic of converting the domain specific parameters into your catfood blending model, then solving it. If you go with the former approach then you can potentially reuse the web service to solve LPs for other kinds of problems, but then you need to figure out where else in your system your domain-specific model would live.
posted by are-coral-made at 12:17 PM on April 20, 2021 [2 favorites]
This thread is closed to new comments.
I'm at a shop with a strong Python culture, so we use FastAPI and Flask (depending on the project) when we need backend, and we can use numpy/scipy/etc. Looks like scipy.optimize.linprog would be one entry-point there. I can't say enough good about python + numpy + scipy (+ astropy sometimes, if you want really esoteric stuff). It's a nice language, and numpy uses native code under the hood so it's actually performant.
I've not used LP professionally, but the sense I have is that it is not particularly fancy or esoteric, so I'd really look at the language, infra, and the people you have available.
posted by Alterscape at 6:44 AM on April 20, 2021 [2 favorites]