Octanary polyhedral branch and bound for integer programs

James P. Bailey, Todd Easton and Fabio Vitor

International Journal of Operational Research, 2022, vol. 43, issue 4, 451-478

Abstract: This paper introduces the octanary branching algorithm (OBA), a polyhedral branching technique to solve integer programs. Unlike the traditional branch and bound algorithm, each of OBA's branching nodes generates eight children instead of two. Four of them are created by equality constraints, while the other four use inequalities. This branching strategy allows a dimension reduction of the linear relaxation space of the four equality children, which should enable OBA to find quality integer solutions sooner than the branch and bound algorithm. Computational experiments showed that the branch and bound algorithm required over one billion nodes to identify a solution that is at least as good as the solution found by OBA after only half a million nodes. Consequently, OBA should replace the branch and bound algorithm during the first portion of the branching tree, be used to identify a warm start solution, or be implemented as a diving strategy.

Keywords: branch and bound; hyperplane branching; branching polyhedra; random diving; integer programming. (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=122815 (text/html)
Access to full text is restricted to subscribers.

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:ids:ijores:v:43:y:2022:i:4:p:451-478

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().