{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/108464"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/108464","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Cyclic best first search in branch-and-bound algorithms","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Zhang, Wenda"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Industrial Engineering","degree_department":null,"school":null,"contributors":["Jacobson, Sheldon H","King, Douglas","Chen, Xin","Marla, Lavanya"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020-10-07T20:59:41Z","date_published":"2020-10-07T20:59:41Z","updated_at":"2026-07-22T22:24:48Z","subjects":["Branch-and-bound","Search Strategy","Cyclic Best First Search","Combinatorial Optimization"],"languages":["en"],"rights":["Copyright 2020 Wenda Zhang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/108464","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Jacobson, Sheldon H","King, Douglas","Chen, Xin","Marla, Lavanya"]},{"key":"dc:creator","label":"Author","values":["Zhang, Wenda"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-10-07T20:59:41Z","2020-07-17","2020-08"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Branch-and-bound","Search Strategy","Cyclic Best First Search","Combinatorial Optimization"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2020 Wenda Zhang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/108464"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-10-02 without embargo terms","The student, Wenda Zhang, accepted the attached license on 2020-07-08 at 17:07.","The student, Wenda Zhang, submitted this Dissertation for approval on 2020-07-08 at 17:14.","This Dissertation was approved for publication on 2020-07-17 at 11:16.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15532 on 2020-10-02 at 15:12:38","Made available in DSpace on 2020-10-07T20:59:41Z (GMT). No. of bitstreams: 2 ZHANG-DISSERTATION-2020.pdf: 1100023 bytes, checksum: eb229bec487cf011aa95b708022e8214 (MD5) LICENSE.txt: 4208 bytes, checksum: 1cd29239a641bb8080d86b67bb3767b9 (MD5) Previous issue date: 2020-07-17"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Cyclic best first search in branch-and-bound algorithms"]}]}],"canonical_facts":{"dc:contributor":["Jacobson, Sheldon H","King, Douglas","Chen, Xin","Marla, Lavanya"],"dc:creator":["Zhang, Wenda"],"dc:date":["2020-10-07T20:59:41Z","2020-07-17","2020-08"],"dc:description":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-10-02 without embargo terms","The student, Wenda Zhang, accepted the attached license on 2020-07-08 at 17:07.","The student, Wenda Zhang, submitted this Dissertation for approval on 2020-07-08 at 17:14.","This Dissertation was approved for publication on 2020-07-17 at 11:16.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15532 on 2020-10-02 at 15:12:38","Made available in DSpace on 2020-10-07T20:59:41Z (GMT). No. of bitstreams: 2 ZHANG-DISSERTATION-2020.pdf: 1100023 bytes, checksum: eb229bec487cf011aa95b708022e8214 (MD5) LICENSE.txt: 4208 bytes, checksum: 1cd29239a641bb8080d86b67bb3767b9 (MD5) Previous issue date: 2020-07-17"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/108464"],"dc:language":["en"],"dc:rights":["Copyright 2020 Wenda Zhang"],"dc:subject":["Branch-and-bound","Search Strategy","Cyclic Best First Search","Combinatorial Optimization"],"dc:title":["Cyclic best first search in branch-and-bound algorithms"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Industrial Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:48Z"}