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:
$\begingroup$
$\endgroup$
7
-
2$\begingroup$ Are you just asking if there are public repos that contain code generated as part of research projects? $\endgroup$– LarrySnyder610Jun 13, 2019 at 19:12
-
1$\begingroup$ Yes, I agree it would be helpful to clarify. Also, if there are particular areas you're interested in (e.g., power systems), that may help respondents as well. $\endgroup$– E. TuckerJun 13, 2019 at 19:14
-
2$\begingroup$ @MichaelTrick I think [soft-question] was the right tag (eg, math.stackexchange.com/questions/tagged/soft-question) so I rolled back your edit. You or the OP can reverse me if I was wrong. $\endgroup$– LarrySnyder610Jun 13, 2019 at 20:36
-
$\begingroup$ @larrysnyder610 See the discussion at or.meta.stackexchange.com/questions/163/… Cartaino, as SE Director of Community Development, has a certain legitimacy here. or.meta.stackexchange.com/users/11/robert-cartaino $\endgroup$– Michael TrickJun 13, 2019 at 20:47
-
1$\begingroup$ @MichaelTrick aha, got it. So we should remove [soft-question] not because we can’t ask this kind of question but because it’s a meta tag. That makes sense. Sorry, I missed that question on meta. So, shall we remove the tag here (again!)? $\endgroup$– LarrySnyder610Jun 13, 2019 at 20:56
|
Show 2 more comments
7 Answers
$\begingroup$
$\endgroup$
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
exactcolorsand thepmclibraries, 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
- cplex-example: example code I use to teach students the basics of modelling with CPLEX's C++ API.
$\begingroup$
$\endgroup$
1
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.
-
1$\begingroup$ Yes indeed this is a step in the right direction. But I am interested in a framework or suite whereby multiple can be run in the same manner. Perhaps then even deployed as part of a larger solution! $\endgroup$– fhkJun 13, 2019 at 20:57
$\begingroup$
$\endgroup$
1
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.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
answered Jun 14, 2019 at 15:00
$\begingroup$
$\endgroup$
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:
- People can read this code and understand the mathematical logic being applied.
- This code only needs to be written once. It can then be reused to apply this reformulation for any problem, by anyone. The names you see are just user-defined handles for the language, e.g., the variables in the model don't need to actually be named $y_1$ and $y_2$ for that exact code to work. The names are only used internally by the compiler to match each variable to other rules later on.
