An implicit enumeration algorithm for the computer system configuration/expansion problem

This paper introduces the Computer System Configuration/Expansion Problem (CSCEP), a combinatorial problem of selecting the hardware and software components of a computer system to provide the required capacity at a minimum cost. We present a general integer programming formulation of the problem and a method of solution based on the implicit enumeration procedure of Trotter and Shetty [23].

By exploiting the special structure of the CSCEP, we have developed a very efficient algorithm. Typically a hardware or software device will provide only one or two types of capacity (although it may consume many different types of capacity). This fact is the basis for efficient procedures for augmentation, computing objective function bounds and dynamically bounding variables in the CSCEP algorithm.

The algorithm was implemented with data derived from Oak Ridge Associated University's historical capacity requirements. Problems with 33 variables and 19 constraints were solved in core using a 32 kilobyte region on a PDP 11/34 minicomputer.