IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v50y2004i6p761-776.html
   My bibliography  Save this article

Pooling Problem: Alternate Formulations and Solution Methods

Author

Listed:
  • Charles Audet

    (GERAD and École Polytechnique de Montréal, C.P. 6079, Succursalle Centre-ville, Montréal, Québec, Canada H3C 3A7)

  • Jack Brimberg

    (School of Business Administration, University of Prince Edward Island, Charlottetown, Prince Edward Island, Canada C1A 4P3)

  • Pierre Hansen

    (GERAD and École des Hautes Études Commerciales, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec, Canada H3T 2A7)

  • Sébastien Le Digabel

    (GERAD and École des Hautes Études Commerciales, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec, Canada H3T 2A7)

  • Nenad Mladenovi'{c}

    (GERAD and École des Hautes Études Commerciales, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec, Canada H3T 2A7)

Abstract

The pooling problem, which is fundamental to the petroleum industry, describes a situation in which products possessing different attribute qualities are mixed in a series of pools in such a way that the attribute qualities of the blended products of the end pools must satisfy given requirements. It is well known that the pooling problem can be modeled through bilinear and nonconvex quadratic programming. In this paper, we investigate how best to apply a new branch-and-cut quadratic programming algorithm to solve the pooling problem. To this effect, we consider two standard models: One is based primarily on flow variables, and the other relies on the proportion of flows entering pools. A hybrid of these two models is proposed for general pooling problems. Comparison of the computational properties of flow and proportion models is made on several problem instances taken from the literature. Moreover, a simple alternating procedure and a variable neighborhood search heuristic are developed to solve large instances and compared with the well-known method of successive linear programming. Solution of difficult test problems from the literature is substantially accelerated, and larger ones are solved exactly or approximately.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:ormnsc:v:50:y:2004:i:6:p:761-776
    DOI: 10.1287/mnsc.1030.0207
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.1030.0207
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.1030.0207?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. M. Dür & R. Horst, 1997. "Lagrange Duality and Partitioning Techniques in Nonconvex Global Optimization," Journal of Optimization Theory and Applications, Springer, vol. 95(2), pages 347-369, November.
    2. F. Palacios-Gomez & L. Lasdon & M. Engquist, 1982. "Nonlinear Optimization by Successive Linear Programming," Management Science, INFORMS, vol. 28(10), pages 1106-1120, October.
    3. Weldon A. Lodwick, 1992. "Preprocessing Nonlinear Functional Constraints with Applications to the Pooling Problem," INFORMS Journal on Computing, INFORMS, vol. 4(2), pages 119-131, May.
    4. R. E. Griffith & R. A. Stewart, 1961. "A Nonlinear Programming Technique for the Optimization of Continuous Processing Systems," Management Science, INFORMS, vol. 7(4), pages 379-392, July.
    5. 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.
    6. Faiz A. Al-Khayyal & James E. Falk, 1983. "Jointly Constrained Biconvex Programming," Mathematics of Operations Research, INFORMS, vol. 8(2), pages 273-286, May.
    7. Thomas E. Baker & Leon S. Lasdon, 1985. "Successive Linear Programming at Exxon," Management Science, INFORMS, vol. 31(3), pages 264-274, March.
    8. Calvin W. DeWitt & Leon S. Lasdon & Allan D. Waren & Donald A. Brenner & Simon A. Melhem, 1989. "OMEGA: An Improved Gasoline Blending System for Texaco," Interfaces, INFORMS, vol. 19(1), pages 85-101, February.
    9. Jianzhong Zhang & Nae-Heon Kim & L. Lasdon, 1985. "An Improved Successive Linear Programming Algorithm," Management Science, INFORMS, vol. 31(10), pages 1312-1331, October.
    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. Mohammed Alfaki & Dag Haugland, 2014. "A cost minimization heuristic for the pooling problem," Annals of Operations Research, Springer, vol. 222(1), pages 73-87, November.
    2. 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.
    3. Sarker, Ruhul A. & Gunn, Eldon A., 1997. "A simple SLP algorithm for solving a class of nonlinear programs," European Journal of Operational Research, Elsevier, vol. 101(1), pages 140-154, August.
    4. Natashia Boland & Thomas Kalinowski & Fabian Rigterink, 2016. "New multi-commodity flow formulations for the pooling problem," Journal of Global Optimization, Springer, vol. 66(4), pages 669-710, December.
    5. Chen, Ruoran & Deng, Tianhu & Huang, Simin & Qin, Ruwen, 2015. "Optimal crude oil procurement under fluctuating price in an oil refinery," European Journal of Operational Research, Elsevier, vol. 245(2), pages 438-445.
    6. Ted Kutz & Mark Davis & Robert Creek & Nick Kenaston & Craig Stenstrom & Margery Connor, 2014. "Optimizing Chevron’s Refineries," Interfaces, INFORMS, vol. 44(1), pages 39-54, February.
    7. Radu Baltean-Lugojan & Ruth Misener, 2018. "Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness," Journal of Global Optimization, Springer, vol. 71(4), pages 655-690, August.
    8. Mohammed Alfaki & Dag Haugland, 2013. "Strong formulations for the pooling problem," Journal of Global Optimization, Springer, vol. 56(3), pages 897-916, July.
    9. 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.
    10. Cheng, Xianliang & Feng, Suzhen & Zheng, Hao & Wang, Jinwen & Liu, Shuangquan, 2022. "A hierarchical model in short-term hydro scheduling with unit commitment and head-dependency," Energy, Elsevier, vol. 251(C).
    11. N. V. Thoai, 2000. "Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints," Journal of Optimization Theory and Applications, Springer, vol. 107(2), pages 331-354, November.
    12. Hong, Sung-Pil & Kim, Taegyoon & Lee, Subin, 2019. "A precision pump schedule optimization for the water supply networks with small buffers," Omega, Elsevier, vol. 82(C), pages 24-37.
    13. Draman, Murat & Kuban Altinel, I & Bajgoric, Nijaz & Tamer Unal, Ali & Birgoren, Burak, 2002. "A clone-based graphical modeler and mathematical model generator for optimal production planning in process industries," European Journal of Operational Research, Elsevier, vol. 137(3), pages 483-496, March.
    14. Lars Hellemo & Asgeir Tomasgard, 2016. "A generalized global optimization formulation of the pooling problem with processing facilities and composite quality constraints," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 24(2), pages 409-444, July.
    15. Daniel De Wolf & Yves Smeers, 2000. "The Gas Transmission Problem Solved by an Extension of the Simplex Algorithm," Management Science, INFORMS, vol. 46(11), pages 1454-1465, November.
    16. Hagspiel, S. & Jägemann, C. & Lindenberger, D. & Brown, T. & Cherevatskiy, S. & Tröster, E., 2014. "Cost-optimal power system extension under flow-based market coupling," Energy, Elsevier, vol. 66(C), pages 654-666.
    17. 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.
    18. Hagspiel, Simeon & Jägemann, Cosima & Lindenberger, Dietmar & Brown, Tom & Cherevatskiy, Stanislav & Tröster, Eckehard, 2013. "Cost-Optimal Power System Extension under Flow-Based Market Coupling," EWI Working Papers 2013-9, Energiewirtschaftliches Institut an der Universitaet zu Koeln (EWI).
    19. Dag Haugland & Eligius M. T. Hendrix, 2016. "Pooling Problems with Polynomial-Time Algorithms," Journal of Optimization Theory and Applications, Springer, vol. 170(2), pages 591-615, August.
    20. 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.

    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:ormnsc:v:50:y:2004:i:6:p:761-776. 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.