IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v64y2017i1p64-82.html
   My bibliography  Save this article

Cyclic best first search: Using contours to guide branch‐and‐bound algorithms

Author

Listed:
  • David R. Morrison
  • Jason J. Sauppe
  • Wenda Zhang
  • Sheldon H. Jacobson
  • Edward C. Sewell

Abstract

The cyclic best‐first search (CBFS) strategy is a recent search strategy that has been successfully applied to branch‐and‐bound algorithms in a number of different settings. CBFS is a modification of best‐first search (BFS) that places search tree subproblems into contours which are collections of subproblems grouped in some way, and repeatedly cycles through all non‐empty contours, selecting one subproblem to explore from each. In this article, the theoretical properties of CBFS are analyzed for the first time. CBFS is proved to be a generalization of all other search strategies by using a contour definition that explores the same sequence of subproblems as any other search strategy. Further, a bound is proved between the number of subproblems explored by BFS and the number of children generated by CBFS, given a fixed branching strategy and set of pruning rules. Finally, a discussion of heuristic contour‐labeling functions is provided, and proof‐of‐concept computational results for mixed‐integer programming problems from the MIPLIB 2010 database are shown. © 2017 Wiley Periodicals, Inc. Naval Research Logistics, 64: 64–82, 2017

Suggested Citation

  • David R. Morrison & Jason J. Sauppe & Wenda Zhang & Sheldon H. Jacobson & Edward C. Sewell, 2017. "Cyclic best first search: Using contours to guide branch‐and‐bound algorithms," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(1), pages 64-82, February.
    • Handle: RePEc:wly:navres:v:64:y:2017:i:1:p:64-82
    DOI: 10.1002/nav.21732
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.21732
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.21732?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. E. C. Sewell & S. H. Jacobson, 2012. "A Branch, Bound, and Remember Algorithm for the Simple Assembly Line Balancing Problem," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 433-442, August.
    2. Alper Atamtürk & Martin Savelsbergh, 2005. "Integer-Programming Software Systems," Annals of Operations Research, Springer, vol. 140(1), pages 67-124, November.
    3. Morrison, David R. & Sewell, Edward C. & Jacobson, Sheldon H., 2014. "An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset," European Journal of Operational Research, Elsevier, vol. 236(2), pages 403-409.
    4. Scholl, Armin & Klein, Robert, 1999. "Balancing assembly lines effectively - A computational comparison," European Journal of Operational Research, Elsevier, vol. 114(1), pages 50-58, April.
    5. David R. Morrison & Jason J. Sauppe & Edward C. Sewell & Sheldon H. Jacobson, 2014. "A Wide Branching Strategy for the Graph Coloring Problem," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 704-717, November.
    6. David R. Morrison & Edward C. Sewell & Sheldon H. Jacobson, 2016. "Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 67-82, February.
    7. J. T. Linderoth & M. W. P. Savelsbergh, 1999. "A Computational Study of Search Strategies for Mixed Integer Programming," INFORMS Journal on Computing, INFORMS, vol. 11(2), pages 173-187, May.
    8. Fred Glover, 1990. "Tabu Search: A Tutorial," Interfaces, INFORMS, vol. 20(4), pages 74-94, August.
    9. Edward Sewell & Jason Sauppe & David Morrison & Sheldon Jacobson & Gio Kao, 2012. "A BB&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times," Journal of Global Optimization, Springer, vol. 54(4), pages 791-812, December.
    10. Leyuan Shi & Sigurdur Ólafsson, 2000. "Nested Partitions Method for Global Optimization," Operations Research, INFORMS, vol. 48(3), pages 390-407, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Yolmeh, Abdolmajid & Baykal-Gürsoy, Melike, 2021. "Weighted network search games with multiple hidden objects and multiple search teams," European Journal of Operational Research, Elsevier, vol. 289(1), pages 338-349.
    2. Wenda Zhang & Jason J. Sauppe & Sheldon H. Jacobson, 2021. "An Improved Branch-and-Bound Algorithm for the One-Machine Scheduling Problem with Delayed Precedence Constraints," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1091-1102, July.
    3. Wenda Zhang & Jason J. Sauppe & Sheldon H. Jacobson, 2023. "Results for the close-enough traveling salesman problem with a branch-and-bound algorithm," Computational Optimization and Applications, Springer, vol. 85(2), pages 369-407, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Li, Zixiang & Kucukkoc, Ibrahim & Zhang, Zikai, 2020. "Branch, bound and remember algorithm for two-sided assembly line balancing problem," European Journal of Operational Research, Elsevier, vol. 284(3), pages 896-905.
    2. Wenda Zhang & Jason J. Sauppe & Sheldon H. Jacobson, 2023. "Results for the close-enough traveling salesman problem with a branch-and-bound algorithm," Computational Optimization and Applications, Springer, vol. 85(2), pages 369-407, June.
    3. Morrison, David R. & Sewell, Edward C. & Jacobson, Sheldon H., 2014. "An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset," European Journal of Operational Research, Elsevier, vol. 236(2), pages 403-409.
    4. Wenda Zhang & Jason J. Sauppe & Sheldon H. Jacobson, 2021. "An Improved Branch-and-Bound Algorithm for the One-Machine Scheduling Problem with Delayed Precedence Constraints," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1091-1102, July.
    5. Pape, Tom, 2015. "Heuristics and lower bounds for the simple assembly line balancing problem type 1: Overview, computational tests and improvements," European Journal of Operational Research, Elsevier, vol. 240(1), pages 32-42.
    6. García-Villoria, Alberto & Corominas, Albert & Nadal, Adrià & Pastor, Rafael, 2018. "Solving the accessibility windows assembly line problem level 1 and variant 1 (AWALBP-L1-1) with precedence constraints," European Journal of Operational Research, Elsevier, vol. 271(3), pages 882-895.
    7. Bukchin, Yossi & Raviv, Tal, 2018. "Constraint programming for solving various assembly line balancing problems," Omega, Elsevier, vol. 78(C), pages 57-68.
    8. Pereira, Jordi & Álvarez-Miranda, Eduardo, 2018. "An exact approach for the robust assembly line balancing problem," Omega, Elsevier, vol. 78(C), pages 85-98.
    9. Battaïa, Olga & Dolgui, Alexandre, 2022. "Hybridizations in line balancing problems: A comprehensive review on new trends and formulations," International Journal of Production Economics, Elsevier, vol. 250(C).
    10. Kumar Abhishek & Sven Leyffer & Jeff Linderoth, 2010. "FilMINT: An Outer Approximation-Based Solver for Convex Mixed-Integer Nonlinear Programs," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 555-567, November.
    11. Yolmeh, Abdolmajid & Baykal-Gürsoy, Melike, 2021. "Weighted network search games with multiple hidden objects and multiple search teams," European Journal of Operational Research, Elsevier, vol. 289(1), pages 338-349.
    12. Raphael Kramer & Mauro Dell’Amico & Manuel Iori, 2017. "A batching-move iterated local search algorithm for the bin packing problem with generalized precedence constraints," International Journal of Production Research, Taylor & Francis Journals, vol. 55(21), pages 6288-6304, November.
    13. Jordi Pereira & Mariona Vilà, 2016. "A new model for supply chain network design with integrated assembly line balancing decisions," International Journal of Production Research, Taylor & Francis Journals, vol. 54(9), pages 2653-2669, May.
    14. Pereira, Jordi & Ritt, Marcus, 2023. "Exact and heuristic methods for a workload allocation problem with chain precedence constraints," European Journal of Operational Research, Elsevier, vol. 309(1), pages 387-398.
    15. Pereira, Jordi, 2016. "Procedures for the bin packing problem with precedence constraints," European Journal of Operational Research, Elsevier, vol. 250(3), pages 794-806.
    16. Jiaqiao Hu & Michael C. Fu & Steven I. Marcus, 2007. "A Model Reference Adaptive Search Method for Global Optimization," Operations Research, INFORMS, vol. 55(3), pages 549-568, June.
    17. Boysen, Nils & Schulze, Philipp & Scholl, Armin, 2022. "Assembly line balancing: What happened in the last fifteen years?," European Journal of Operational Research, Elsevier, vol. 301(3), pages 797-814.
    18. Bissan Ghaddar & Ignacio Gómez-Casares & Julio González-Díaz & Brais González-Rodríguez & Beatriz Pateiro-López & Sofía Rodríguez-Ballesteros, 2023. "Learning for Spatial Branching: An Algorithm Selection Approach," INFORMS Journal on Computing, INFORMS, vol. 35(5), pages 1024-1043, September.
    19. Lee, Loo Hay & Chew, Ek Peng & Manikam, Puvaneswari, 2006. "A general framework on the simulation-based optimization under fixed computing budget," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1828-1841, November.
    20. Scholl, Armin & Becker, Christian, 2006. "State-of-the-art exact and heuristic solution procedures for simple assembly line balancing," European Journal of Operational Research, Elsevier, vol. 168(3), pages 666-693, February.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wly:navres:v:64:y:2017:i:1:p:64-82. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.