Cyclic best first search in branch-and-bound algorithms

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Industrial Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2020

Author dc:creator

• Zhang, Wenda

Contributors dc:contributor

• Jacobson, Sheldon H
• King, Douglas
• Chen, Xin
• Marla, Lavanya

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

Statement dc:rights

• Copyright 2020 Wenda Zhang

Language dc:language

en

Handle dc:identifier

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

OAI identifier oai:identifier

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