Ttdfjt

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?

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

• 
  

  Vehicle Routing Problem

  
  
  
  • Jsprit: many rich problem types. source code - company website. (Desktop-based open source application built around it ODL Studio).
  
  
  • OptaPlanner: explanation + video's - source code (capacitated, time windows, multiple depots)
  
  

  • LocalSolver: explanation + source code (same with time windows)

  
  

  • OR-tools: explanation + source code

  
  
  • COIN-OR tools: TODO
  
  
  • OscaR: TODO
  
  


• 
  Nurse Rostering problem
  
  
  • OptaPlanner: explanation + video's - source code
    
  
  


• 
  Conference Scheduling
  
  
  • OptaPlanner: explanation + video's - source code
    
  
  


• 
  Course Scheduling
  
  
  • OptaPlanner: source code
    
  
  


• 
  Exam Scheduling
  
  
  • OptaPlanner: source code
    
  
  


• 
  Job Shop scheduling
  
  
  • OptaPlanner: source code of variant
    
  
  
  • LocalSolver: explanation + source code
    
  
  


• 
  Knapsack
  
  
  • LocalSolver: explanation + source code
    
  
  
  • OR-Tools: explanation + source code
    
  
  


• 
  Assembly Line Balancing Problem
  
  
  • SALOME Branch & Bound Algorithm:explanation + source code
  
  
  • Branch & Bound & Remember Algorithm: explanation + source code
    
  
  


• 
  P-median site location
  
  
  • Territorium: source code, UI. Does capacitated clustering for both min and max quantity range using heuristics.
  
  

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

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.

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.

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.

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.