×

zbMATH — the first resource for mathematics

Quaternary hyperplane branching with internally generated cutting planes for solving integer programmes. (English) Zbl 1362.90295
Summary: Branch and bound (BB) is typically used to solve an integer programme, \(\max c^t x\) subject to \(Ax\leq b\), \(x\in\mathbb{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.
MSC:
90C10 Integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Software:
CPLEX
PDF BibTeX XML Cite
Full Text: DOI