26
$\begingroup$

For the TSP there famously is the concord solver (http://www.math.uwaterloo.ca/tsp/concorde.html) which is argubly the fastest exact solver for the TSP.

There are many other problems that also show up again and again, for example the capacitated vehicle routing problem (CVRP). CVRP can be solved very efficiently using branch and price, and there are many papers, on the fastest current methodes and how they can incorporate different constraints (e.g. time windows). However, i was unable to find any available implementation.

So I wonder, are there some good implementations of the state of the art for other problems than the TSP? Is there a list of such implementations and if not, can we create one?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I saw the "Why is the programming code of many algorithms not public in the OR community?" and i think, this is not about sharing the code, but rather the executables. $\endgroup$
    – PSLP
    Commented Jul 1, 2019 at 8:15
  • 1
    $\begingroup$ including heuristic, metaheuristic, and approximation approaches? or just implementations that are guaranteed to solve the problem globally? $\endgroup$
    – Michael Feldmeier
    Commented Jul 1, 2019 at 15:21
  • 1
    $\begingroup$ @MichaelFeldmeier I was originally mostly interested in optimal solutions, but i think state of the art can certainly include approximation and (meta-)heuristic approches. $\endgroup$
    – PSLP
    Commented Jul 2, 2019 at 12:17

7 Answers 7

Reset to default
27
$\begingroup$

Let's make an inventory of example code for each common OR problem?

  • Vehicle Routing Problem
    • OptaPlanner: explanation + videos - source code (capacitated, time windows, multiple depots, ...)
    • LocalSolver: explanation + source code (same with time windows)
    • OR-tools: explanation + source code
    • Jsprit: source code - company website (capacitated, time windows, multiple depots, ...) (Related: ODL Studio).
    • vrpy: A python framework for solving the VRP and its variants with column generation.
    • VeRyPy: A python library with implementations of 15 classical heuristics for the capacitated vehicle routing problem.
    • vroom: Vehicle Routing Open-source Optimization Machine
    • HGS-CVRP: Modern implementation of the hybrid genetic search (HGS) algorithm specialized to the capacitated vehicle routing problem (CVRP).
    • VRPSolver: Branch-Cut-and-Price based exact solver for vehicle routing and some related problems
    • vrp: A Vehicle Routing Problem solver
    • COIN-OR tools: TODO
    • OscaR: TODO
  • Nurse Rostering problem
  • Conference Scheduling
  • Course Scheduling
  • Exam Scheduling
  • Job Shop scheduling
  • Knapsack
  • Bin Packing
    • BinPacking2D: Exact solutions for two-dimensional bin packing problems by branch-and-cut
    • bin-packing: C++ implementation of heuristics for solving the bin-packing problem
  • Assembly Line Balancing Problem
  • P-median site location
    • Territorium: source code, UI. Does capacitated clustering for both min and max quantity range using heuristics.
  • K-median Problem
    • kmedian: Lagrangian tools for the k-median problem
  • Resource constrainted shortest path
    • cspy: A collection of algorithms for the (Resource) Constrained Shortest Path problem in Python / C++ / C#
    • vrp-espprc: Elementary Shortest Path Problem with Resource Constraints
  • Assignment Problems
  • Set Covering Problem
  • Hitting Set Problem
    • findminhs: Implementation of the Minimum Hitting Set solver described in the paper "An Efficient Branch-and-Bound Solver for Hitting Set".
  • Stable Set Problem
    • stablesolver: Solvers for the Maximum(-Weight) Independent Set and the Maximum(-Weight) Clique Problems
    • Cliquer: Cliquer - routines for clique searching
    • KaMIS: A framework for computing maximum independent sets (and related problems)
  • Graph Coloring Problem

I've made this post a wiki: please add common OR problems and/or implementations.

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ given the diverse nature of solution algorithms, I suggest adding a short hint to each link (metaheuristic, heuristic, approximation, global) $\endgroup$
    – Michael Feldmeier
    Commented Jul 2, 2019 at 13:43
  • $\begingroup$ Should this list only be restricted to open source / 100% free products? I know the question doesn't explicitly ask for open source, but it seems like the theme/assumption is 'solvers you can access for free'. LocalSolver isn't free (outside of academia) and if we included commercial non-free products than this list will just end up with hundreds of items, with very few of them being available for free... $\endgroup$
    – Open Door Logistics
    Commented Jul 11, 2019 at 1:53
  • $\begingroup$ Any efficient code for k-coverage problem (coverage problem with a knapsack constraint) ? $\endgroup$
    – Evren Guney
    Commented Jul 22, 2019 at 12:39
  • $\begingroup$ You can find a great collection of fundamental problems on the github site of Florian Fontan (@fontanf): github.com/fontanf $\endgroup$
    – ktnr
    Commented Mar 23, 2022 at 16:18
17
$\begingroup$

A good place to start is COIN-OR, which aims to "create for mathematical software what the open literature is for mathematical theory".

You can also take a look at Google's OR-Tools. It contains many algorithms for specific problems (like knapsack or max flow) and also generic LP and CP solvers.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ FYI: In an evaluation that two of my students did, LocalSolver performed better at CVRPs than Google's OR-Tools. $\endgroup$
    – Simon
    Commented Jul 1, 2019 at 11:46
  • $\begingroup$ @Simon Any chance you could have them benchmark OptaPlanner too (with Nearby Selection and Multithreaded Incremental Solving turned on). A big customer stated that it also beat Google OR tools (and 2 other vendors) significantly on their big VRPTW's. YMMV, of course. $\endgroup$
    – Geoffrey De Smet
    Commented Jul 1, 2019 at 21:13
  • $\begingroup$ @Simon, By "implementation" I've understood "with source code available". But you're right, LocalSolver perform well on many kind of problems, in particular VRPs. $\endgroup$
    – mrBen
    Commented Jul 2, 2019 at 8:13
12
$\begingroup$

I would, for everything knapsack-like, always go to David Pisingers homepage. Here you can find very efficient codes for knapsack problems (COMBO), multiple-choice knapsack problems (Mcknap), and quadratick knapsack problems (quadknap) among others.

I don't know if it qualifies as a "common OR problem" but for linear vector optimization (and therefore also linear multi-objective optimization) there is the BENSOLVE solver.

Improve this answer
$\endgroup$
5
$\begingroup$

I am sorry to advertise our own VRP solver, but may be it is what you are looking for:

https://vrpsolver.math.u-bordeaux.fr/

For knapsack, Pisinger's code is the best (mentioned above), however integer knapsack code there has a bug. I only use 0-1 knapsack code, it is reliable.

For bin packing, this nice paper has links to several available solvers: https://doi.org/10.1016/j.ejor.2016.04.030

For (weighted) maximum clique (minimum stable set), Ostergard's code is very good: https://users.aalto.fi/~pat/cliquer.html

Although, it may not be state-of-the-art anymore.

Improve this answer
$\endgroup$
5
$\begingroup$

A nice framework for heuristic optimization is provided by HeuristicLab. Several classical problems, such as Job Shop Scheduling, Knapsack, Bin Packing or TSP are also integrated (https://dev.heuristiclab.com/trac.fcgi/wiki/Features).

Improve this answer
$\endgroup$
3
$\begingroup$

For assembly line balancing problem, test problems, codes for several versions of problem and useful resources can be found at https://assembly-line-balancing.de.

Improve this answer
$\endgroup$
2
$\begingroup$

I just want to mention the solvers that have been produced in recent years in the remit of the PACE (Parameterized Algorithms and Computational Experiments) challenge, see https://pacechallenge.org/.

This competition asks participants to produce fast exact and/or heuristic solvers for various NP-hard graph problems. Thus far the challenges have been on treewidth, (directed) feedback vertex set, vertex cover, steiner tree, cluster editing, treedepth, and hypertreewidth.

These problems are not commonly encountered OR problems in the way that something like VRP is, but they may well occur as subroutines in a larger OR solution framework.

The winning solvers produced each year tend to be extremely good, and a significant advance on what has come before, so they are definitely worth considering if such problems cross your path in OR.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.