How to Understand a Class of Network Optimization with Automatic Differentiation
by
Mohamed Masmoudi
MIP, UMR 5640, UFR MIG, Université Paul Sabatier Toulouse 3, 118 route de Narbonne, 31062 Toulouse cedex 4, France
Coauthors: Miloslav Grundmann (Université Paul Sabatier Toulouse 3, France), Sophie Jan (Université Paul Sabatier Toulouse 3, France)

This talk deals with network optimization, which seems to be of a great interest at the moment, in particular for petroleum engineers. In this domain, the network represent the gathering and transportation system of petroleum or gas from a lot of production wells (say n) towards few exit points (say m) at the refinery. The flow of each well must be adjusted in order to have the required quantities and qualities at the exit points. This problem seems to be difficult and we want to show how the automatic differentiation can help us to submit an efficient method of resolution.

Since each of the n production wells has a given pressure, an estimation of the pressure at the bottom of each well (BHP) can be made, that allows to propagate all the flows from the wells towards the exit points, using the conservation law of the flows. Then, since the pressure at the exit points is known, the pressures can be propagated from the exit points towards the wells. After this calculation, one has two values for the BHP : an estimated one and a calculated one. Let us denote by F the difference between these two values. The network simulation consists then in the search of n estimated BHPs such that F is zero. In order to apply Newton's method to this problem, we need to compute the Jacobian DF of F and to be able to solve DF   x = b.

Automatic differentiation provides an easy manner to compute DF. Since m << n, the reverse method allows to calculate the derivatives of the pressure at the exit points with respect to the estimated BHPs. It brings an n ×m matrix U. Then, the forward mode is adapted to compute the derivatives of the calculated BHPs with respect to the pressure at the exit points. It provides an m ×n matrix V^T. After the simple product of U and V^T, we obtain easily all the derivatives of the calculated BHPs with respect to the estimated ones. We have DF = I-U V^T, with U V^T of rank m and the system DF   x = b is thus easy to solve.

Date received: December 17, 1999