18
$\begingroup$

As far as I understand, all know deterministic pivot rules for simplex algorithms have specific inputs on which the algorithm requires exponential time (or at least not polynomial) to find the optimum. Let us call these instances 'pathological' since usually (i.e. on most inputs) the simplex algorithm terminates quickly. I remember from my mathematical programming course that the standard examples of pathological instances for specific rules were highly structured. My general question is if this is an artifact of the specific examples, or a feature of pathological instances in general?

Results like smoothed analysis and the polynomial time algorithm extending it rely on perturbing the input --- suggesting that the pathological examples are very special. Hence the intuition that the pathological instances are highly-structured does not seem that far fetched.

Does anybody have any specific insights on this? Or some references to existing work? I have been specifically vague about what I mean by 'structured' to try to be as encompassing as possible, but suggestions on how to better pin down 'structured' would also be useful. Any advice or references are greatly appreciated!

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I am not sure if I have understood your question, but the opposite of “structured” seems to be “random.” If a simplex algorithm with a certain pivoting rule is inefficient already for random instances (with high probability, according to some natural distribution), probably people are not interested in constructing a bad example for that particular pivoting rule because that particular pivoting rule is mostly useless. $\endgroup$
    – Tsuyoshi Ito
    Oct 27, 2010 at 1:57
  • $\begingroup$ Are you asking: for a fixed pivoting rule, what is the probability that a random instance will be pathological? i.e. the average-case analysis of the algorithm? $\endgroup$
    – Kaveh
    Oct 27, 2010 at 2:09
  • $\begingroup$ I am not asking for the probability that a random instance is pathological. I am really just asking if pathological instances have a special structure to them. As Tsuyoshi points out, I should really restrict it to 'good' pivot rules, whatever that means. Any suggestions on how to make this more clear? $\endgroup$
    – Artem Kaznatcheev ♦
    Oct 27, 2010 at 2:14
  • 4
    $\begingroup$ I believe a lot of pathological instances are cubes whose sides have been maliciously perturbed, but I looked at this long enough ago that my memory could be completely wrong. $\endgroup$
    – Peter Shor
    Oct 27, 2010 at 3:26

1 Answer 1

Reset to default
17
$\begingroup$

Amenta and Ziegler proved that all currently-known constructions of exponential-time instances for simplex follow a particular structure that they call "deformed products":

Deformed Products and Maximal Shadows of Polytopes by Amenta and Ziegler

However, I don't think there's any reason to believe that all bad instances for simplex have this structure. This is probably just an artifact of the research process:

  1. Klee and Minty found the first exponential-time example.
  2. Other researchers looked and Klee and Minty's techniques and extended them to other pivot rules. They naturally took the path of least resistance and followed the Klee-Minty cube as closely as possible.
  3. Once someone finds one bad example for a pivot rule, there's no incentive for people to look for more. As a result, all the bad examples we know of have a similar structure.
Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I always love sociological answers to math question ;). Thanks for the answer! I will take a closer look at AmentaZiegler1996, do you know of results since '96 that work well on deformed products? I found a paper by Norman Zadeh (from 1980 and 2009) that even in the '80s version [ stanford.edu/group/SOL/reports/OR-80-27.pdf ] mentions overcoming the deformed product construction. $\endgroup$
    – Artem Kaznatcheev ♦
    Oct 27, 2010 at 18:43
  • $\begingroup$ "Deformed product" was clearly an intuitive notion in the LP community decades before Nina and Gunter formalized it. Certainly that's an accurate description of the Klee-Minty cubes! $\endgroup$
    – Jeffε
    Oct 28, 2010 at 5:12
  • 1
    $\begingroup$ See also Matoušek and Szabo's exponential lower bounds for RANDOM EDGE on "abstract cubes", which can be seen as combinatorial cousins of Amenta and Ziegler's deformed products: portal.acm.org/citation.cfm?id=1033164 $\endgroup$
    – Jeffε
    Oct 28, 2010 at 5:18

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.