16
8

Stealing from Math Overflow and Theoretical Computer Science part of Stackoverflow, let's try this question on the operations research crowd:

We all have favorite papers in our own respective areas of operations research. Every once in a while, one finds a paper so astounding (e.g., important, compelling, deceptively simple, etc.) that one wants to share it with everyone. So list these papers here! They don't have to be from the OR literature -- anything that you think might appeal to the community is a fine answer.

You can give as many answers as you want; please put one paper per answer!

asked 12 Sep '10, 13:39

Michael%20Trick's gravatar image

Michael Trick ♦♦
4.1k41533
accept rate: 20%

awesome question. for a novice like me, this is the wealth of information I am looking for.

(14 Sep '10, 16:15) Venky

123next »

10

Retrospective on Optimization. Lorenz T. Biegler and Ignacio E. Grossmann. 2004 http://www.courant.nyu.edu/ComplexSystems/literature/Biegler_Grossman.pdf

A survey paper on the state-of-the-art (in 2004) in optimization algorithms. There have been a few advances since, but the basic approaches are still the same. This paper offers an accessible entry point to the field of nonlinear applied optimization. I'm not sure how well known Biegler and Grossmann are in the OR world, but in the field of continuous and discrete optimization respectively, they are two of the biggest names.

On the global convergence of a filter-SQP algorithm. R. Fletcher, S. Leyffer, and Ph. L. Toint. SIAM J. Optimization, 13(1):44–59, 2002.

This paper introduced the idea of the "filter" line search, which sparked a great deal of research interest. Very roughly, the filter method is a line search that tries to reduce constraint violation while descending; it has been incorporated into the solver IPOPT to great advantage.

link

answered 12 Sep '10, 17:28

Gilead's gravatar image

Gilead ♦
2.3k513
accept rate: 15%

edited 12 Sep '10, 17:37

Because I believe that every OR person should know something about Constraint Programming, here's a good place to start:

"Program Does Not Equal Program: Constraint Programming and Its Relationship to Mathematical Programming", by Irvin Lustig and Jean-François Puget, Interfaces 31(6):29-53, 2001.

link

answered 18 Sep '10, 14:26

Tallys%20Yunes's gravatar image

Tallys Yunes ♦
2.1k518
accept rate: 11%

Good choice. IIRC, it does not serve as a primer on CP, but it does a pretty good job of differentiating CP from MP and explaining to some degree where they complement each other. I agree with you that every OR person (or at least everyone doing optimization) should know at least a little about CP.

(18 Sep '10, 15:36) Paul Rubin ♦♦

I'm a bit embarrassed to be cited along such giants as Dantzig. But I'm happy about it, and thank you!

(27 Oct '13, 13:55) jfpuget

I think you could do a long list which would be biased by people's working areas, but judge by importance then :

Dantzig, G. B "Computational Algorithm of the Revised Simplex Method"
RAND Report RM-1266 The Rand Corporation, Santa Monica, California, 1953.

Must be the most important paper ever..

What a genius.

link

answered 12 Sep '10, 14:49

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
accept rate: 14%

Barnhart, C.; Johnson, E. L.; Nemhauser, G. L.; Savelsbergh, M. W. P. & Vance, P. H. "Branch-and-Price: Column Generation for Solving Huge Integer Programs". Operations Research, 1998, 46, 316-329.

This is the best starting point I've found for learning about branch-and-price.

link

answered 12 Sep '10, 15:55

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.5k412
accept rate: 19%

"Top 10 Algorithms in Data Mining", by Wu, Kumar, Quinlan, Ghosh, Yang, Motoda, McLachlan, Ng, Liu, Yu, zhou, Steinbach, Hand, Steinberg, Knowledge and Information Systems, 14(2008), 1: 1-37.

From the paper (and courtesy of Getting Things Done):

Here are the winners:

  1. C4.5
  2. The k-Means algorithm
  3. Support Vector Machines
  4. The Apriori algorithm
  5. Expectation-Maximization
  6. PageRank
  7. AdaBoost
  8. k-Nearest Neighbor Classification
  9. Naive Bayes
  10. CART (Classification and Regression Trees)
link

answered 15 Sep '10, 13:26

larrydag%201's gravatar image

larrydag 1 ♦
3.2k51326
accept rate: 9%

link

answered 12 Sep '10, 15:04

adamo's gravatar image

adamo
638513
accept rate: 0%

And second place :

N. Karmarkar "A new Polynomial Time Alogorithm for Linear Programming" Combinatorica 4, 375-395, 1984

Though some work on MIP's is also important.

link

answered 12 Sep '10, 14:54

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
accept rate: 14%

1

And the "companion piece" by Gill et al., "On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method, Math. Prog. 1986, which pointed the way to making general-purpose interior-point methods practical.

(15 Oct '10, 14:03) Matthew Salt... ♦

For those who do applied OR (Transportation, Supply Chain, Logistics,...) I think Marshall Fisher’s “An applications oriented guide to Lagrangian relaxation” is a must [here is my review of that paper, not the best review but I keep going back to it so I thought it might be useful to others as well)

I also like the articles in the "50 years of integer programming" book. I found all those articles very enjoyable as well.

link

answered 12 Sep '10, 15:20

Mark's gravatar image

Mark ♦
3.6k22350
accept rate: 9%

1

+1 for Fisher, to which I'll add two more below (separate comments since apparently you can't force a line-break in a comment).

(12 Sep '10, 15:53) Paul Rubin ♦♦
1

Fisher, M. L. The Lagrangian Relaxation Method for Solving Integer Programming Problems Management Science, 1981, 27, 1-18

(12 Sep '10, 15:53) Paul Rubin ♦♦
1

Geoffrion, A. M. Lagrangean Relaxation for Integer Programming Mathematical Programming Study, 1974, 2, 82-114

(12 Sep '10, 15:53) Paul Rubin ♦♦
1

Everyone can get something from this paper. LR is a central topic, and the author makes it very easy to follow every step. It is a great example of exposition, even for those who may find the content familiar. Plus, there is a more detailed Operations Research version of the same paper.

(I missed that this paper was already listed, so I moved my earlier post into this comment).

(08 Nov '13, 08:52) Leo

Benders, J. F. Partitioning Procedures for Solving Mixed-Variables Programming Problems Numerische Mathematik, 1962, 4, 238-252

-- where Benders decomposition began.

link

answered 12 Sep '10, 15:49

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.5k412
accept rate: 19%

"Cutting planes in integer and mixed integer programming", by Marchand, Mantel, Weismantel and Wolsey, Discrete Applied Mathematics, 123 (2002) 397-446.

A very nice survey of techniques.

link

answered 13 Sep '10, 11:06

Serge%20Kruk's gravatar image

Serge Kruk
311
accept rate: 0%

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:

×8

Asked: 12 Sep '10, 13:39

Seen: 11,312 times

Last updated: 08 Nov '13, 08:52

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