Skip to main content
SpringerLink
Log in

Using branch-and-bound algorithms to obtain suboptimal solutions

  • Papers
  • Series A: Theory
  • Published:
Zeitschrift für Operations-Research Aims and scope Submit manuscript

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. (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. (2)

    Cut off the computation as soon as T0 partial problems are decomposed, where T0 is a prespecified positive integer.

  3. (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. (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. (2)

    Beende die Rechnung, sobald T0 Teilprobleme bearbeitet worden sind, wobei T0 vorgegeben ist (Beschränkung der Rechenzeit).

  3. (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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Agin, N.: Optimum seeking with branch and bound. Management Science13, 1966, B176-B185.

    Article  Google Scholar 

  • 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.

    Article  MathSciNet  MATH  Google Scholar 

  • Geoffrion, A., andR. Morsten: Integer programming: A framework and state-of-the-art survey. Management Science18, 1972, 465–491.

    Article  MathSciNet  MATH  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  MathSciNet  MATH  Google Scholar 

  • —: Computational efficiency of approximate branch-and-bound algorithms. Mathematics of Operations Research1, 1976b, 287–298.

    Article  MATH  Google Scholar 

  • —: The power of dominance relations in branch-and-bound algorithms. J. ACM24, 1977a, 264–279.

    Article  MathSciNet  MATH  Google Scholar 

  • —: On the computational efficiency of branch-and-bound algorithms. J. Operations Research Society of Japan20, 1977b, 16–35.

    MathSciNet  MATH  Google Scholar 

  • —: 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.

    Google Scholar 

  • 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.

    Article  MathSciNet  MATH  Google Scholar 

  • —: Exact, approximate and guaranteed accurarcy algorithms for the flow-step problem n/2/F/¯F. J. ACM22, 1975, 106–114.

    Article  MATH  Google Scholar 

  • Lawler, E.L., andD.E. Wood: Branch-and-bound method: A survey. Operations Research14, 1966, 699–719.

    Article  MathSciNet  MATH  Google Scholar 

  • Mitten, L.G.: Branch-and-bound method: General formulation and properties. Operations Research18, 1970, 24–34.

    Article  MathSciNet  MATH  Google Scholar 

  • 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.

Download references

Author information

Authors and Affiliations

  1. Dept. of Informationrand Computer Sciences, Toyohashi University of Technology, 440, Tempaku-cho Toyohashi, Japan

    T. Ibaraki

  2. Dept of Applied Mathematics and Physics, Faculty of Engineering, Kyoto University, 606, Kyoto, Japan

    S. Muro & T. Hasegawa

  3. Tokyo System Section, Teijin Ltd., Uchisaiwai-cho, Chiyoda-ku, 100, Tokyo, Japan

    T. Murakami

Authors
  1. T. Ibaraki
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. Muro
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. T. Murakami
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. T. Hasegawa
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01916914

Keywords

Search

Navigation