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

K-REx Repository

Show simple item record Lee, Jin Hua 2010-11-08T18:25:26Z 2010-11-08T18:25:26Z 2010-11-08
dc.description.abstract Integer 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.language.iso en_US en_US
dc.publisher Kansas State University en
dc.subject Branch and Bound en_US
dc.subject Cutting Planes en_US
dc.title Theoretically and computationally improving branch and bound through multivariate branching with internal cutting planes en_US
dc.type Thesis en_US Master of Science en_US
dc.description.level Masters en_US
dc.description.department Department of Industrial & Manufacturing Systems Engineering en_US
dc.description.advisor Todd W. Easton en_US
dc.subject.umi Engineering, Industrial (0546) en_US 2010 en_US December en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search K-REx

Advanced Search


My Account


Center for the

Advancement of Digital