Files in this item
Files  Description  Format 

application/pdf David_Morrison.pdf (960kB)  (no description provided) 
Description
Title:  New methods for branchandbound algorithms 
Author(s):  Morrison, David 
Director of Research:  Jacobson, Sheldon H. 
Doctoral Committee Chair(s):  Jacobson, Sheldon H. 
Doctoral Committee Member(s):  Sewell, Edward C.; Godfrey, Philip B.; Forsyth, David A. 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  branchandbound
branchandprice search strategies zerosuppressed binary decision diagrams wide branching graph coloring mixed integer programming 
Abstract:  Branchandbound (B&B) algorithms, and extensions such as branchandprice (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 bestfirst 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 generalpurpose 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 zerosuppressed 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 maximumweight 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. 
Issue Date:  20140916 
URI:  http://hdl.handle.net/2142/50713 
Rights Information:  Copyright 2014 David R. Morrison 
Date Available in IDEALS:  20140916 
Date Deposited:  201408 
This item appears in the following Collection(s)

Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois