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

dc.contributor.authorLee, Jin Hua
dc.description.abstractInteger 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.en_US
dc.description.advisorTodd W. Eastonen_US
dc.description.degreeMaster of Scienceen_US
dc.description.departmentDepartment of Industrial & Manufacturing Systems Engineeringen_US
dc.publisherKansas State Universityen
dc.subjectBranch and Bounden_US
dc.subjectCutting Planesen_US
dc.subject.umiEngineering, Industrial (0546)en_US
dc.titleTheoretically and computationally improving branch and bound through multivariate branching with internal cutting planesen_US


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
345.37 KB
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
1.61 KB
Item-specific license agreed upon to submission