IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v258y2017i2p590-606.html
   My bibliography  Save this article

A parallel Branch-and-Fix Coordination based matheuristic algorithm for solving large sized multistage stochastic mixed 0–1 problems

Author

Listed:
  • Aldasoro, Unai
  • Escudero, Laureano F.
  • Merino, María
  • Pérez, Gloria

Abstract

A parallel matheuristic algorithm is presented as a spin-off from the exact Branch-and-Fix Coordination (BFC) algorithm for solving multistage stochastic mixed 0–1 problems. Some steps to guarantee the solution’s optimality are relaxed in the BFC algorithm, such that an incomplete backward branching scheme is considered for solving large sized problems. Additionally, a new branching criterion is considered, based on dynamically-guided and stage-wise ordering schemes, such that fewer Twin Node Families are expected to be visited during the execution of the so-called H-DBFC algorithm. The inner parallelization IH-DBFC of the new approach, allows to solve in parallel scenario clusters MIP submodels at different steps of the algorithm. The outer parallel version, OH-DBFC, considers independent paths and allows iterative incumbent solution values exchanges to obtain tighter bounds of the solution value of the original problem. A broad computational experience is reported for assessing the quality of the matheuristic solution for large sized instances. The instances dimensions that are considered are up to two orders of magnitude larger than in some other works that we are aware of. The optimality gap of the H-DBFC solution value versus the one obtained by a state-of-the-art MIP solver is very small, if any. The new approach frequently outperforms it in terms of solution’s quality and computing time. A comparison with our Stochastic Dynamic Programming algorithm is also reported. The use of parallel computing provides, on one hand, a perspective for solving very large sized instances and, on the other hand, an expected large reduction in elapsed time.

Suggested Citation

  • Aldasoro, Unai & Escudero, Laureano F. & Merino, María & Pérez, Gloria, 2017. "A parallel Branch-and-Fix Coordination based matheuristic algorithm for solving large sized multistage stochastic mixed 0–1 problems," European Journal of Operational Research, Elsevier, vol. 258(2), pages 590-606.
    • Handle: RePEc:eee:ejores:v:258:y:2017:i:2:p:590-606
    DOI: 10.1016/j.ejor.2016.08.072
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716307111
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2016.08.072?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Pagès-Bernaus, Adela & Pérez-Valdés, Gerardo & Tomasgard, Asgeir, 2015. "A parallelised distributed implementation of a Branch and Fix Coordination algorithm," European Journal of Operational Research, Elsevier, vol. 244(1), pages 77-85.
    2. Monique Guignard, 2003. "Lagrangean relaxation," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 11(2), pages 151-200, December.
    3. Laureano Escudero, 2009. "On a mixture of the fix-and-relax coordination and Lagrangian substitution schemes for multistage stochastic mixed integer programming," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 17(1), pages 5-29, July.
    4. L.F. Escudero & J.L. De La Fuente & C. García & F.J. Prieto, 1999. "A parallel computation approach for solvingmultistage stochastic network problems," Annals of Operations Research, Springer, vol. 90(0), pages 131-160, January.
    5. Escudero, Laureano F. & Garín, María Araceli & Merino, María & Pérez, Gloria, 2016. "On time stochastic dominance induced by mixed integer-linear recourse in multistage stochastic programs," European Journal of Operational Research, Elsevier, vol. 249(1), pages 164-176.
    6. Shapiro, Alexander & Tekaya, Wajdi & da Costa, Joari Paulo & Soares, Murilo Pereira, 2013. "Risk neutral and risk averse Stochastic Dual Dynamic Programming method," European Journal of Operational Research, Elsevier, vol. 224(2), pages 375-391.
    7. Vincent Guigues, 2014. "SDDP for some interstage dependent risk-averse problems and application to hydro-thermal planning," Computational Optimization and Applications, Springer, vol. 57(1), pages 167-203, January.
    8. L. F. Escudero & J. F. Monge & D. Romero Morales & J. Wang, 2013. "Expected Future Value Decomposition Based Bid Price Generation for Large-Scale Network Revenue Management," Transportation Science, INFORMS, vol. 47(2), pages 181-197, May.
    9. Dias, Bruno Henriques & Tomim, Marcelo Aroca & Marcato, André Luís Marques & Ramos, Tales Pulinho & Brandi, Rafael Bruno S. & Junior, Ivo Chaves da Silva & Filho, João Alberto Passos, 2013. "Parallel computing applied to the stochastic dynamic programming for long term operation planning of hydrothermal power systems," European Journal of Operational Research, Elsevier, vol. 229(1), pages 212-222.
    10. Unai Aldasoro & Laureano Escudero & María Merino & Juan Monge & Gloria Pérez, 2015. "On parallelization of a stochastic dynamic programming algorithm for solving large-scale mixed 0–1 problems under uncertainty," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 23(3), pages 703-742, October.
    11. Jean-Paul Watson & David Woodruff, 2011. "Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems," Computational Management Science, Springer, vol. 8(4), pages 355-370, November.
    12. Laureano Escudero, 2009. "Rejoinder on: On a mixture of the fix-and-relax coordination and Lagrangean substitution schemes for multistage stochastic mixed integer programming," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 17(1), pages 40-43, July.
    13. Jeff Linderoth & Alexander Shapiro & Stephen Wright, 2006. "The empirical behavior of sampling methods for stochastic programming," Annals of Operations Research, Springer, vol. 142(1), pages 215-241, February.
    14. Guglielmo Lulli & Suvrajeet Sen, 2004. "A Branch-and-Price Algorithm for Multistage Stochastic Integer Programming with Application to Stochastic Batch-Sizing Problems," Management Science, INFORMS, vol. 50(6), pages 786-796, June.
    15. H. Vladimirou & S.A. Zenios, 1999. "Scalable parallel computations forlarge-scale stochastic programming," Annals of Operations Research, Springer, vol. 90(0), pages 87-129, January.
    16. Laureano Escudero & Araceli Garín & María Merino & Gloria Pérez, 2009. "BFC-MSMIP: an exact branch-and-fix coordination approach for solving multistage stochastic mixed 0–1 problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 17(1), pages 96-122, July.
    17. Lulli, Guglielmo & Sen, Suvrajeet, 2006. "A heuristic procedure for stochastic integer programs with complete recourse," European Journal of Operational Research, Elsevier, vol. 171(3), pages 879-890, June.
    18. John R. Birge, 1985. "Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs," Operations Research, INFORMS, vol. 33(5), pages 989-1007, October.
    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. Guido Schryen & Natalia Kliewer & Andreas Fink, 2020. "High Performance Business Computing," Business & Information Systems Engineering: The International Journal of WIRTSCHAFTSINFORMATIK, Springer;Gesellschaft für Informatik e.V. (GI), vol. 62(1), pages 1-3, February.
    2. Unai Aldasoro & María Merino & Gloria Pérez, 2019. "Time consistent expected mean-variance in multistage stochastic quadratic optimization: a model and a matheuristic," Annals of Operations Research, Springer, vol. 280(1), pages 151-187, September.
    3. Guido Schryen & Natalia Kliewer & Andreas Fink, 2018. "Call for Papers Issue 1/2020," Business & Information Systems Engineering: The International Journal of WIRTSCHAFTSINFORMATIK, Springer;Gesellschaft für Informatik e.V. (GI), vol. 60(5), pages 439-440, October.
    4. Cadarso, Luis & Escudero, Laureano F. & Marín, Angel, 2018. "On strategic multistage operational two-stage stochastic 0–1 optimization for the Rapid Transit Network Design problem," European Journal of Operational Research, Elsevier, vol. 271(2), pages 577-593.
    5. Escudero, Laureano F. & Monge, Juan F. & Rodríguez-Chía, Antonio M., 2020. "On pricing-based equilibrium for network expansion planning. A multi-period bilevel approach under uncertainty," European Journal of Operational Research, Elsevier, vol. 287(1), pages 262-279.
    6. Escudero, Laureano F. & Garín, M. Araceli & Monge, Juan F. & Unzueta, Aitziber, 2020. "Some matheuristic algorithms for multistage stochastic optimization models with endogenous uncertainty and risk management," European Journal of Operational Research, Elsevier, vol. 285(3), pages 988-1001.
    7. Iturriaga, E. & Aldasoro, U. & Terés-Zubiaga, J. & Campos-Celador, A., 2018. "Optimal renovation of buildings towards the nearly Zero Energy Building standard," Energy, Elsevier, vol. 160(C), pages 1101-1114.
    8. Schryen, Guido, 2020. "Parallel computational optimization in operations research: A new integrative framework, literature review and research directions," European Journal of Operational Research, Elsevier, vol. 287(1), pages 1-18.

    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. Unai Aldasoro & Laureano Escudero & María Merino & Juan Monge & Gloria Pérez, 2015. "On parallelization of a stochastic dynamic programming algorithm for solving large-scale mixed 0–1 problems under uncertainty," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 23(3), pages 703-742, October.
    2. Escudero, Laureano F. & Landete, Mercedes & Rodríguez-Chía, Antonio M., 2011. "Stochastic set packing problem," European Journal of Operational Research, Elsevier, vol. 211(2), pages 232-240, June.
    3. Eguía Ribero, María Isabel & Garín Martín, María Araceli & Unzueta Inchaurbe, Aitziber, 2018. "Generating cluster submodels from two-stage stochastic mixed integer optimization models," BILTOKI 31248, Universidad del País Vasco - Departamento de Economía Aplicada III (Econometría y Estadística).
    4. Semih Atakan & Suvrajeet Sen, 2018. "A Progressive Hedging based branch-and-bound algorithm for mixed-integer stochastic programs," Computational Management Science, Springer, vol. 15(3), pages 501-540, October.
    5. İ. Esra Büyüktahtakın, 2022. "Stage-t scenario dominance for risk-averse multi-stage stochastic mixed-integer programs," Annals of Operations Research, Springer, vol. 309(1), pages 1-35, February.
    6. Escudero, Laureano F. & Monge, Juan F. & Rodríguez-Chía, Antonio M., 2020. "On pricing-based equilibrium for network expansion planning. A multi-period bilevel approach under uncertainty," European Journal of Operational Research, Elsevier, vol. 287(1), pages 262-279.
    7. Giovanni Pantuso & Trine K. Boomsma, 2020. "On the number of stages in multistage stochastic programs," Annals of Operations Research, Springer, vol. 292(2), pages 581-603, September.
    8. W. Ackooij & X. Warin, 2020. "On conditional cuts for stochastic dual dynamic programming," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 8(2), pages 173-199, June.
    9. Andre Luiz Diniz & Maria Elvira P. Maceira & Cesar Luis V. Vasconcellos & Debora Dias J. Penna, 2020. "A combined SDDP/Benders decomposition approach with a risk-averse surface concept for reservoir operation in long term power generation planning," Annals of Operations Research, Springer, vol. 292(2), pages 649-681, September.
    10. Laureano Escudero, 2009. "On a mixture of the fix-and-relax coordination and Lagrangian substitution schemes for multistage stochastic mixed integer programming," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 17(1), pages 5-29, July.
    11. Michelle Bandarra & Vincent Guigues, 2021. "Single cut and multicut stochastic dual dynamic programming with cut selection for multistage stochastic linear programs: convergence proof and numerical experiments," Computational Management Science, Springer, vol. 18(2), pages 125-148, June.
    12. Bakker, Hannah & Dunke, Fabian & Nickel, Stefan, 2020. "A structuring review on multi-stage optimization under uncertainty: Aligning concepts from theory and practice," Omega, Elsevier, vol. 96(C).
    13. Schryen, Guido, 2020. "Parallel computational optimization in operations research: A new integrative framework, literature review and research directions," European Journal of Operational Research, Elsevier, vol. 287(1), pages 1-18.
    14. Ankur Kulkarni & Uday Shanbhag, 2012. "Recourse-based stochastic nonlinear programming: properties and Benders-SQP algorithms," Computational Optimization and Applications, Springer, vol. 51(1), pages 77-123, January.
    15. Alonso-Ayuso, Antonio & Escudero, Laureano F. & Guignard, Monique & Weintraub, Andres, 2018. "Risk management for forestry planning under uncertainty in demand and prices," European Journal of Operational Research, Elsevier, vol. 267(3), pages 1051-1074.
    16. Can Li & Ignacio E. Grossmann, 2019. "A finite $$\epsilon $$ϵ-convergence algorithm for two-stage stochastic convex nonlinear programs with mixed-binary first and second-stage variables," Journal of Global Optimization, Springer, vol. 75(4), pages 921-947, December.
    17. Soares, Murilo Pereira & Street, Alexandre & Valladão, Davi Michel, 2017. "On the solution variability reduction of Stochastic Dual Dynamic Programming applied to energy planning," European Journal of Operational Research, Elsevier, vol. 258(2), pages 743-760.
    18. Martin N. Hjelmeland & Arild Helseth & Magnus Korpås, 2019. "Medium-Term Hydropower Scheduling with Variable Head under Inflow, Energy and Reserve Capacity Price Uncertainty," Energies, MDPI, vol. 12(1), pages 1-15, January.
    19. Vincent Guigues, 2014. "SDDP for some interstage dependent risk-averse problems and application to hydro-thermal planning," Computational Optimization and Applications, Springer, vol. 57(1), pages 167-203, January.
    20. Wolf, Christian & Koberstein, Achim, 2013. "Dynamic sequencing and cut consolidation for the parallel hybrid-cut nested L-shaped method," European Journal of Operational Research, Elsevier, vol. 230(1), pages 143-156.

    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:eee:ejores:v:258:y:2017:i:2:p:590-606. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.