ISSN:
1432-5217
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Description / Table of Contents:
Zusammenfassung Das Branch-and-Bound-Prinzip kann erfolgreich zur Lösung verschiedener kombinatorischer Optimierungsprobleme eingesetzt werden. In der Regel nimmt der Rechenaufwand jedoch sehr stark mit wachsender Problemgröße zu. Um dieser Schwierigkeit zu begegnen, werden folgende drei suboptimale Methoden oft in der Praxis angewendet: (1) Seien z der Zielfunktionswert der besten bekannten Lösung eines gegebenen Minimierungsproblems undg (P i ) eine untere Schranke für die Zielfunktion des Teilproblems Pi. Dann terminiereP i , fallsg (P i ) ⩾z−∃ (z) ist, wobei∃ (z) eine vorgegebene Fehlerschranke ist. (2) Beende die Rechnung, sobald T0 Teilprobleme bearbeitet worden sind, wobei T0 vorgegeben ist (Beschränkung der Rechenzeit). (3) Berücksichtige stets höchstensM 0 (eine vorgegebene Zahl) aktive Teilprobleme. Die übrigen Teilprobleme weiden ignoriert (Beschränkung des Speicherplatzes). Die Auswirkungen dieser drei Methoden auf die benötigte Rechenzeit und die erhaltenen suboptimalen Lösungen werden theoretisch und an Hand von Simulationen untersucht.
Notes:
Abstract The branch-and-bound principle is successful in solving various combinatorial optimization problems. In general, however, the computation time becomes excessive as the sizes of problems grow. To overcome this difficulty the following three suboptimal methods are often employed in practice. (1) Letz be the value of currently known best solution of a given minimization problem, and letg (P i ) be a lower bound on the objective value of partial problemP i . TerminateP i ifg (P i ) ⩾z−∃ (z), where∃ (z) is an allowance specified in advance. (2) Cut off the computation as soon as T0 partial problems are decomposed, where T0 is a prespecified positive integer. (3) Always take into account at mostM 0 (a given positive integer) number of active partial problems. The overflown partial problems are simply ignored. The effects of these methods on the computation time and the quality of obtained suboptimal solutions are investigated from both theoretical and simulation points of view.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01916914
