IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v32y2020i1p3-15.html
   My bibliography  Save this article

Optimization Bounds from the Branching Dual

Author

Listed:
  • Gerdus Benadè

    (Carnegie Mellon University, Pittsburgh, Pennsylvania 15213;)

  • John N. Hooker

    (Carnegie Mellon University, Pittsburgh, Pennsylvania 15213)

Abstract

We present a general method for obtaining strong bounds for discrete optimization problems that is based on a concept of branching duality. It can be applied when no useful integer programming model is available, and we illustrate this with the minimum bandwidth problem. The method strengthens a known bound for a given problem by formulating a dual problem whose feasible solutions are partial branching trees. It solves the dual problem with a “worst-bound” local search heuristic that explores neighboring partial trees. After proving some optimality properties of the heuristic, we show that it substantially improves known combinatorial bounds for the minimum bandwidth problem with a modest amount of computation. It also obtains significantly tighter bounds than depth-first and breadth-first branching, demonstrating that the dual perspective can lead to better branching strategies when the object is to find valid bounds.

Suggested Citation

  • Gerdus Benadè & John N. Hooker, 2020. "Optimization Bounds from the Branching Dual," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 3-15, January.
    • Handle: RePEc:inm:orijoc:v:32:y:2020:i:1:p:3-15
    DOI: 10.1287/ijoc.2018.0884
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2018.0884
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2018.0884?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. Alberto Caprara & Adam N. Letchford & Juan-José Salazar-González, 2011. "Decorous Lower Bounds for Minimum Linear Arrangement," INFORMS Journal on Computing, INFORMS, vol. 23(1), pages 26-40, February.
    2. M. W. Dawande & J. N. Hooker, 2000. "Inference-Based Sensitivity Analysis for Mixed Integer/Linear Programming," Operations Research, INFORMS, vol. 48(4), pages 623-634, August.
    3. 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.
    4. Alejandro Marcos Alvarez & Quentin Louveaux & Louis Wehenkel, 2017. "A Machine Learning-Based Approximation of Strong Branching," INFORMS Journal on Computing, INFORMS, vol. 29(1), pages 185-195, February.
    5. John N. Hooker, 2012. "Integrated Methods for Optimization," International Series in Operations Research and Management Science, Springer, number 978-1-4614-1900-6, December.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    2. Andrea Lodi & Giulia Zarpellon, 2017. "On learning and branching: a survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 25(2), pages 207-236, July.
    3. Yu Yang & Natashia Boland & Martin Savelsbergh, 2021. "Multivariable Branching: A 0-1 Knapsack Problem Case Study," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1354-1367, October.
    4. Yang, Yu & Boland, Natashia & Dilkina, Bistra & Savelsbergh, Martin, 2022. "Learning generalized strong branching for set covering, set packing, and 0–1 knapsack problems," European Journal of Operational Research, Elsevier, vol. 301(3), pages 828-840.
    5. Markus Chimani & Philipp Hungerländer, 2013. "Exact Approaches to Multilevel Vertical Orderings," INFORMS Journal on Computing, INFORMS, vol. 25(4), pages 611-624, November.
    6. Dimitris Bertsimas & Cheol Woo Kim, 2023. "A Prescriptive Machine Learning Approach to Mixed-Integer Convex Optimization," INFORMS Journal on Computing, INFORMS, vol. 35(6), pages 1225-1241, November.
    7. Francisco Jara-Moroni & John E. Mitchell & Jong-Shi Pang & Andreas Wächter, 2020. "An enhanced logical benders approach for linear programs with complementarity constraints," Journal of Global Optimization, Springer, vol. 77(4), pages 687-714, August.
    8. Ruslan Sadykov & François Vanderbeck & Artur Pessoa & Issam Tahiri & Eduardo Uchoa, 2019. "Primal Heuristics for Branch and Price: The Assets of Diving Methods," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 251-267, April.
    9. Nikolaus Furian & Michael O’Sullivan & Cameron Walker & Eranda Çela, 2021. "A machine learning-based branch and price algorithm for a sampled vehicle routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(3), pages 693-732, September.
    10. Bengio, Yoshua & Lodi, Andrea & Prouvost, Antoine, 2021. "Machine learning for combinatorial optimization: A methodological tour d’horizon," European Journal of Operational Research, Elsevier, vol. 290(2), pages 405-421.
    11. 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.
    12. Hejl, Lukáš & Šůcha, Přemysl & Novák, Antonín & Hanzálek, Zdeněk, 2022. "Minimizing the weighted number of tardy jobs on a single machine: Strongly correlated instances," European Journal of Operational Research, Elsevier, vol. 298(2), pages 413-424.
    13. Dahlbeck, Mirko & Fischer, Anja & Fischer, Frank, 2020. "Decorous combinatorial lower bounds for row layout problems," European Journal of Operational Research, Elsevier, vol. 286(3), pages 929-944.
    14. Anjos, Miguel F. & Fischer, Anja & Hungerländer, Philipp, 2018. "Improved exact approaches for row layout problems with departments of equal length," European Journal of Operational Research, Elsevier, vol. 270(2), pages 514-529.
    15. Maryam Daryalal & Hamed Pouya & Marc Antoine DeSantis, 2023. "Network Migration Problem: A Hybrid Logic-Based Benders Decomposition Approach," INFORMS Journal on Computing, INFORMS, vol. 35(3), pages 593-613, May.
    16. Kandula, Shanthan & Krishnamoorthy, Srikumar & Roy, Debjit, 2021. "Learning to Play the Box-Sizing Game: A Machine Learning Approach for Solving the E-commerce Packaging Problem," IIMA Working Papers WP 2021-11-02, Indian Institute of Management Ahmedabad, Research and Publication Department.
    17. Vincent T’kindt & Federico Della Croce & Jean-Louis Bouquard, 2007. "Enumeration of Pareto Optima for a Flowshop Scheduling Problem with Two Criteria," INFORMS Journal on Computing, INFORMS, vol. 19(1), pages 64-72, February.
    18. David Bergman & Andre A. Cire & Willem-Jan van Hoeve & J. N. Hooker, 2016. "Discrete Optimization with Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 47-66, February.
    19. 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.
    20. S. Göttlich & A. Potschka & C. Teuber, 2019. "A partial outer convexification approach to control transmission lines," Computational Optimization and Applications, Springer, vol. 72(2), pages 431-456, March.

    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:inm:orijoc:v:32:y:2020:i:1:p:3-15. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.