Mixed integer models for the stationary case of gas network optimization. (English) Zbl 1085.90035

Summary: A gas network basically consists of a set of compressors and valves that are connected by pipes. The problem of gas network optimization deals with the question of how to optimize the flow of the gas and to use the compressors cost-efficiently such that all demands of the gas network are satisfied. This problem leads to a complex mixed integer nonlinear optimization problem. We describe techniques for a piece-wise linear approximation of the nonlinearities in this model resulting in a large mixed integer linear program. We study sub-polyhedra linking these piece-wise linear approximations and show that the number of vertices is computationally tractable yielding exact separation algorithms. Suitable branching strategies complementing the separation algorithms are also presented. Our computational results demonstrate the success of this approach.


90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut


Full Text: DOI


[1] Balas, E., Ceria, S., Cornuéjols, G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Mathematical Programming 58, 295–324 (1993) · Zbl 0796.90041
[2] Beale, E.M.L.: Branch and bound methods for mathematical programming systems. Annals of Discrete Mathematics 5, 201–219 (1979) · Zbl 0405.90049
[3] Beale, E.M.L., Forrest, J.J.H.: Global optimization using special ordered sets. Mathematical Programming 10, 52–69 (1976) · Zbl 0331.90056
[4] Beale, E.L.M., Tomlin, J.A.: Special facilities in a general mathematical programming system for nonconvex problems using ordered sets of variables. In: Lawrence J. (ed) Proceedings of the fifth international conference on operations research. Tavistock Publications, London, 1970, pp 447–454
[5] Christof, T., Löbel, A.: PORTA: POlyhedron Representation Transformation Algorithm, Version 1.3. Konrad-Zuse-Zentrum für Informationstechnik Berlin, 2000
[6] Dantzig, G.B.: Linear programming and extensions. Princeton University Press, 1963 · Zbl 0108.33103
[7] de Farias, Jr., I.R., Johnson, E.L., Nemhauser, G.L.: A generalized assignment problem woth special ordered sets; a polyhedral approach. Mathematical Programming 89, 187–203 (2000) · Zbl 1060.90081
[8] de Farias, Jr., I.R., Johnson, E.L., Nemhauser, G.L.: Branch-and-Cut for combinatorial optimization problems without auxiliary binary variables. The Knowledge Engineering Review 16, 25–39 (2001) · Zbl 1060.90082
[9] Ehrhardt, K., Steinbach, M.: Nonlinear optimization in gas networks. In: Bock, H.G., Kostina, E., Phu, H.X., Ranacher, R. (eds) Modeling simulation and optimization of complex processes. Berlin - Heidelberg - New York, Springer, pp 139-148, 2005 · Zbl 1069.90014
[10] Erdmann, B., Lang, J., Roitzsch, R.: KARDOS User’s Guide. Technical Report ZR 02-42, Konrad-Zuse-Zentrum Berlin, 2002
[11] Gopal, V.N.: Techniques to optimize fuel and compressor combination selection. In: American Gas Association Transmission Conference, 1979
[12] ILOG CPLEX Division, 889 Alder Avenue, Suite 200, Incline Village, NV 89451, USA. Using the CPLEX Callable Library, 2002. Information available at http://www.cplex.com
[13] Jenicek, T.: Steady-state optimization of gas transport. In: Proceedings of the 2nd international workshop SIMONE on innovative approaches to modelling and optimal control of large scale pipeline networks, September 1993
[14] Hall, Jr. M.: Combinatorial theory. Blaisdell Publishing Co. Ginn and Co., Waltham, Mass.-Toronto, Ont.-London, 1967 · Zbl 0196.02401
[15] Keha, A.B., de Farias Jr. I.R., Nemhauser, G.L.: Models for representing piecewise linear cost functions. Operations Research Letters 32, 44–48 (2004) · Zbl 1056.90107
[16] Králik, J.: Compressor stations in SIMONE. In: Proceedings of the 2nd International Workshop SIMONE on Innovative Approaches to Modelling and Optimal Control of Large Scale Pipeline Networks, 1993
[17] Lee, J., Wilson, D.: Polyhedral methods for piecewise-linear functions I: the lambda method. Discrete Applied Mathematics 108, 269–285 (2001) · Zbl 1002.90038
[18] Markowitz, H.M., Manne, A.S.: On the solution of discrete programming problems. Econometrica 25, 84–110 (1957) · Zbl 0078.34005
[19] Möller, M.: Mixed integer models for the optimisation of gas networks in the stationary case. PhD thesis, Darmstadt University of Technology, 2004 · Zbl 1069.90120
[20] Nemhauser, G.L., Wolsey, L.A.: Integer and combinatorial optimization. Wiley, 1988 · Zbl 0652.90067
[21] Padberg, M.: Approximating separable nonlinear functions via mixed zero-one programs. Operations Research Letters 27, 1–5 (2000) · Zbl 0960.90065
[22] Pratt, K.F., Wilson, J.G.: Optimization of operation of gas transmission systems. Transactions of the Institute of Measurement and Control 6(4), 261–269 (1984)
[23] Carter, R.: Pipeline optimization: Dynamic programming after 30 years. In: Pipeline simulation interest group,URL:// www.psig.com, 1998
[24] Ruhrgas, A.G.: http://www.ruhrgas.com, 2003
[25] Schrijver, A.: Combinatorial optimization. polyhedra and efficiency (3 volumes). Springer, 2003 · Zbl 1041.90001
[26] Sekirnjak, E.: Mixed integer optimization for gas transmission and distribution systems. INFORMS Meeting, Seattle, October 1998, Lecture notes
[27] Sekirnjak, E.: Transiente technische optimierung (TTO-Prototyp). PSI Berlin, 1999. Technical Report
[28] Smeers, Y., De Wolf, D.: The gas transmission problem solved by an extension of the simplex algorithm. Management Science 46, 1454–1465 (2000) · Zbl 1232.90355
[29] Tomlin, J.A.: A suggested extension of special ordered sets to non-separable non-convex programming problems. Annals of Discrete Mathematics 11, 359–370 (1981) · Zbl 0469.90068
[30] van Oostvoorn, F.: European gas market developments - oportunities and threats-. In: Supplement to the IAEE/GEE Conference “Energy Markets What’s New?” pp 29–44, Berlin, 9-10 September 1998
[31] Vostrý, Z.: Transient optimization of gas transport and distribution. In: Proceedings of the 2nd International Workshop SIMONE on Innovative Approaches to Modelling and Optimal Control of Large Scale Pipeline Networks, 1993
[32] Williams, H.P.: Model building in mathematical programming. Wiley, 1990 · Zbl 0709.90072
[33] Wilson, D.: Polyhedral methods for piecewise-linear functions. PhD thesis, University of Kentucky 1998. Thesis only availabe via www.umi.com
[34] Wright, S., Somani, M., Ditzel, C.: Compressor station optimization. In: Pipeline Simulation Interest Group, Denver, Colorado, October 1998
[35] Jiří Záworka.: Project SIMONE - Achievements and running development. Institute of Information Theory and Automation, Czech Republik
[36] Zimmer, H.I.: Calculating optimum pipeline operations. American Gas Association Transmission Conference, 1975
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.