Cyclic best first search in branch-and-bound algorithms

Zhang, Wenda

Permalink

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

Description

Title

Cyclic best first search in branch-and-bound algorithms

Author(s)

Zhang, Wenda

Issue Date

2020-07-17

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

Jacobson, Sheldon H

Doctoral Committee Chair(s)

King, Douglas

Committee Member(s)

• Chen, Xin
• Marla, Lavanya

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Branch-and-bound
• Search Strategy
• Cyclic Best First Search
• Combinatorial Optimization

Abstract

In this dissertation, we study the application of a search strategy called cyclic best first search (CBFS) in branch-and-bound (B&B) algorithms. First, we solve a one machine scheduling problem with release and delivery times with the minimum makespan objective with a B&B algorithm using a variant of CBFS called CBFS-depth and a modified heuristic for finding feasible schedules. Second, we investigate the conditions of the search trees that may lead to CBFS-depth outperforming BFS in terms of the average number of nodes explored to prove optimality. Finally, we present a B&B algorithm using CBFS for a close-enough traveling salesman problem that demonstrates the benefit of using CBFS even if it does not improve the number of nodes explored to prove optimality. Overall, we show that using CBFS has a number of advantages to the performance of a B&B algorithm in comparison to the other search strategies given the right problems.

Graduation Semester

2020-08

Type of Resource

Thesis

Permalink

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

Copyright and License Information

Copyright 2020 Wenda Zhang

Owning Collections