Skip to main content
SpringerLink
Log in

A generalized global optimization formulation of the pooling problem with processing facilities and composite quality constraints

  • Original Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

We present a generalized formulation of the pooling problem. Our formulation is different from the standard formulations in explicitly modeling component flows. Modeling the physical components directly, allows easy inclusion of processing facilities that may alter the flow composition. It also allows adding composite quality constraints that cannot be added directly as quality parameters as they do not blend linearly. We provide new test instances motivated by natural gas transport problems at the Norwegian Continental Shelf and give computational results. We show examples of nonlinear composite constraints on quality attributes and give computational results on the effect of adding such constraints to the new set of test instances. The increased flexibility of our formulation comes at the cost of less tight constraints and a performance penalty on existing test cases in literature. The advantage is that it can solve the more general test cases described above. We use GAMS implementations of the various formulations and solve the problems with BARON. We compare the performance of our bilinear formulation in BARON with discretizations solved as a Mixed Integer Linear Program using CPLEX. The discretized versions do not generally perform as well as the continuous model; however, they have better worst-case behavior on the new test cases.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  • Adhya N, Tawarmalani M, Sahinidis N (1999) A Lagrangian approach to the pooling problem. Ind Eng Chem Res 38(5):1956–1972

    Article  Google Scholar 

  • Alfaki M, Haugland D (2013a) A multi-commodity flow formulation for the generalized pooling problem. J Global Optim 56:917–937

  • Alfaki M, Haugland D (2013b) Strong formulations for the pooling problem. J Global Optim 56(3):897–916. doi:10.1007/s10898-012-9875-6

  • Androulakis I, Maranas C, Floudas C (1995) \(\alpha \)bb: a global optimization method for general constrained nonconvex problems. J Global Optim 7(4):337–363

    Article  Google Scholar 

  • Audet C, Hansen P, Jaumard B, Savard G (2000) A branch and cut algorithm for nonconvex quadratically constrained quadratic programming. Math Program 87(1):131–152

    Article  Google Scholar 

  • Audet C, Brimberg J, Hansen P, Le Digabel S, Mladenović N (2004) Pooling problem: alternate formulations and solution methods. Manag Sci 50:761–776

    Article  Google Scholar 

  • Baker T, Lasdon L (1985) Successive linear programming at Exxon. Manag Sci 31:264–274

    Article  Google Scholar 

  • Ben-Tal A, Eiger G, Gershovitz V (1994) Global minimization by reducing the duality gap. Math Program 63(1):193–212

    Article  Google Scholar 

  • Castro PM, Teles JP (2013) Comparison of global optimization algorithms for the design of water-using networks. Comput Chem Eng 52:249–261

    Article  Google Scholar 

  • Dey SS, Gupte A (2015) Analysis of MILP techniques for the pooling problem. Oper Res 62(2):412–427

    Article  Google Scholar 

  • Fodstad M, Midthun KT, Tomasgard A (2015) Adding flexibility in a natural gas transportation network using interruptible transportation services. Eur J Oper Res 243(2):647–657

  • Foulds LR, Haugland D, Jørnsten K (1992) A bilinear approach to the pooling problem. Optimization 24:165–180

    Article  Google Scholar 

  • Frimannslund L, Haugland D (2009) Parallel solution of the pooling problem with application to the cell broadband engine architecture. In: International conference on computers and industrial engineering, 2009. CIE 2009. IEEE, pp 354–359

  • Gounaris C, Misener R, Floudas C (2009) Computational comparison of piecewise-linear relaxations for pooling problems. Ind Eng Chem Res 48(12):5742–5766

    Article  Google Scholar 

  • Gupte A (2012) Mixed integer bilinear programming with applications to the pooling problem. Ph.D. thesis, Georgia Institute of Technology, Atlanta. https://smartech.gatech.edu/handle/1853/45761. Accessed 14 Sept 2015

  • Gupte A, Ahmed S, Dey SS, CheonMS (2012) Pooling problem. http://www.optimization-online.org/DB_FILE/2012/10/3658. Accessed 14 Sept 2015

  • Haugland D (2010) An overview of models and solution methods for pooling problems. In: Energy, natural resources and environmental economics, pp 459–469

  • Haverly C (1978) Studies of the behavior of recursion for the pooling problem. ACM SIGMAP Bull 25:19–28

    Article  Google Scholar 

  • Haverly C (1979) Behavior of recursion model–more studies. ACM SIGMAP Bull 26:22–28

    Article  Google Scholar 

  • Haverly C (1980) Recursion model behavior: more studies. ACM SIGMAP Bull 28:39–41

    Article  Google Scholar 

  • Hellemo L, Midthun K, Tomasgard A, Werner A (2012) Multi-stage stochastic programming for natural gas infrastructure design with a production perspective. In: Ziemba WT, Wallace SW, Gassman HI (eds) Stochastic programming—applications in finance, energy, planning and logistics, World Scientific series in finance, vol 4. World Scientific, Singapore, pp 259–288

    Google Scholar 

  • Hellemo L, Midthun K, Tomasgard A, Werner A (2012) Natural gas infrastructure design with an operational perspective. Energy Proc 26:67–73

    Article  Google Scholar 

  • Hornemann JAT (1998) Method for determining the calorific value of a gas and/or the wobbe index of a natural gas. US Patent 5,807,749

  • Kocis G, Grossmann I (1989) A modelling and decomposition strategy for the MINLP optimization of process flowsheets. Comput Chem Eng 13(7):797–819

    Article  Google Scholar 

  • Lee S, Grossmann I (2003) Global optimization of nonlinear generalized disjunctive programming with bilinear equality constraints: applications to process networks. Comput Chem Eng 27(11):1557–1575

    Article  Google Scholar 

  • Li X, Armagan E, Tomasgard A, Barton PI (2011a) Stochastic pooling problem for natural gas production network design and operation under uncertainty. AIChE J 57:2120–2135

  • Li X, Tomasgard A, Barton P (2011b) Decomposition strategy for the stochastic pooling problem. J Global Optim 54:765–790

  • Lodwick W (1992) Preprocessing nonlinear functional constraints with applications to the pooling problem. ORSA J Comput 4(2):119–131

    Article  Google Scholar 

  • Meyer C, Floudas C (2006) Global optimization of a combinatorially complex generalized pooling problem. AIChE J 52(3):1027–1037

    Article  Google Scholar 

  • Misener R, Floudas C (2009) Advances for the pooling problem: modeling, global optimization, and computational studies. Appl Comput Math 8(1):3–22

    Google Scholar 

  • Misener R, Thompson JP, Floudas CA (2011) Apogee: global optimization of standard, generalized, and extended pooling problems via linear and logarithmic partitioning schemes. Comput Chem Eng 35(5):876–892

    Article  Google Scholar 

  • Quesada I, Grossmann I (1995) Global optimization of bilinear process networks with multicomponent flows. Comput Chem Eng 19(12):1219–1242

    Article  Google Scholar 

  • Rømo F, Tomasgard A, Hellemo L, Fodstad M, Eidesen B, Pedersen B (2009) Optimizing the Norwegian natural gas production and transport. Interfaces 39(1):46–56

    Article  Google Scholar 

  • Selot A, Kuok L, Robinson M, Mason T, Barton P (2008) A short-term operational planning model for natural gas production systems. AIChE J 54(2):495–515

    Article  Google Scholar 

  • Tawarmalani M, Sahinidis NV (2002) Convexification and global optimization in continuous and mixed-integer nonlinear programming. Kluwer Academic Publishers, Norwell

    Book  Google Scholar 

  • Teles JP, Castro PM, Matos HA (2012) Global optimization of water networks design using multiparametric disaggregation. Comput Chem Eng 40:132–147

    Article  Google Scholar 

  • The Norwegian Ministry of Petroleum and Energy and The Norwegian Petroleum Directorate (2012) Facts 2012—The Norwegian petroleum sector. http://www.npd.no/en/Publications/Facts/Facts-2012/

  • Tomasgard A, Rømo F, Fodstad M, Midthun K (2007) Optimization models for the natural gas value chain. In: Hasle G, Lie KA, Quak E (eds) Geometric modelling, numerical simulation and optimization. Springer, Berlin, pp 521–558

    Chapter  Google Scholar 

  • UK Government (1996) Gas Safety (Management) Regulations. Statutory Instruments 1996 No. 551

  • Ulstein NL (2000) Short term planning of gas production (in Norwegian). Masters thesis, Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology

  • Ulstein NL, Nygreen B, Sagli JR (2007) Tactical planning of offshore petroleum production. Eur J Oper Res 176(1):550–564

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department for Industrial Economics and Technology Management, Norwegian University of Science and Technology, Alfred Getz veg 3, 7491, Trondheim, Norway

    Lars Hellemo & Asgeir Tomasgard

Authors
  1. Lars Hellemo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Asgeir Tomasgard
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lars Hellemo.

Appendices

Appendix 1: Software and hardware specifications

All numerical tests were performed using GAMS version 23.7.2 with BARON using CPLEX in combination with Conopt or GAMS in combination with CPLEX for MILPs on an HP bl685c G7 4x AMD Opteron 6274, 16 core, 2.2 GHz with 128 Gb memory running Linux 2.6.32-358 (Rocks 6.1.1).

Appendix 2: Tables of numerical results

See Tables 3, 4, 5, 6, 7, 8, 9 and 10.

Table 3 NCS instances (no processing)
Full size table
Table 4 Full results from NCS processing cases
Full size table
Table 5 Full results from NCS processing cases with composite constraints using smodel
Full size table
Table 6 Full results from NCS benchmark
Full size table
Table 7 Full results from NCS benchmarks with processing facility
Full size table
Table 8 Full results from NCS benchmarks with processing facility and composite constraints
Full size table
Table 9 Gap with time limit 1 h for cases from the literature (GPP)
Full size table
Table 10 Full results from benchmark
Full size table

Table 10 shows the full results from comparing several formulations for the NCS test instances without processing facilities or composite quality constraints. Note that the number of binary variables for formulation S-D1 is shown as 0. This is because SOS1 variables are not reported as binary variables by GAMS.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hellemo, L., Tomasgard, A. A generalized global optimization formulation of the pooling problem with processing facilities and composite quality constraints. TOP 24, 409–444 (2016). https://doi.org/10.1007/s11750-015-0403-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-015-0403-y

Keywords

Mathematics Subject Classification

Search

Navigation