3
1

This is a simple question to be asked to the Operations Research commumity. I would like to see responses for, in your opinion, the top algorithms that are used in Operations Research.

Please allow only ONE algorithm per answer so that no repeats an included and no lists in answers. Let OR-Exchange users vote up the favorite ones that are already answered.

I'm interested to see what the OR community answers. Also this list could be useful for folks outside of the OR community to understand OR methodologies and best practices.

asked 14 Oct '10, 18:03

larrydag%201's gravatar image

larrydag 1 ♦
3.2k51326
accept rate: 9%


12next »

Dijkstra's shortest path algorithm, which is probably implemented inside a lot of GPS systems

link

answered 14 Oct '10, 22:42

Tallys%20Yunes's gravatar image

Tallys Yunes ♦
2.1k518
accept rate: 11%

I also use the Floyd-Warshall algorithm for finding shortest paths when doing arc routing...

(16 Oct '10, 07:33) DC Woods ♦

I am a bit unsure if you mean mostly used algorithm, since "top" is not clear. I bet mostly solved problem must be LP, since it's often subroutines in other algorithms such as MIP's. Since warmstart is important in these cases, then my bet is the Simplex Algorithm.

link

answered 14 Oct '10, 19:15

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
accept rate: 14%

Simplex is going to be a favorite for sure.

(14 Oct '10, 19:24) larrydag 1 ♦

Yes, I almost did not suggest it, because it was a bit too obvious :-) But besides it's importance, I love the nice history about it's origin and all the old stories about G.B.D.

(14 Oct '10, 19:39) Bo Jensen ♦

The max-flow/min-cut algorithm by Ford and Fulkerson (with its many variations as well).

link

answered 14 Oct '10, 22:40

Tallys%20Yunes's gravatar image

Tallys Yunes ♦
2.1k518
accept rate: 11%

Personally, I value the out-of-kilter algorithm (http://t.co/n5F3Hh9) for min cost flow (and complex assignment problems) over Ford/Fulkerson.

(15 Oct '10, 07:34) fbahr ♦

Benders decomposition (in various forms) seems to be used pretty heavily these days.

link

answered 15 Oct '10, 21:32

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

And its dual, Dantzig-Wolfe decomposition, which is the basis for many column generation algorithms.

(16 Oct '10, 00:36) Matthew Salt... ♦

Bender's is also the foundation for many of the Stochastic Programming algorithms.

(20 Jan '11, 06:45) Berk Ustun

Since Bo beat me to simplex (which we should construe to mean all variants thereof), I'll toss in branch-and-cut.

link

answered 14 Oct '10, 22:29

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

The tabu search! Very easy to implement! And relatively fast answers on difficult MIPS!(a bit general...)

link

answered 15 Oct '10, 05:52

Buxley's gravatar image

Buxley
5641414
accept rate: 9%

You beat me to my favorite one!

(15 Oct '10, 21:10) DC Woods ♦

Lagrangian relaxation and subgradient optimization.

link

answered 16 Oct '10, 00:37

Matthew%20Saltzman's gravatar image

Matthew Salt... ♦
4.7k310
accept rate: 17%

Are there any good introductory resources for this?

(18 Oct '10, 01:34) Berk Ustun

Chapter 10 of Wolsey's "Integer Programming" (Wiley, 1998) is a quick overview.

(18 Oct '10, 16:52) Matthew Salt... ♦

Newton's method is the core of many algorithms in nonlinear programming, as well as of interior-point algorithms for linear programming.

link

answered 16 Oct '10, 17:08

Matthew%20Saltzman's gravatar image

Matthew Salt... ♦
4.7k310
accept rate: 17%

We cannot forget about heuristics, especially the Lin-Kernighan heuristic for TSP which (with many variations) is one of the main primal heuristics used to solve gigantic TSP instances.

link

answered 14 Oct '10, 22:36

Tallys%20Yunes's gravatar image

Tallys Yunes ♦
2.1k518
accept rate: 11%

Genetic Algorithms. A very powerful and flexible method for solving all sorts of problems, especially when extended to Genetic Programming.

A biological implementation of these could be considered responsible for all life on Earth, although this highlights that they are heuristic methods and can give non-optimal solutions. ;-)

link

answered 15 Oct '10, 21:13

DC%20Woods's gravatar image

DC Woods ♦
4.1k22546
accept rate: 5%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×190
×29

Asked: 14 Oct '10, 18:03

Seen: 9,897 times

Last updated: 17 Jan '11, 23:11

OR-Exchange! Your site for questions, answers, and announcements about operations research.