ISSN:
1432-5217
Keywords:
assignment problem
;
augmenting path method
;
outpricing
;
re-optimization phase
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Description / Table of Contents:
Zusammenfassung Wir beschreiben einen sogenannten “In-Core/Out-of-Core” Ansatz auf der Basis der kürzesten erweiternden Wege Methode für die Lösung gro\er Zuordnungsprobleme, für die die gesamte Kostenmatrix nicht im Zentralspeicher des Rechners gehalten werden kann. Bei diesem Ansatz wird in einer ersten Phase ein Zuordnungsproblem über einem dünnen Teilgraph optimal gelöst. In einer zweiten Phase werden dann die nicht berücksichtigen Kanten mittels der optimalen Duallösung bewertet (“outpricing”) und gegebenenfalls eine Reoptimierung durchgeführt. Durch Anwendung spezieller Strategien wird es möglich, während der gesamten Lösung den im Zentralspeicher abzuspeichernden Teilgraphen dünn zu halten. Weiterhin zeigt sich, da\ dieser Ansatz zu einem neuen Verfahren führt, das der zugrunde liegenden kürzesten erweiternden Wege Methode überlegen ist.
Notes:
Abstract We describe how the shortest augmenting path method can be used as basis for a so called “in-core/out-of-core” approach for solving large assignment problems in which the data cannot be kept in central memory of a computer. Here we start by solving the assignment problem on a sparse subgraph and then we introduce the remaining edges in an outpricing/reoptimization phase. We introduce several strategies which enable to keep the working subgraph sparse throughout the procedure and even lead to an all in-core code which is faster than the basic shortest augmenting path code.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01919285
Permalink
