New methods for branch-and-bound algorithms.
Degree: PhD, 0112, 2014, University of Illinois – Urbana-Champaign
Branch-and-bound (B&B) algorithms, and extensions such as branch-and-price (B&P) are powerful tools for optimization. These algorithms are used in a wide variety of settings, and thus it is beneficial to develop new techniques to improve the performance of B&B algorithms that are independent of the specific problem being studied. This dissertation describes three such techniques.
First, new results for the cyclic best-first search (CBFS) strategy are presented. This strategy groups subproblems into a list of contours which it repeatedly cycles through. The strategy selects one subproblem to explore from each contour on every pass through the list. Theoretical results are proven showing the generality of the CBFS strategy, and bounds are given on the number of subproblems the strategy explores. Moreover, an analysis of various contour definitions is performed to ascertain the factors that drive its performance.
In addition, two general-purpose methods are described for B&P algorithms that enable standard integer branching rules to be used while limiting the computation time required to solve the constrained pricing problem (i.e., the pricing problem which respects the branching decisions at the current subproblem). The first method uses a data structure called a zero-suppressed binary decision diagram (ZDD) to solve the pricing problem and keep track of previous branching decisions. Bounds are proved on the size of a ZDD for the maximum-weight maximal independent set problem, which is used to solve the pricing problem in a B&P algorithm for the graph coloring problem.
The last method described in this dissertation restructures the search tree in a B&P setting using a wide branching strategy so as to minimize the number of times the constrained pricing problem must be solved. This restructuring is motivated by the Wide Branching Theorem, which guarantees the existence of a smallest search tree for a fixed set of pruning rules. A delayed branching technique is described that limits the branching factor of the search tree, and forgetful branching is applied to further reduce the number of times the constrained pricing problem needs to be solved in the tree.
Computational results are presented for all methods on various optimization problems (mixed integer programming, graph coloring, the generalized assignment problem, and the simple assembly line balancing problem). Finally, future research directions are presented.
Advisors/Committee Members: Jacobson, Sheldon H. (advisor), Jacobson, Sheldon H. (Committee Chair), Sewell, Edward C. (committee member), Godfrey, Philip B. (committee member), Forsyth, David A. (committee member).
Subjects/Keywords: branch-and-bound; branch-and-price; search strategies; zero-suppressed binary decision diagrams; wide branching; graph coloring; mixed integer programming
…second B&P extension, called wide branching, is presented in Chapter 5. Instead of trying to… …Phase 1:
Branching Binary Branching
Strategy Wide Branching… …Rules
Branching… …binary, or wide, branching strategies. Additionally, due to the prevalence of integer… …that assign a particular task
to a worker.
In contrast to binary…
to Zotero / EndNote / Reference
APA (6th Edition):
Morrison, D. (2014). New methods for branch-and-bound algorithms. (Doctoral Dissertation). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/50713
Chicago Manual of Style (16th Edition):
Morrison, David. “New methods for branch-and-bound algorithms.” 2014. Doctoral Dissertation, University of Illinois – Urbana-Champaign. Accessed June 16, 2019.
MLA Handbook (7th Edition):
Morrison, David. “New methods for branch-and-bound algorithms.” 2014. Web. 16 Jun 2019.
Morrison D. New methods for branch-and-bound algorithms. [Internet] [Doctoral dissertation]. University of Illinois – Urbana-Champaign; 2014. [cited 2019 Jun 16].
Available from: http://hdl.handle.net/2142/50713.
Council of Science Editors:
Morrison D. New methods for branch-and-bound algorithms. [Doctoral Dissertation]. University of Illinois – Urbana-Champaign; 2014. Available from: http://hdl.handle.net/2142/50713