For a recent project that involved an optimisation problem, I settled on using the OR-Tools library, an open-source project from Google (https://developers.google.com/optimization).
Of interest to me was its CP-SAT solver which claimed good solution speed based on Constraint Programming (https://en.wikipedia.org/wiki/Constraint_programming)
Key selling points:
- Documentation looked good with plenty of examples – this was critical since I was starting from zero and needed to get up to speed quickly;
- Has a Python interface, which is the only programming language I consider myself a capable developer in;
- Supports a number of solver back-ends; although I did not get a chance to try this out; and
- If Google uses it, it must be good... right?
As someone who has more experience with Stats/Machine Learning models, Constraint Optimisation presented an interesting challenge given the way models need to be defined;
- Variables must be integers, this means multiplying decimal variables to a magnitude that allows the truncation of the decimal component.
- Expression are in the form of linear equations, which creates some limitations. For example you are unable to simply multiply variables within the same expression such as y = a * b, however you can work around this; in this case one has to use a function cp_model.AddProdEquality(, [])
To note however, that the CP-SAT solver although superior, has a different Python API to the previous CP Solver which (on face value) appeared to have more flexibility in how equations could be constructed.
Also, more generally, when referring to the API docs (which are presented in C++) there appears to be certain things that are either not represented in the Python API, or not well documented to understand how it should be used.
I’ll dig into things a bit further in future posts as I’d like pursue some experimentation to understand pros and cons of different approaches. In the meantime check out the examples, they really are quite comprehensive for standard problems.
As a postscript, the project was successfully delivered using OR-Tools , however due to the modeled variables and constraints, solution speed was pretty slow. This was not unexpected and not a reflection of OR-Tools since the model contained thousands of variables … but it would have been nice to find a silver bullet!