Some Integer Programs Arising in the Design of Main Frame Computers.
Please always quote using this URN: urn:nbn:de:0297-zib-957
- 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 $NP$-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.
Download full text files
Additional Services
| Author: | Carlos E. Ferreira, Martin Grötschel, Stefan Kiefl, Ludwig Krispenz, Alexander Martin, Robert Weismantel |
|---|---|
| Document Type: | ZIB-Report |
| Date of first Publication: | 1993/01/13 |
| Series (Serial Number): | ZIB-Report (SC-92-25) |
| ZIB-Reportnumber: | SC-92-25 |
| Published in: | Appeared in: Zeitschrift für Operations Research 38 1 (1993) pp. 77-100. |
