BRANCHING FROM THE LARGEST UPPER BOUND: FOLKLORE AND FACTS

B. L. Fox, J. K. Lenstra, A. H. G. Rinnooy Kan and L. E. Schrage

No 272158, Econometric Institute Archives from Erasmus University Rotterdam

Abstract: Branch-and-bound algorithms are widely used to solve combinatorial maximization problems. At each step of such an algorithm a search strategy selects an active subset of feasible solutions for examination. In this paper we discuss the formal properties and the practical value of search strategies based on branching from the largest upper bound (BLUB strategies). We investigate conditions under which BLUB strategies are optimal in the sense that they minimize the number of subsets generated. Counterexamples show that the conditions given in the literature are not strong enough and a correct optimality condition is formulated. Finally, we argue that the practical objections raised against BLUB strategies are not necessarily convincing.

Keywords: Agricultural and Food Policy; Research Methods/Statistical Methods (search for similar items in EconPapers)
Pages: 12
Date: 1977
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://ageconsearch.umn.edu/record/272158/files/erasmus095.pdf (application/pdf)
https://ageconsearch.umn.edu/record/272158/files/erasmus095.pdf?subformat=pdfa (application/pdf)

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:ags:eureia:272158

DOI: 10.22004/ag.econ.272158

Access Statistics for this paper

More papers in Econometric Institute Archives from Erasmus University Rotterdam Contact information at EDIRC.
Bibliographic data for series maintained by AgEcon Search ().