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

J. Glover (), V. Quan () and S. Zolfaghari ()
Additional contact information
J. Glover: Ryerson University
V. Quan: University of Toronto at Scarborough
S. Zolfaghari: Ryerson University

Computational Management Science, 2021, vol. 18, issue 2, No 3, 177-193

Abstract: 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.

Keywords: Branch and Bound; Integer programming; Implicit enumeration; Balas method (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10287-021-00389-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:comgts:v:18:y:2021:i:2:d:10.1007_s10287-021-00389-6

Ordering information: This journal article can be ordered from
http://www.springer. ... ch/journal/10287/PS2

DOI: 10.1007/s10287-021-00389-6

Access Statistics for this article

Computational Management Science is currently edited by Ruediger Schultz

More articles in Computational Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().