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

Todd Easton and Jin Lee

International Journal of Operational Research, 2012, vol. 14, issue 3, 366-385

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. (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=47095 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijores:v:14:y:2012:i:3:p:366-385

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().