ISSN:
1436-6304
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Description / Table of Contents:
Zusammenfassung Algorithmen zur Erzeugung von Nebenbedingungen zur Identifizierung von Facetteninduzierten Ungleichungen, die von der Optimallösung der aktuellen LP-Relaxation verletzt werden, werden häufig benutzt, um ganzzahlige Optimierungsprobleme zu lösen. Für kapazitierte Standortprobleme hat Barcelo kürzlich bereits rechnerisch die Güte eines solchen Algorithmusses getestet. Hallefjord und Jörnsten haben gezeigt, wie diese Algorithmen zu besseren Schranken führen können, wenn sie mit Lagrange-Relaxationen anstelle von klassischen LP's benutzt werden. Wir beschreiben einen heuristischen Lagrange-Relaxationsalgorithmus für das kapazitierte Standortproblem, der in jeder Iteration den dualen Raum erweitert, indem zur dualen Lagrange-Funktion eine neue, für das Ausgangsproblem gültige Ungleichungen addiert wird. Diese Ungleichung wird aus der aktuellen Teillösung erzeugt. Beispiele und numerische Ergebnisse sind angefügt.
Notes:
Summary Constraint generation procedures for identifying facet-induced inequalities violated by the optimal solution to the current LP relaxation have been widely used to solve integer programming problems. For capacitated plant location problems, Barcelo has recently tested computationally the performance of one such procedure. Hallefjord and Jörnsten have shown how these procedures can lead to better bounds when used with Lagrangean relaxations instead of the classical LP ones. We describe a Lagrangean relaxation heuristic algorithm for the capacitated location problem that in each iteration expands the dual space by adding to the dual Lagrangean function a new valid inequality for the problem generated from the current partial solution. Examples and computational results are included.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01784983
Permalink
