Title: Octanary polyhedral branch and bound for integer programs

Authors: James P. Bailey; Todd Easton; Fabio Vitor

Addresses: Department of Industrial and Systems Engineering, Texas A&M University, College Station, TX, USA ' Department of Industrial and Manufacturing Systems Engineering, Kansas State University, Manhattan, KS, USA ' Department of Mathematics, University of Nebraska at Omaha, Omaha, NE, USA

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.

DOI: 10.1504/IJOR.2022.122815

International Journal of Operational Research, 2022 Vol.43 No.4, pp.451 - 478

Received: 02 Oct 2018
Accepted: 25 Jun 2019
Published online: 13 May 2022 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article