Files in this item

FilesDescriptionFormat

application/pdf

application/pdfZHANG-DISSERTATION-2020.pdf (1MB)
(no description provided)PDF

Description

Title:Cyclic best first search in branch-and-bound algorithms
Author(s):Zhang, Wenda
Director of Research:Jacobson, Sheldon H
Doctoral Committee Chair(s):King, Douglas
Doctoral Committee Member(s):Chen, Xin; Marla, Lavanya
Department / Program:Industrial&Enterprise Sys Eng
Discipline:Industrial Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(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.
Issue Date:2020-07-17
Type:Thesis
URI:http://hdl.handle.net/2142/108464
Rights Information:Copyright 2020 Wenda Zhang
Date Available in IDEALS:2020-10-07
Date Deposited:2020-08


This item appears in the following Collection(s)

Item Statistics