New methods for branch-and-bound algorithms

Morrison, David

Permalink

https://hdl.handle.net/2142/50713 Copy

Description

Title

New methods for branch-and-bound algorithms

Author(s)

Morrison, David

Issue Date

2014-09-16

Director of Research (if dissertation) or Advisor (if thesis)

Jacobson, Sheldon H.

Doctoral Committee Chair(s)

Jacobson, Sheldon H.

Committee Member(s)

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

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

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

Abstract

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.

Graduation Semester

2014-08

Permalink

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

Copyright and License Information

Copyright 2014 David R. Morrison

Owning Collections