Master of Science / Department of Industrial and Manufacturing Systems Engineering / Todd Easton / Integer Programs (IP) are a class of discrete optimization that have been used commercially
to improve various systems. IPs are often used to reach an optimal financial objective
with constraints based upon resources, operations and other restrictions. While incredibly
beneficial, IPs have been shown to be NP-complete with many IPs remaining unsolvable.
Traditionally, Branch and Bound (BB) has been used to solve IPs. BB is an iterative
algorithm that enumerates all potential integer solutions for a given IP. BB can guarantee
an optimal solution, if it exists, in finite time. However, BB can require an exponential
number of nodes to be evaluated before terminating. As a result, the memory of a computer
using BB can be exceeded or it can take an excessively long time to find the solution.
This thesis introduces a modified BB scheme called the Octanary Branching Algorithm
(OBA). OBA introduces eight children in each iteration to more effectively partition the
feasible region of the linear relaxation of the IP. OBA also introduces equality constraints
in four of the children in order to reduce the dimension of the remaining nodes. OBA can
guarantee an optimal solution, if it exists, in finite time. In addition, OBA has been shown
to have some theoretical improvements over traditional BB. During computational tests,
OBA was able to find the first, second and third integer solution with 64.8%, 27.9% and
29.3% fewer nodes evaluated, respectively, than CPLEX. These integers were 44.9%, 54.7%
and 58.2% closer to the optimal solution, respectively, when compared to CPLEX. It is
recommended that commercial solvers incorporate OBA in the initialization and random
diving phases of BB.
| Identifer | oai:union.ndltd.org:KSU/oai:krex.k-state.edu:2097/13801 |
| Date | January 1900 |
| Creators | Bailey, James Patrick |
| Publisher | Kansas State University |
| Source Sets | K-State Research Exchange |
| Language | en_US |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.002 seconds