University of Illinois Urbana-Champaign

Cyclic best first search in branch-and-bound algorithms

Zhang, Wenda

Content Files
ZHANG-DISSERTATION-2020.pdf

Permalink

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

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
Date of Ingest
2020-10-07T20:59:41Z
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

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Industrial and Enterprise Systems Engineering