IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v22y2016i2d10.1007_s10732-015-9304-3.html
   My bibliography  Save this article

PSO-based and SA-based metaheuristics for bilinear programming problems: an application to the pooling problem

Author

Listed:
  • Gökalp Erbeyoğlu

    (Boğaziçi University)

  • Ümit Bilge

    (Boğaziçi University)

Abstract

Bilinear programming problems (BLP) are subsets of nonconvex quadratic programs and can be classified as strongly NP-Hard. The exact methods to solve the BLPs are inefficient for large instances and only a few heuristic methods exist. In this study, we propose two metaheuristic methods, one is based on particle swarm optimization (PSO) and the other is based on simulated annealing (SA). Both of the proposed approaches take advantage of the bilinear structure of the problem. For the PSO-based method, a search variable, which is selected among the variable sets causing bilinearity, is subjected to particle swarm optimization. The SA-based procedure incorporates a variable neighborhood scheme. The pooling problem, which has several application areas in chemical industry and formulated as a BLP, is selected as a test bed to analyze the performances. Extensive experiments are conducted and they indicate the success of the proposed solution methods.

Suggested Citation

  • Gökalp Erbeyoğlu & Ümit Bilge, 2016. "PSO-based and SA-based metaheuristics for bilinear programming problems: an application to the pooling problem," Journal of Heuristics, Springer, vol. 22(2), pages 147-179, April.
    • Handle: RePEc:spr:joheur:v:22:y:2016:i:2:d:10.1007_s10732-015-9304-3
    DOI: 10.1007/s10732-015-9304-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-015-9304-3
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10732-015-9304-3?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. David H. Evans, 1963. "Modular Design---A Special Case in Nonlinear Programming," Operations Research, INFORMS, vol. 11(4), pages 637-647, August.
    2. Jaco Schutte & Albert Groenwold, 2005. "A Study of Global Optimization Using Particle Swarms," Journal of Global Optimization, Springer, vol. 31(1), pages 93-108, January.
    3. Christodoulos A. Floudas & Avanish Aggarwal, 1990. "A Decomposition Strategy for Global Optimum Search in the Pooling Problem," INFORMS Journal on Computing, INFORMS, vol. 2(3), pages 225-235, August.
    4. Harvey J. Greenberg, 1995. "Analyzing the Pooling Problem," INFORMS Journal on Computing, INFORMS, vol. 7(2), pages 205-217, May.
    5. Yiqiang Su & Joseph Geunes, 2013. "Multi-period price promotions in a single-supplier, multi-retailer supply chain under asymmetric demand information," Annals of Operations Research, Springer, vol. 211(1), pages 447-472, December.
    6. Charles Audet & Jack Brimberg & Pierre Hansen & Sébastien Le Digabel & Nenad Mladenovi'{c}, 2004. "Pooling Problem: Alternate Formulations and Solution Methods," Management Science, INFORMS, vol. 50(6), pages 761-776, June.
    7. Al-Khayyal, Faiz A., 1992. "Generalized bilinear programming: Part I. Models, applications and linear programming relaxation," European Journal of Operational Research, Elsevier, vol. 60(3), pages 306-314, August.
    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. Michelle L. Blom & Christina N. Burt & Adrian R. Pearce & Peter J. Stuckey, 2014. "A Decomposition-Based Heuristic for Collaborative Scheduling in a Network of Open-Pit Mines," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 658-676, November.
    2. Benhamou, Latifa & Giard, Vincent & Khouloud, Mehdi & Fenies, Pierres & Fontane, Frédéric, 2020. "Reverse Blending: An economically efficient approach to the challenge of fertilizer mass customization," International Journal of Production Economics, Elsevier, vol. 226(C).
    3. Akshay Gupte & Shabbir Ahmed & Santanu S. Dey & Myun Seok Cheon, 2017. "Relaxations and discretizations for the pooling problem," Journal of Global Optimization, Springer, vol. 67(3), pages 631-669, March.
    4. Daniel de Wolf & Stéphane Auray & Yves Smeers, 2015. "Using Column Generation To Solve A Coal Blending Problem," Post-Print halshs-02396784, HAL.
    5. Nats Esquejo & Kevin Miller & Kevin Norwood & Ivan Oliveira & Rob Pratt & Ming Zhao, 2015. "Statistical and Optimization Techniques for Laundry Portfolio Optimization at Procter & Gamble," Interfaces, INFORMS, vol. 45(5), pages 444-461, October.
    6. Boukouvala, Fani & Misener, Ruth & Floudas, Christodoulos A., 2016. "Global optimization advances in Mixed-Integer Nonlinear Programming, MINLP, and Constrained Derivative-Free Optimization, CDFO," European Journal of Operational Research, Elsevier, vol. 252(3), pages 701-727.
    7. Vidal, Carlos J. & Goetschalckx, Marc, 2001. "A global supply chain model with transfer pricing and transportation cost allocation," European Journal of Operational Research, Elsevier, vol. 129(1), pages 134-158, February.
    8. Yifu Chen & Christos T. Maravelias, 2020. "Preprocessing algorithm and tightening constraints for multiperiod blend scheduling: cost minimization," Journal of Global Optimization, Springer, vol. 77(3), pages 603-625, July.
    9. N.V. Thoai, 2002. "Convergence and Application of a Decomposition Method Using Duality Bounds for Nonconvex Global Optimization," Journal of Optimization Theory and Applications, Springer, vol. 113(1), pages 165-193, April.
    10. Jie Wu & Zhixin Chen & Xiang Ji, 2020. "Sustainable trade promotion decisions under demand disruption in manufacturer-retailer supply chains," Annals of Operations Research, Springer, vol. 290(1), pages 115-143, July.
    11. Beck, Yasmine & Ljubić, Ivana & Schmidt, Martin, 2023. "A survey on bilevel optimization under uncertainty," European Journal of Operational Research, Elsevier, vol. 311(2), pages 401-426.
    12. Saeide Bigdellou & Shirin Aslani & Mohammad Modarres, 2023. "Sustainable Trade Promotions in Case of Negative Demand Disruption in E-Commerce," Sustainability, MDPI, vol. 15(3), pages 1-17, January.
    13. Al-Khayyal, Faiz & Hwang, Seung-June, 2007. "Inventory constrained maritime routing and scheduling for multi-commodity liquid bulk, Part I: Applications and model," European Journal of Operational Research, Elsevier, vol. 176(1), pages 106-130, January.
    14. Mohammed Alfaki & Dag Haugland, 2013. "Strong formulations for the pooling problem," Journal of Global Optimization, Springer, vol. 56(3), pages 897-916, July.
    15. Ata Allah Taleizadeh & Zahedeh Cheraghi & Leopoldo Eduardo Cárdenas-Barrón & Mahsa Noori-Daryan, 2021. "Studying the Effect of Noise on Pricing and Marketing Decisions of New Products under Co-op Advertising Strategy in Supply Chains: Game Theoretical Approaches," Mathematics, MDPI, vol. 9(11), pages 1-26, May.
    16. Malekian, Yaser & Rasti-Barzoki, Morteza, 2019. "A game theoretic approach to coordinate price promotion and advertising policies with reference price effects in a two-echelon supply chain," Journal of Retailing and Consumer Services, Elsevier, vol. 51(C), pages 114-128.
    17. Shuihua Han & Yufang Fu & Bin Cao & Zongwei Luo, 2018. "Pricing and bargaining strategy of e-retail under hybrid operational patterns," Annals of Operations Research, Springer, vol. 270(1), pages 179-200, November.
    18. Guajardo, Mario & Kylinger, Martin & Rönnqvist, Mikael, 2013. "Speciality oils supply chain optimization: From a decoupled to an integrated planning approach," European Journal of Operational Research, Elsevier, vol. 229(2), pages 540-551.
    19. Xiaotong Fu & Shuai Yan & Zhifu Chen & Xiaoyu Xu & Zhuoxiang Ren, 2024. "A Practical Hybrid Hysteresis Model for Calculating Iron Core Losses in Soft Magnetic Materials," Energies, MDPI, vol. 17(10), pages 1-14, May.
    20. Gaurav Singh & Rodolfo García-Flores & Andreas Ernst & Palitha Welgama & Meimei Zhang & Kerry Munday, 2014. "Medium-Term Rail Scheduling for an Iron Ore Mining Company," Interfaces, INFORMS, vol. 44(2), pages 222-240, 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:spr:joheur:v:22:y:2016:i:2:d:10.1007_s10732-015-9304-3. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.