Octanary branching algorithm

K-REx Repository

Show simple item record

dc.contributor.author Bailey, James Patrick
dc.date.accessioned 2012-05-07T13:41:50Z
dc.date.available 2012-05-07T13:41:50Z
dc.date.issued 2012-05-07
dc.identifier.uri http://hdl.handle.net/2097/13801
dc.description.abstract 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. en_US
dc.language.iso en_US en_US
dc.publisher Kansas State University en
dc.subject Branching Algorithm en_US
dc.subject Integer Programming en_US
dc.title Octanary branching algorithm en_US
dc.type Thesis en_US
dc.description.degree Master of Science en_US
dc.description.level Masters en_US
dc.description.department Department of Industrial and Manufacturing Systems Engineering en_US
dc.description.advisor Todd Easton en_US
dc.subject.umi Industrial Engineering (0546) en_US
dc.subject.umi Mathematics (0405) en_US
dc.subject.umi Operations Research (0796) en_US
dc.date.published 2012 en_US
dc.date.graduationmonth August en_US

Files in this item


Files Size Format View

This item appears in the following Collection(s)

Show simple item record