New methods for branch-and-bound algorithms

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2014

Author dc:creator

• Morrison, David

Contributors dc:contributor

• Jacobson, Sheldon H.
• Sewell, Edward C.
• Godfrey, Philip B.
• Forsyth, David A.

• branch-and-price
• search strategies
• zero-suppressed binary decision diagrams
• wide branching
• branch-and-bound
• graph coloring
• mixed integer programming

Statement dc:rights

• Copyright 2014 David R. Morrison

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/50713

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/50713