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

摘要

Branch and bound (BB) is typically used to solve an integer programme, max c~Tx subject to Ax ≤ b, x∈ Z_+~n. This paper introduces a modified 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.