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 Luebbecke ♦
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