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

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    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, 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    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.

    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.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Haili He). General contact details of provider: http://www.elsevier.com/locate/eor .

    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 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.