17
$\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!

$\endgroup$
  • 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 '10 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 '10 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 '10 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 '10 at 3:26
16
$\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.
$\endgroup$
  • 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 '10 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 '10 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 '10 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.