Solving MINLPs on Loosely-Coupled Networks with Applications in Water and Gas Network Optimization
Published on 18. September 2013
Book
Paperback/Softback
196 pages
978-3-8439-1176-4 (ISBN)
Description
Mixed-integer nonlinear programming (MINLP) problems are one of the most flexible ways for modeling in optimization and their solution is, especially for real-world instances, very challenging. We aim at global solutions for two real-world applications from water and gas network optimization leading to large-scale nonconvex MINLP problems. An abstract view of both problems reveals that only low dimensional nonlinear relationships are involved and that their mathematical models are based on some underlying network structure. Thus, we initially investigate two solution approaches exploiting these properties in a generic setting of MINLP.
Problems involving only low dimensional nonlinearities are applicable for piecewise linear approximation and general-purpose mixed-integer linear programming (MIP) techniques. A suitable construction of the approximations even leads to rigorous MIP-based relaxations. Practically efficient MIP-relaxations for MINLP problems require many essential steps, such as problem representation and preprocessing, construction of piecewise linear approximations, and modeling of piecewise linear approximations. We use the minimax approximation theory to construct optimal piecewise linear approximations for univariate continuous functions. Theoretical and algorithmic aspects for univariate piecewise approximations with a minimum error or with a minimum number of pieces are presented.
MIP-relaxations might suffer from the curse of dimensionality, since they involve many auxiliary binary variables. To tackle larger problems, we investigate a second approach based on the underlying graph structure. We present a generic framework, which allows the derivation of a Lagrangian relaxation from a given graph decomposition. The evaluation of the Lagrangian function is based on the global optimization of smaller independent MINLP subproblems. An integration into a branch-and-bound framework eventually leads an optimum solution of the MINLP. We propose a graph decomposition into biconnected and triconnected components from our experience with gas and water network optimization.
Subsequently, we develop an MINLP model for the operational management of dynamic water supply networks involving physical and practical issues. Moreover, we summarize a stationary optimization model for gas transport networks. Finally, we present numerical results for our solution approaches with real-world instances from our industry partners for both applications.
Problems involving only low dimensional nonlinearities are applicable for piecewise linear approximation and general-purpose mixed-integer linear programming (MIP) techniques. A suitable construction of the approximations even leads to rigorous MIP-based relaxations. Practically efficient MIP-relaxations for MINLP problems require many essential steps, such as problem representation and preprocessing, construction of piecewise linear approximations, and modeling of piecewise linear approximations. We use the minimax approximation theory to construct optimal piecewise linear approximations for univariate continuous functions. Theoretical and algorithmic aspects for univariate piecewise approximations with a minimum error or with a minimum number of pieces are presented.
MIP-relaxations might suffer from the curse of dimensionality, since they involve many auxiliary binary variables. To tackle larger problems, we investigate a second approach based on the underlying graph structure. We present a generic framework, which allows the derivation of a Lagrangian relaxation from a given graph decomposition. The evaluation of the Lagrangian function is based on the global optimization of smaller independent MINLP subproblems. An integration into a branch-and-bound framework eventually leads an optimum solution of the MINLP. We propose a graph decomposition into biconnected and triconnected components from our experience with gas and water network optimization.
Subsequently, we develop an MINLP model for the operational management of dynamic water supply networks involving physical and practical issues. Moreover, we summarize a stationary optimization model for gas transport networks. Finally, we present numerical results for our solution approaches with real-world instances from our industry partners for both applications.