IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v62y2014i1p114-122.html
   My bibliography  Save this article

Exploiting Erraticism in Search

Author

Listed:
  • Matteo Fischetti

    (Department of Information Engineering, University of Padova, 35131 Padova, Italy)

  • Michele Monaci

    (Department of Information Engineering, University of Padova, 35131 Padova, Italy)

Abstract

High sensitivity to initial conditions is generally viewed as a drawback of tree search methods because it leads to erratic behavior to be mitigated somehow. In this paper we investigate the opposite viewpoint and consider this behavior as an opportunity to exploit. Our working hypothesis is that erraticism is in fact just a consequence of the exponential nature of tree search that acts as a chaotic amplifier, so it is largely unavoidable. We propose a bet-and-run approach to actually turn erraticism to one's advantage. The idea is to make a number of short sample runs with randomized initial conditions, to bet on the “most promising” run selected according to certain simple criteria, and to bring it to completion. Computational results on a large testbed of mixed integer linear programs from the literature are presented, showing the potential of this approach even when embedded in a proof-of-concept implementation.

Suggested Citation

  • Matteo Fischetti & Michele Monaci, 2014. "Exploiting Erraticism in Search," Operations Research, INFORMS, vol. 62(1), pages 114-122, February.
    • Handle: RePEc:inm:oropre:v:62:y:2014:i:1:p:114-122
    DOI: 10.1287/opre.2013.1231
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2013.1231
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2013.1231?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. Gérard Cornuéjols & Miroslav Karamanov & Yanjun Li, 2006. "Early Estimates of the Size of Branch-and-Bound Trees," INFORMS Journal on Computing, INFORMS, vol. 18(1), pages 86-96, February.
    2. Thorsten Koch & Ted Ralphs & Yuji Shinano, 2012. "Could we use a million cores to solve an integer program?," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 76(1), pages 67-93, August.
    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. Alexander Schnell & Richard F. Hartl, 2016. "On the efficient modeling and solution of the multi-mode resource-constrained project scheduling problem with generalized precedence relations," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(2), pages 283-303, March.
    2. Kramer, Arthur & Lalla-Ruiz, Eduardo & Iori, Manuel & Voß, Stefan, 2019. "Novel formulations and modeling enhancements for the dynamic berth allocation problem," European Journal of Operational Research, Elsevier, vol. 278(1), pages 170-185.
    3. Luke Mason & Vicky Mak-Hau & Andreas Ernst, 2015. "A parallel optimisation approach for the realisation problem in intensity modulated radiotherapy treatment planning," Computational Optimization and Applications, Springer, vol. 60(2), pages 441-477, March.
    4. Baïou, Mourad & Colares, Rafael & Kerivin, Hervé, 2023. "Complexity, algorithmic, and computational aspects of a dial-a-ride type problem," European Journal of Operational Research, Elsevier, vol. 310(2), pages 552-565.
    5. Fernando Stefanello & Vaneet Aggarwal & Luciana S. Buriol & Mauricio G. C. Resende, 2019. "Hybrid algorithms for placement of virtual machines across geo-separated data centers," Journal of Combinatorial Optimization, Springer, vol. 38(3), pages 748-793, October.
    6. Elisangela Martins de Sá & Ivan Contreras & Jean-François Cordeau & Ricardo Saraiva de Camargo & Gilberto de Miranda, 2015. "The Hub Line Location Problem," Transportation Science, INFORMS, vol. 49(3), pages 500-518, August.
    7. Alessandro Hill & Eduardo Lalla-Ruiz & Stefan Voß & Marcos Goycoolea, 2019. "A multi-mode resource-constrained project scheduling reformulation for the waterway ship scheduling problem," Journal of Scheduling, Springer, vol. 22(2), pages 173-182, April.
    8. 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.
    9. Bruno P. Bruck & Fábio Cruz & Manuel Iori & Anand Subramanian, 2019. "The Static Bike Sharing Rebalancing Problem with Forbidden Temporary Operations," Transportation Science, INFORMS, vol. 53(3), pages 882-896, May.
    10. 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.
    11. Pietro Belotti & Pierre Bonami & Matteo Fischetti & Andrea Lodi & Michele Monaci & Amaya Nogales-Gómez & Domenico Salvagnin, 2016. "On handling indicator constraints in mixed integer programming," Computational Optimization and Applications, Springer, vol. 65(3), pages 545-566, December.
    12. Miranda, Pablo A. & Blazquez, Carola A. & Obreque, Carlos & Maturana-Ross, Javier & Gutierrez-Jarpa, Gabriel, 2018. "The bi-objective insular traveling salesman problem with maritime and ground transportation costs," European Journal of Operational Research, Elsevier, vol. 271(3), pages 1014-1036.
    13. Ivan Derpich & Juan Valencia & Mario Lopez, 2023. "The Set Covering and Other Problems: An Empiric Complexity Analysis Using the Minimum Ellipsoidal Width," Mathematics, MDPI, vol. 11(13), pages 1-22, June.
    14. Timo Berthold, 2018. "A computational study of primal heuristics inside an MI(NL)P solver," Journal of Global Optimization, Springer, vol. 70(1), pages 189-206, January.
    15. Fischetti, Matteo & Monaci, Michele, 2020. "A branch-and-cut algorithm for Mixed-Integer Bilinear Programming," European Journal of Operational Research, Elsevier, vol. 282(2), pages 506-514.
    16. Michele Monaci & André Gustavo Santos, 2018. "Minimum tiling of a rectangle by squares," Annals of Operations Research, Springer, vol. 271(2), pages 831-851, December.
    17. Lalla-Ruiz, Eduardo & Voß, Stefan, 2016. "Modeling the Parallel Machine Scheduling Problem with Step Deteriorating Jobs," European Journal of Operational Research, Elsevier, vol. 255(1), pages 21-33.
    18. Liang Chen & Wei-Kun Chen & Mu-Ming Yang & Yu-Hong Dai, 2021. "An exact separation algorithm for unsplittable flow capacitated network design arc-set polyhedron," Journal of Global Optimization, Springer, vol. 81(3), pages 659-689, November.

    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. José Berenguel & L. Casado & I. García & Eligius Hendrix, 2013. "On estimating workload in interval branch-and-bound global optimization algorithms," Journal of Global Optimization, Springer, vol. 56(3), pages 821-844, July.
    2. Lluís-Miquel Munguía & Geoffrey Oxberry & Deepak Rajan & Yuji Shinano, 2019. "Parallel PIPS-SBB: multi-level parallelism for stochastic mixed-integer programs," Computational Optimization and Applications, Springer, vol. 73(2), pages 575-601, June.
    3. Yuji Shinano & Stefan Heinz & Stefan Vigerske & Michael Winkler, 2018. "FiberSCIP—A Shared Memory Parallelization of SCIP," INFORMS Journal on Computing, INFORMS, vol. 30(1), pages 11-30, February.
    4. Lluís-Miquel Munguía & Shabbir Ahmed & David A. Bader & George L. Nemhauser & Yufen Shao, 2018. "Alternating criteria search: a parallel large neighborhood search algorithm for mixed integer programs," Computational Optimization and Applications, Springer, vol. 69(1), pages 1-24, January.
    5. Luke Mason & Vicky Mak-Hau & Andreas Ernst, 2015. "A parallel optimisation approach for the realisation problem in intensity modulated radiotherapy treatment planning," Computational Optimization and Applications, Springer, vol. 60(2), pages 441-477, March.
    6. Ivo Nowak & Norman Breitfeld & Eligius M. T. Hendrix & Grégoire Njacheun-Njanzoua, 2018. "Decomposition-based Inner- and Outer-Refinement Algorithms for Global Optimization," Journal of Global Optimization, Springer, vol. 72(2), pages 305-321, October.
    7. 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.
    8. Zhou, Wei & O'Neill, Eoghan & Moncaster, Alice & Reiner, David M. & Guthrie, Peter, 2020. "Forecasting urban residential stock turnover dynamics using system dynamics and Bayesian model averaging," Applied Energy, Elsevier, vol. 275(C).
    9. Timo Berthold, 2018. "A computational study of primal heuristics inside an MI(NL)P solver," Journal of Global Optimization, Springer, vol. 70(1), pages 189-206, January.
    10. Gregor Hendel & Daniel Anderson & Pierre Le Bodic & Marc E. Pfetsch, 2022. "Estimating the Size of Branch-and-Bound Trees," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 934-952, March.
    11. Thorsten Koch & Ted Ralphs & Yuji Shinano, 2012. "Could we use a million cores to solve an integer program?," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 76(1), pages 67-93, August.
    12. Osman Y. Özaltın & Brady Hunsaker & Andrew J. Schaefer, 2011. "Predicting the Solution Time of Branch-and-Bound Algorithms for Mixed-Integer Programs," INFORMS Journal on Computing, INFORMS, vol. 23(3), pages 392-403, August.
    13. Martin Branda, 2013. "On relations between chance constrained and penalty function problems under discrete distributions," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 77(2), pages 265-277, April.

    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:oropre:v:62:y:2014:i:1:p:114-122. 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.