[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Some new perspectives for solving 0–1 integer programming problems using Balas method

  • Original Paper
  • Published:
Computational Management Science Aims and scope Submit manuscript

Abstract

Egon Balas’s additive algorithm, also known as implicit enumeration, is a technique that uses a branch-and-bound (B&B) approach to finding optimal solutions to 0–1 integer programming problems. Three common search strategies in B&B are depth-first search, breadth-first search and best-first search. The B&B approach generates a list of pending nodes to be evaluated and storage of these nodes becomes a memory issue for larger problems. In this paper, we propose a simple bookkeeping method that tracks the state of the problem using a single array when performing a depth-first search, dramatically reducing memory requirements. The method also provides the ability to calculate, at any point of the search, the theoretical maximum number of remaining nodes to be evaluated. We note in this paper that when using the best-first search strategy, the first candidate solution found is the optimal solution.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

References

  • Balas E (1965) An additive algorithm for solving linear programs with zero-one variables. Opns Res 13:517–546

    Article  Google Scholar 

  • Bradley SP, Hax AC, Magnanti TL (1977) Applied mathematical programming. Addison-Wesley (Section 9.7)

    Google Scholar 

  • Chinneck JW. 2015. Practical optimization: A gentle introduction. Draft. Not published. All chapters available at http://www.sce.carleton.ca/faculty/chinneck/po/. (Chapter 13).

  • Dechter R, Pearl J (1985) Generalized best-first search strategies and the optimality of A∗. J ACM 32:505–536

    Article  Google Scholar 

  • Fagerberg N, Odenbrand D (2016) Binary integer programming in associative data models. Master’s Thesis, Dept Computer Science. Lund University

  • Geoffrion AM (1967) Integer programming by implicit enumeration and balas’ method. SIAM Rev 9(2):178–190

    Article  Google Scholar 

  • Glover F (1965) A multiphase-dual algorithm for the zero-one integer programming problem. Oper Res 13(6):879–919

    Article  Google Scholar 

  • Hillier FS, Liberman GJ (2001) Introduction to operations research, 7th edn. McGraw Hill, New York (Section 12.6)

    Google Scholar 

  • Ibaraki T (1976) Theoretical comparisons of search strategies in branch-and-bound algorithms. Int J Comput Inf Sci 5:315–344

    Article  Google Scholar 

  • Land AH, Doig AG (1960) An automatic method for solving discrete programming problems. Econometrica 28(3):497–520

    Article  Google Scholar 

  • Lawler EL, Wood ED (1966) Branch-and-bound methods: a survey. Oper Res 14:699–719

    Article  Google Scholar 

  • Mannur NR (1993) Implicit enumeration algorithms for solving 0–1 integer programming problems. PhD Thesis. State University of New York at Buffalo.

  • Morrison DR, Jacobson SH, Sauppe JJ, Sewell EC (2016) Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning. Discret Optim 19:79–102

    Article  Google Scholar 

  • Murty KG (1995) Operations research deterministic optimization models. Prentice Hall Section 10:7

    Google Scholar 

  • Nemhauser G, Wolsey L (1988) Integer and combinatorial optimization. Wiley (Section 11.4)

    Book  Google Scholar 

  • Taha HA (1975) Integer programming, applications and computations. Academic Press, New York (Ch3)

  • Tuan NPh (1971) A flexible tree-search method for integer programming problems. Oper Res 19(1):115–119

    Article  Google Scholar 

  • Winston WL (1991) Operations research: applications and algorithms. PWS-Kent Pub Co. Ch9

Download references

Author information

Authors and Affiliations

  1. Department of Mechanical and Industrial Engineering, Ryerson University, 350 Victoria Street, Toronto, ON, M5B 2K3, Canada

    J. Glover

  2. Department of Management, University of Toronto at Scarborough, 1265 Military Trail, Toronto, ON, M1C 1A4, Canada

    V. Quan

  3. Department of Mechanical and Industrial Engineering, Ryerson University, 350 Victoria Street, Toronto, ON, M5B 2K3, Canada

    S. Zolfaghari

Authors
  1. J. Glover
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. V. Quan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. S. Zolfaghari
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to J. Glover.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Glover, J., Quan, V. & Zolfaghari, S. Some new perspectives for solving 0–1 integer programming problems using Balas method. Comput Manag Sci 18, 177–193 (2021). https://doi.org/10.1007/s10287-021-00389-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10287-021-00389-6

Keywords

Search

Navigation