25

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?

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
PSLP
  • 2,401
  • 9
  • 33
  • 1
    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. – PSLP Jul 01 '19 at 08:15
  • 1
    including heuristic, metaheuristic, and approximation approaches? or just implementations that are guaranteed to solve the problem globally? – Michael Feldmeier Jul 01 '19 at 15:21
  • 1
    @MichaelFeldmeier I was originally mostly interested in optimal solutions, but i think state of the art can certainly include approximation and (meta-)heuristic approches. – PSLP Jul 02 '19 at 12:17

7 Answers7

27

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.

steven kelk
  • 25
  • 3
Geoffrey De Smet
  • 4,851
  • 10
  • 34
  • 4
    given the diverse nature of solution algorithms, I suggest adding a short hint to each link (metaheuristic, heuristic, approximation, global) – Michael Feldmeier Jul 02 '19 at 13:43
  • 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... – Open Door Logistics Jul 11 '19 at 01:53
  • Any efficient code for k-coverage problem (coverage problem with a knapsack constraint) ? – Evren Guney Jul 22 '19 at 12:39
  • You can find a great collection of fundamental problems on the github site of Florian Fontan (@fontanf): https://github.com/fontanf – ktnr Mar 23 '22 at 16:18
17

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.

mrBen
  • 521
  • 4
  • 11
  • 1
    FYI: In an evaluation that two of my students did, LocalSolver performed better at CVRPs than Google's OR-Tools. – Simon Jul 01 '19 at 11:46
  • @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. – Geoffrey De Smet Jul 01 '19 at 21:13
  • @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. – mrBen Jul 02 '19 at 08:13
12

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.

Sune
  • 6,457
  • 2
  • 17
  • 31
5

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.

Ruslan Sadykov
  • 1,504
  • 8
  • 8
5

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).

Janis Neufeld
  • 51
  • 2
3

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.

kur ag
  • 815
  • 5
  • 14
2

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.

steven kelk
  • 25
  • 3