Theoretically and computationally improving branch and bound through multivariate branching with internal cutting planes

Abstract

Integer Programs (IP) are a class of discrete optimization problems that are utilized commercially to improve the function of various systems. Implementation is often aimed at reaching optimal financial objectives with constraints on resources and operation. While incredibly beneficial, IPs are NP-complete, with many IP models being unsolvable. Branch and bound (BB) is the primary method employed to solve IPs to optimality. BB is an exhaustive approach to enumerating all potential integer solutions for a given IP. By utilizing a hierarchical tree structure to tabulate progression of enumeration, BB can guarantee an optimal solution in finite time. However, BB can take an exponential number of iterations to solve an IP. Computationally, this can result in a tree structure that exceeds a computer’s memory capacity, or a prohibitively long solution time. This thesis introduces a modified version of BB call the Quaternary Hyperplane Branching Algorithm (QHBA). QHBA employs a quaternary branching scheme, utilizes hyperplane branching constraints, and generates internal cutting planes to increase efficiency. Implementation of these advancements theoretically improves QHBA in comparison to traditional BB. It can also be shown that QHBA guarantees an optimal solution in a finite number of iterations. A short computational study shows that QHBA results in a 26.7% decrease in solution times when compared to CPLEX, a commercially available IP solver.