I am looking for collections of large-scale or difficult-to-solve (in the sense of: long-running) linear programs (we have the usual suspects like MIPLIBs and NETLIB). Yes, linear, not integer programs. As I know the (mathematical) optimization world quite well, I expect that there are some "hidden" instances out there from other communities like biology, engineering, and the like. Do you have any pointers to share?


asked 04 Mar '13, 18:22

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
accept rate: 16%


What about the DEP for any stochastic LP?

(04 Mar '13, 21:52) Austin Buchanan

that would be very nice actually, do you know of public "collections"?

(05 Mar '13, 00:15) Marco Luebbecke ♦

COSP maintains a list of stochastic program test sets on their site. Not sure whether deterministic equivalents explicitly exist, or if you'd need to convert them from SMPS format (I could think of better ways to spend my day!).

(05 Mar '13, 09:26) AndyT

The refinery problems at the Data section at Jordi Castros are very decent problems. The tabular data problems at the same page are in many cases extremely nasty.

Something like MIPLIB for LPs is missing in my opinion.


answered 05 Mar '13, 07:03

Erling_MOSEK's gravatar image

accept rate: 5%

+1 on your MIPLIB/LP comment

(05 Mar '13, 07:22) Marco Luebbecke ♦

What about taking some of the larger/harder MIPLIB instances and relaxing? You could experiment at first and see if some indeed correspond to difficult LP relaxations.

(05 Mar '13, 09:28) AndyT

What do you think about the Klee-Minty problem?

Encyclopedia of Operations Research & Management Science. 2001, p431-431. 1/4p. Abstract: A definition of the term "Klee-Minty problem" is presented. It refers to the linear programming problem. It demonstrates that a problem requires the simplex algorithm to generate the extreme point solutions before finding the optimal. It also demonstrates the number of iterations can increase exponentially.

Klee, V. and Minty, G.J., 1972, How good is the simplex algorithm? In: O. Shisha (Ed.) Inequalities III, (Boston:Academic Press), pp. 159–175


answered 05 Mar '13, 16:42

Slavko's gravatar image

accept rate: 0%

I belive that modern simplex codes "recognize" this case and find the "short cut" immediately.

(05 Mar '13, 17:16) Marco Luebbecke ♦

How can I recognize that the path searching for solutions does not grow exponentially?

(05 Mar '13, 17:41) Slavko

All Klee-Minty type examples are tailored to a particular pivoting rule (like Dantzig's original most negative rule). If you choose a different rule, like devex, you choose a different path - and the single alternative in the Klee-Minty examples gives the optimum in a single pivot. Just lucky!

(05 Mar '13, 17:59) Marco Luebbecke ♦

I forgot the rules. ;-)

This is very interesting, especially since such alternatives rules are commonly available in commercial packages, such as CPLEX:

P. M. J. Harris, Pivot selection methods of the Devex LP code, Mathematical Programming,5(1973),pp.1-28

(05 Mar '13, 18:40) Slavko

I have been work on solving LPs for the last 20 years and I think Klee-Minty are totally useless as test problem. They have very little to do with real world problems.

You can very easily create a solver that solves the Klee-Minty problems efficiently but that proves nothing about your solver in general. If you want artificial problems that very hard to solve, then those are easy to create but I doubt that lead to something very interesting.

(06 Mar '13, 02:36) Erling_MOSEK

If it's a such nasty example of, why the work of Klee-Minty has so impressive impact factor?

(06 Mar '13, 14:11) Slavko

@Slavko it is a result of great theoretical importance: variants of it show for (afaik) all known pivoting rules that they are not polynomial.

(06 Mar '13, 14:14) Marco Luebbecke ♦
showing 5 of 7 show 2 more comments
Your answer
toggle preview

Follow this question

By Email:

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



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



Asked: 04 Mar '13, 18:22

Seen: 3,004 times

Last updated: 06 Mar '13, 14:14

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