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.
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.
Similar content being viewed by others
References
Agin, N.: Optimum seeking with branch and bound. Management Science13, 1966, B176-B185.
Forrest, J.J.H., J.P.H. Hirst, andJ.A. Tomlin: Practical solution of large mixed integer programming problems with UMPIRE. Management Science20, 1974, 736–773.
Geoffrion, A., andR. Morsten: Integer programming: A framework and state-of-the-art survey. Management Science18, 1972, 465–491.
Hart, P.E., N.J. Nilsson, andB. Raphael: A formal basis for the heuristic determination of minimal cost paths. IEEE Trans. System Science and CyberneticsSSC-4, 1968, 100–107.
Horowitz, E., andS. Sahni: Fundamentals of Computer Algorithms. Rockville, MD, 1978.
Ibaraki, T.: Theoretical comparison of search strategies in branch-and-bound algorithms. International J. of Computer and Information Sciences5, 1976a, 315–344.
—: Computational efficiency of approximate branch-and-bound algorithms. Mathematics of Operations Research1, 1976b, 287–298.
—: The power of dominance relations in branch-and-bound algorithms. J. ACM24, 1977a, 264–279.
—: On the computational efficiency of branch-and-bound algorithms. J. Operations Research Society of Japan20, 1977b, 16–35.
—: Theoretical and simulation studies on computational performance of branch-and-bound algorithms. In: Survey of Mathematical Programming. Ed. by A. Prékopa. Hungary Academy of Science, Budapest, 1978.
Kohler, W.H.: Exact and approximate algorithms for permuation problems. Ph. D. Thesis, Department of Computer Science, Princeton University, 1972.
Kohler, W.H., andK. Steiglitz: Characterization and theoretical comparison of branch-and-bound algorithms for permutation problems. J. ACM21, 1974, 140–156.
—: Exact, approximate and guaranteed accurarcy algorithms for the flow-step problem n/2/F/¯F. J. ACM22, 1975, 106–114.
Lawler, E.L., andD.E. Wood: Branch-and-bound method: A survey. Operations Research14, 1966, 699–719.
Mitten, L.G.: Branch-and-bound method: General formulation and properties. Operations Research18, 1970, 24–34.
Murakami, T.: Simulation and analysis of the performance of branch-and-bound algorithms. Master Thesis, Dept. of Applied Mahtematics and Physics, Kyoto University, 1980.
Nilsson, N.J.: Principles of Artifical Intelligence. Berlin 1982.
Ohkawa, T.: Simulation study on computational behavior of branch-and-bound algorithms. Master Thesis, Dept. of Applied Mathematics and Physics, Kyoto University, 1976.
Salkin, H.M.: Integer Programming. Reading, MA, 1975.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Ibaraki, T., Muro, S., Murakami, T. et al. Using branch-and-bound algorithms to obtain suboptimal solutions. Zeitschrift für Operations Research 27, 177–202 (1983). https://doi.org/10.1007/BF01916914
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF01916914