Return to search

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

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / 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.

Identiferoai:union.ndltd.org:KSU/oai:krex.k-state.edu:2097/6496
Date January 1900
CreatorsLee, Jin Hua
PublisherKansas State University
Source SetsK-State Research Exchange
Languageen_US
Detected LanguageEnglish
TypeThesis

Page generated in 0.0024 seconds