A single-branch implicit enumeration algorithm for zero-one programs with geometrical constraints (Q1085782)

This paper presents an algorithm for solving a class of mathematical programming problems that arise in connection with optimizing recovery from air base attacks. The problems are formulated as zero-one programs with geometrical constraints associated with quasirandom arrangements of circular craters imposed on taxiways. It is shown that efficient, computer-based enumerative methods may be employed successfully in the absence of algebraic representations for the constraints. The computational efficiency of the algorithm is characterized empirically using samples of randomly generated test problems. Rapid increase in solution time with growth in problem size is noted. A simple but effective means of decomposition to additive subproblems is described to help avoid long solution time. Finally, directions of current related research are given.