Viele praktische Probleme lassen sich als Packungs- oder Partitionierungsprobleme in Graphen oder Hypergraphen formulieren. Dazu zählen beispielsweise Fragestellungen beim Entwurf elektronischer Schaltungen, im Rahmen des Designs von Supercomputern, bei der Bestückung von Leiterplatten mit elektronischen Bauteilen in flexiblen Fertigungssystemen, bei der Fahrzeugeinsatzplanung von Anrufsammeltaxisystemen (etwa beim Berliner ``Telebus'' Fahrdienst für Behinderte) oder bei der Personaleinsatzplanung von Luftverkehrsgesellschaften oder im öffentlichen Pesonennahverkehr. Die mathematische Formulierung dieser Probleme führt häufig zu äußerst komplexen ganzzahligen Optimierungsproblemen, welche für praktische Größenordnungen mit bisherigen Methoden nicht zufriedenstellend gelöst werden können.
Als im Jahre 1990 C. E. Ferreira zu uns als Doktorand kam, haben wir begonnen, ein bei der Firma Siemens-Nixdorf München auftretendes Problem beim Entwurf von Supercomputern, das wir in enger Zusammenarbeit mit Siemens-Mitarbeitern ([3]) als Partitionierungsproblem in einem Graphen beziehungsweise Hypergraphen formuliert haben, zu untersuchen und polyedrische Ans"atze zur L"osung von Teilproblemen dieser Formulierung zu entwickeln. Dabei konnten wir bereits vielversprechende Teilerfolge erzielen ([2], [4], [5], [10]). Diese Ergebnisse zeigen aber auch, daß noch viele Fragestellungen unbeantwortet sind. Nicht ausreichend studiert sind bislang polyedrische Fragestellungen von Partitionierungsproblemen in Hypergraphen. Um die erwähnten Designfragen für praktische Größenordnungen angehen zu können, scheinen uns neue theoretische und algorithmische Erkenntnisse in diesem Bereich unumgänglich. Gemeinsames Ziel dieses Projekts wird es sein, die zugrundeliegenden Polyeder intensiv zu studieren und geeignete Separierungsverfahren zu entwerfen und zu implementieren. Diese Verfahren dienen als Grundlage für die Entwicklung eines effizienten Branch and Cut Algorithmus.
In einem zweiten Teil unseres gemeinsamen Projekts sollen mehrdimensionalen Packungsproblemen und Setpacking- beziehungsweise Setpartioningprobleme grundlegend studiert werden und L"osungsmethoden daf"ur entwickelt werden. Für mehrdimensionale Packungsprobleme wurden bereits Vorarbeiten von brasilianischer Seite geleistet ([8], [9]). Die Vorgehensweisen und Ziele zur Lösung dieser Probleme werden ausführlich in dem brasilianischen Antrag vorgestellt. Wir wollen intensiv Setpacking- und Setpartioningprobleme studieren. Dabei soll zur Lösung der Probleme ein polyedrischer Ansatz gewählt werden, das heißt die zugehörigen Polyeder grundlegend untersucht und die gewonnenen Erkenntnisse algorithmisch umgesetzt werden. Erste Untersuchungen hierzu sind in [1] zu finden.
Die Zusammenarbeit zwischen den involvierten Personen an beiden Institution beruht auf einer langen Tradition und ist in zahlreichen Veröffentlichungen dokumentiert ([3], [4], [5], [6], [7]). Nicht zuletzt deshalb ist f"ur uns die Abteilung für Informatik in IME-USP, São Paulo (an dem Y. Wakabayashi und, seit Februar 1994, C. E. Ferreira beschäftigt sind) der geeignete Partner zur erfolgreichen Lösung dieser Probleme.