16
$\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?

$\endgroup$
  • 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$ – Luke599999 Jul 1 '19 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 Jul 1 '19 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$ – Luke599999 Jul 2 '19 at 12:17
13
$\begingroup$

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

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

$\endgroup$
  • 3
    $\begingroup$ given the diverse nature of solution algorithms, I suggest adding a short hint to each link (metaheuristic, heuristic, approximation, global) $\endgroup$ – Michael Feldmeier Jul 2 '19 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 Jul 11 '19 at 1:53
  • $\begingroup$ Any efficient code for k-coverage problem (coverage problem with a knapsack constraint) ? $\endgroup$ – Evren Guney Jul 22 '19 at 12:39
15
$\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.

$\endgroup$
  • 1
    $\begingroup$ FYI: In an evaluation that two of my students did, LocalSolver performed better at CVRPs than Google's OR-Tools. $\endgroup$ – Simon Jul 1 '19 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 Jul 1 '19 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 Jul 2 '19 at 8:13
11
$\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.

$\endgroup$
4
$\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.

$\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.

$\endgroup$
3
$\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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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