Octanary polyhedral branch and bound for integer programs. (13th May 2022)

• Record Type: Journal Article
• Authors: Bailey, James P.; Easton, Todd; Vitor, Fabio
• Is Part Of: International journal of operational research. Volume 43:Number 4(2022)
• Page Start: 451
• Page End: 478
• Publication Date: 2022-05-13
• Subjects: branch and bound -- hyperplane branching -- branching polyhedra -- random diving -- integer programming; Operations research -- Periodicals; 003.05
• Languages: English
• ISSNs: 1745-7645

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.