Huang, Wei (2019)
Optimal Operation of Water Supply Networks by Mixed Integer Nonlinear Programming and Algebraic Methods.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication
Abstract
In this thesis we are dealing with the operative planning of water supply networks. The task of an operative planning is to create a pump and valve configuration such that the water requirement from consumers is fulfilled with necessary quality. An optimal operation corresponds to a configuration that minimizes the operation cost as well as potential water procurement cost.
There are different ways to handle this problem. We solve it as an optimization problem using mathematical programming. On the one hand, the network problem contains some discrete variables, for example, the pump or valve status; on the other hand, nonlinearities and nonconvexities from physical behaviors make the mathematical model extremely difficult. We model the optimization problem as a mixed-integer nonlinear program (MINLP).
We choose MINLP solver SCIP, developed mainly at Zuse Insitute Berlin. We use two real-world instances provided by industrial partner Siemens and a further real-world instance obtained from the Department of Hydraulic Engineering of Tsinghua University.
In this thesis, we first show that our solver SCIP is able to solve the optimal operation problem to global optimality in a fixed point of time. However, for a daily operation which contains 24 coupled time periods (hours), "good" solutions are usually found rapidly, but the dual gap cannot verify the solution quality.
In a further chapter we show that a class of subnetworks which only contains pipes and consumers, can be simplified and the original nonlinear constraints can be replaced by few (or single) nonlinear constraints, without changing the feasible region. Computation shows that this simplification makes the MINLP easier to solve.
The algorithm which solves our nonconvex MINLP generates at every iteration a convex relaxation of the feasible region. A lot of theories and experiments showed that tighter convex relaxation is quite relevant for the branch-and-bound approach.
In the objective of our model, we have bivariate polynomial term with degree 3. Based on the default construction of convex relaxation, we want to find additional linear constrains ("valid cuts") to make the relaxation tighter. We investigate the graph of general polynomial functions over a polytope in general dimension and develop theory to describe the convex hull of the graph and to find halfspaces which contain the convex hull. After that we define "tight" halfspaces which denote the "efficient" halfspaces when forming the convex hull. For bivariate polynomial functions with degree 3, algorithms are designed to find such tight halfspaces. After adding these halfspaces (linear constraints) into the MINLP, computation shows that both primal and dual bound are definitively improved within the same time limit.
Item Type: | Ph.D. Thesis | ||||
---|---|---|---|---|---|
Erschienen: | 2019 | ||||
Creators: | Huang, Wei | ||||
Type of entry: | Primary publication | ||||
Title: | Optimal Operation of Water Supply Networks by Mixed Integer Nonlinear Programming and Algebraic Methods | ||||
Language: | English | ||||
Referees: | Pfetsch, Prof. Dr. Marc E. ; Hemmecke, PD Dr. Raymond | ||||
Date: | 2019 | ||||
Place of Publication: | Darmstadt | ||||
Publisher: | tuprints | ||||
Refereed: | 16 April 2019 | ||||
URL / URN: | https://tuprints.ulb.tu-darmstadt.de/8657 | ||||
Abstract: | In this thesis we are dealing with the operative planning of water supply networks. The task of an operative planning is to create a pump and valve configuration such that the water requirement from consumers is fulfilled with necessary quality. An optimal operation corresponds to a configuration that minimizes the operation cost as well as potential water procurement cost. There are different ways to handle this problem. We solve it as an optimization problem using mathematical programming. On the one hand, the network problem contains some discrete variables, for example, the pump or valve status; on the other hand, nonlinearities and nonconvexities from physical behaviors make the mathematical model extremely difficult. We model the optimization problem as a mixed-integer nonlinear program (MINLP). We choose MINLP solver SCIP, developed mainly at Zuse Insitute Berlin. We use two real-world instances provided by industrial partner Siemens and a further real-world instance obtained from the Department of Hydraulic Engineering of Tsinghua University. In this thesis, we first show that our solver SCIP is able to solve the optimal operation problem to global optimality in a fixed point of time. However, for a daily operation which contains 24 coupled time periods (hours), "good" solutions are usually found rapidly, but the dual gap cannot verify the solution quality. In a further chapter we show that a class of subnetworks which only contains pipes and consumers, can be simplified and the original nonlinear constraints can be replaced by few (or single) nonlinear constraints, without changing the feasible region. Computation shows that this simplification makes the MINLP easier to solve. The algorithm which solves our nonconvex MINLP generates at every iteration a convex relaxation of the feasible region. A lot of theories and experiments showed that tighter convex relaxation is quite relevant for the branch-and-bound approach. In the objective of our model, we have bivariate polynomial term with degree 3. Based on the default construction of convex relaxation, we want to find additional linear constrains ("valid cuts") to make the relaxation tighter. We investigate the graph of general polynomial functions over a polytope in general dimension and develop theory to describe the convex hull of the graph and to find halfspaces which contain the convex hull. After that we define "tight" halfspaces which denote the "efficient" halfspaces when forming the convex hull. For bivariate polynomial functions with degree 3, algorithms are designed to find such tight halfspaces. After adding these halfspaces (linear constraints) into the MINLP, computation shows that both primal and dual bound are definitively improved within the same time limit. |
||||
Alternative Abstract: |
|
||||
URN: | urn:nbn:de:tuda-tuprints-86575 | ||||
Classification DDC: | 500 Science and mathematics > 510 Mathematics | ||||
Divisions: | 04 Department of Mathematics 04 Department of Mathematics > Optimization 04 Department of Mathematics > Optimization > Discrete Optimization |
||||
Date Deposited: | 09 Jun 2019 19:55 | ||||
Last Modified: | 09 Jun 2019 19:55 | ||||
PPN: | |||||
Referees: | Pfetsch, Prof. Dr. Marc E. ; Hemmecke, PD Dr. Raymond | ||||
Refereed / Verteidigung / mdl. Prüfung: | 16 April 2019 | ||||
Export: | |||||
Suche nach Titel in: | TUfind oder in Google |
Send an inquiry |
Options (only for editors)
Show editorial Details |