Some integer programs arising in the design of main frame computers |
| |
Authors: | Carlos Edwards Ferreira Martin Grötschel Alexander Martin Robert Weismantel Stefan Kiefl Ludwig Krispenz |
| |
Institution: | (1) Konrad-Zuse-Zentrum für Informationstechnik Berlin, Heilbronnerstraße 10, 10711 Berlin, Germany;(2) Siemens Nixdorf, Otto-Hahn-Ring 6, 81739 München, Germany |
| |
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 alsoNP-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.On leave from University of São Paulo, Brazil. |
| |
Keywords: | clustering problem design of main frame computers graph partitioning problem hypergraph partitioning problem integer programming mathematical modelling multiple knapsack problem |
本文献已被 SpringerLink 等数据库收录! |