Some Integer Programs Arising in the Design of Main Frame Computers.
Appeared in: Zeitschrift für Operations Research 38 1 (1993) pp. 77-100.
| SC 92-25 | Carlos E. Ferreira, Martin Grötschel, S. Kiefl, L. Krispenz, Alexander Martin, Robert Weismantel
Some Integer Programs Arising in the Design of Main Frame Computers. Appeared in: Zeitschrift für Operations Research 38 1 (1993) pp. 77-100. | |
Abstract: In this paper we describe and discuss a
problem that arises in the (global) design of a main frame
computer. The task is to assign certain functional units to
a given number of so called multi chip modules or printed
circuit boards taking into account many technical
constraints and minimizing a complex objective function. We
describe the real world problem. A thorough mathematical
modelling of all aspects of this problem results in a rather
complicated integer program that seems to be hopelessly
difficult - at least for the present state of integer
programming technology. We introduce several relaxations of
the general model, which are also 
-hard, but seem to be
more easily accessible. The mathematical relations between
the relaxations and the exact formulation of the problem are
discussed as well.