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.
| Identifer | oai:union.ndltd.org:KSU/oai:krex.k-state.edu:2097/6496 |
| Date | January 1900 |
| Creators | Lee, Jin Hua |
| Publisher | Kansas State University |
| Source Sets | K-State Research Exchange |
| Language | en_US |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0021 seconds