Partial polyhedral description and generation of discrete optimization problems with known optima
✍ Scribed by Martha G. Pilcher; Ronald L. Rardin
- Publisher
- John Wiley and Sons
- Year
- 1992
- Tongue
- English
- Weight
- 942 KB
- Volume
- 39
- Category
- Article
- ISSN
- 0894-069X
No coin nor oath required. For personal study only.
✦ Synopsis
We detail a random cut concept for generating instances of discrete optimization problems based on a partial description of the polytope of solutions. We show how implementations of this approach have the useful properties that an optimal solution and the form of valid equalities required to solve the problem by cutting methods are both known at the completion of generation. The former makes possible largescale testing of heuristics. and the latter facilitates cutting algorithm research. The random cut concept of problem generation is first discussed in general and then details are provided on its implementation for symmetric traveling salesman problems.