Partial polyhedral description and generation of discrete optimization problems with known optima

The authors detail a random cut concept for generating instances of discrete optimization problems based on a partial description of the polytope of solutions. They 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 large-scale 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.