Title: Quaternary hyperplane branching with internally generated cutting planes for solving integer programmes

Authors: Todd Easton; Jin Lee

Addresses: Industrial and Manufacturing Systems Engineering, Kansas State University, Manhattan KS, USA ' Georgia Institute of Technology, Atlanta, GA, USA

Abstract: Branch and bound (BB) is typically used to solve an integer programme, max c^Tx subject to Ax ≤ b, x ∈ ℤⁿ₊. This paper introduces amodified version of BB called the quaternary hyperplane branching algorithm (QHBA). QHBA employs a quaternary branching scheme, utilises hyperplane branching constraints and generates internal cutting planes to increase the efficiency of BB. This paper shows that QHBA provides stronger theoretical advancements, quadratically more integer extreme points and the elimination of more continuous relaxation space, than traditional BB. Furthermore, a short computational study shows that QHBA decreases the solution time by 25% when compared to CPLEX.

Keywords: integer programming; branch and bound; hyperplane branching; general disjunctions; polyhedral branching structures; cutting planes.

DOI: 10.1504/IJOR.2012.047095

International Journal of Operational Research, 2012 Vol.14 No.3, pp.366 - 385

Published online: 11 Jan 2015 *

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