Back in 1996, Harvey Greenberg, longtime faculty member at the University of Colorado at Denver, began putting together a collection of myths and counterexamples in mathematical programming. While generally I find mathematical programming to be quite intuitive, there turn out to be lots of things that I think must be true that are not. Consider the following:
- The duality theorem applies to infinite LPs.
- Simulated annealing converges more slowly than steepest descent when there is a unique optimum.
- In linear programming, a degenerate basis implies there is a (weakly) redundant constraint.
- If f has continuous nth-order derivatives, local behavior of f can be approximated by Taylor’s series.
- The problem of finding integer x such that Ax = b, where A is an m by n integer matrix and b a length m integer vector, is NP-complete.
Amazingly none of these are true! Reading through the myths and counterexamples reminds me of how much I “know” is really false.
The Myths and Counterexamples document is hosted by the INFORMS Computing Society as part of its Mathematical Programming Glossary, and Harvey periodically updates the Myths site (with the last update being in February 2010). If you have shown that something that seems obvious is actually false, be sure to let Harvey know about it. And the next time you are doing a proof and are tempted to make a claim because “it is well known that…” or “obviously…”, perhaps you should check out the site first.
Thanks to @fbahr and the folks at Reddit’s SYSOR for reminding me of the value of a project I have followed for about fifteen years so far!