There aren't many examples of reusable functionality shared as a result of research or commercial software development.
Has anyone come across any?
Here is one I just learned of:
Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this communityThere aren't many examples of reusable functionality shared as a result of research or commercial software development.
Has anyone come across any?
Here is one I just learned of:
I try to publish all my O.R. code on my GitHub page. There are both exact and heuristic algorithms.
I am learning about better coding practices every day, so there is no guarantee that code I published 1-4 years ago is of acceptable quality (for my standards of today and even less for my future standards), but perhaps it is better than nothing!
Frameworks
as: this is my general-purpose C++ library with a few goodies for operational research.
For example, a class to parse TSPLIB and derived instances (such as for the orienteering problem);
one to solve TSP problems calling either Concorde or a simple MTZ model;
a simple implementation of the Adaptive large Neighbourhood Search (ALNS) metaheuristic;
utilities to work with and plot graphs, which can be used e.g. to visualise routes in routing problems;
tools for solving the maximum weighted independent set and the max-clique problems, using respectively the exactcolors
and the pmc
libraries, which are also available online here and here.
adaptive-large-neighbourhood-search: as the name suggests, it is a C++ framework to implement ALNS heuristics. There is also a version of ALNS hybridised with Tabu Search to solve flat-landscape problems.
biased-random-key-ga: a C++ implementation of the BRKGA framework, with an example application to the TSP. I also have a Java implementation of the same framework; in the beginning I implemented it to do some experimentation, but in the end I think it is modular enough that it can be used as a framework.
simple-ga-cpp: a toy, but working, C++ implementation of a Genetic Algorithm framework.
Solvers
covid-optimisation: a solver for a model used to maximise swab testing capacity during a viral epidemics. It contains a model implemented with Gurobi's C++ interface. More details in the paper.
A solver for the PTSPC, aka the Probabilistic Travelling Salesman Problem with Crowdsourcing. A part from the full-enumeration solver (exact but super-slow), there is the implementation of a machine-learning-guided heuristic search. Full details here.
crop-growth-scheduling realistic instances for this formulation of a problem arising in Vertical Farming.
tsp_bc: is a work-in-progress branch & cut solver for the TSP. It's not going to be state-of-the-art; just a quick experiment to give a more data-driven answer to this question.
selective-graph-colouring: mainly a branch & price solver for the Selective Graph Colouring Problem (SGCP). You can have a look at the corresponding paper for more information.
sgcp-via-cliques: another SGCP solver which uses a transformation into a max-clique problem; here is the corresponding paper.
orienteering-alns: an ALNS heuristic solver for the Orienteering Problem, presented in this paper.
maritime-vrp: a branch-and-price solver for a maritime vehicle routing problem for container shipping feeder networks. This is the corresponding paper.
fast-bwkp: a C implementation of a collection of exact and heuristic solvers for the black-and-white knapsack problem.
tsppddl: a C++ branch & cut solver for the TSP with Pickup, Delivery, and Draught Limits, a problem arising in the shipping industry and detailed in this paper.
train-energy-genetic-algorithm: is an attempted C implementation of a genetic algorithm to come up with driving profiles for electric and diesel trains, which would minimise energy consumption. I abandoned it half-way through.
Tutorials
This may be a related question: Why is the programming code of many algorithms not public in the OR community?
A recent example I've liked is this large-scale location modeling paper by Cordeau, Furini and Ljubic, 2019. Here's their code.
For biased random-key genetic algorithms (BRKGA) there is a paper of Toso & Resende and accompanying software. In a BRKGA the solution is represented as vector $v\in\mathbb{R}^n$ of real "keys" and all you have to do is to provide a "decoder" that maps $v$ to a solution and computes its fitness.
A bit dated, but still useful is the chapter on Metaheuristic Class Libraries in the Handbook of Metaheuristics.
Hastie, Tibshirani and Tibshirani did a comparison of Best Subset Selection (the MIP-formulation introduced by Bertsimas, King and Mazumder), Forward Stepwise Selection and the Lasso. For their calculations they created an R-package which they shared here.
One group at LANL published several collections of model formulations around infrastructure optimization (power grid, gas pipelines, etc.): https://lanl-ansi.github.io/software/
The formulations are implemented with JuMP and highly configurable. So it's a good setup for comparing different formulations on the same problem type and input data.
The Python package PyPSA does power system analysis, including optimal power flow (OPF) and a bunch of other optimization routines (built on Pyomo). It's a bit like MATPOWER for Python but (I believe) has more functionality. I haven't played around with it much yet, but I mean to—it seems rather awesome.
The new release of Octeract Engine (full disclosure: I own that company) comes with the Octeract Reformulator API, which allows users to code, share, and reuse reformulations in the form of simple Python scripts.
We are still setting up the web infrastructure around it so it's still a bit hush-hush, but we will have a user hub for people to share reformulations, pretty much like people can download MATLAB toolboxes.
We developed that language specifically to write parallel optimisation solvers, so the syntax is extremely powerful. Octeract Engine is basically a tech demo of the Octeract Reformulation Language (the Reformulator being the compiler).
The philosophy is that the mathematical logic is abstracted, so people define the logic and the compiler takes care of applying it to the problem at hand.
For instance, this is the Octeract Reformulator script to linearise a Binary Bilinear Term:
trigger = Match('C(n)*V(y1)*V(y2)')
filters = (IsBinary('y1') & IsBinary('y2'))
action = Track('V(y1)*V(y2)',AddBinaryVariable('w_yy') \
+AddConstraint('con1','y1+y2-w_yy-1<=0') \
+AddConstraint('con2','w_yy-y1<=0') \
+AddConstraint('con3','w_yy-y2<=0'))
mod = action + SubWith('n*w_yy')
rule = (trigger & filters).then(mod)
m.apply_mod(rule)
We first define a symbolic Match
, which is our trigger. We can then apply all sorts of filters, in this case IsBinary
for both variables. We then define actions on how to modify the problem when these conditions are met, in this case to add a new auxiliary variable and three constraints. We can also define Track
, which lets the compiler know to only do this for the first instance of each Match, i.e., if $xy$ appears 100 times in the problem, with Track
the compiler will generate a unique auxiliary variable the first time it sees $xy$, and re-use that variable for all other occurrences. It will also only add the set of constraints once per unique auxiliary variable.
Once we have defined that info, we can build problem modification rules using simple operators, e.g. rule = (trigger & filters).then(mod)
.
All of this information is fully reusable and can be mixed & matched, e.g., the same trigger can be used with other filters and so on.
There are two things that are really interesting here: