Following on the previous project of building a nonlinear model that finds the optimal solution to the gas flow network in Belgium we now want to examine details of how it is possible to implement it in a mathematical programming language such as AMPL.

In this project we first revisit the nonlinear model that was explained in more detail in project 1 and after go to questions that analyze the behavior of the model with the help of AMPL.

1 Model description

The sets of the model I = {All towns represented by Table ??}

P = {All passive edges }

A = {All active edges}

E = {All edges} = {P A}

And the parameters of our model

L_ij = Length in km of the pipe between town i and town j.

D_ij = Interior diameter of the pipe in mm between town i and town j.

= Minimum quantity of 10⁶m³ gas / day to town j.

= Maximum quantity of 10⁶m³ gas / day to town j.

= Minimum pressure in bar in town j.

= Maximum pressure in bar in town j. c_j = Cost in [$/m³] to buy to town j

K = Constant to convert BTU to m³

z = Gas compressibility factor

Lastly the variables for our model will be

f_ij = Flow of gas from town i to town j x_j = Net result of gas in 10⁶m³ / day to town j p_j = Pressure of gas in bar in town j

And the following numerical constants:

(1)

With everything declared the model is

minimize XKcjxj xI jI

s.t.

x_j = Xfji Xfij, j I

iI iI

x_j I x_j qjmin, j I p_j I

pj		pminj , j I
|fij|fij	=	Cij2 (p2i p2j), (i,j) P
|fij|fij		Cij2 (p2i p2j), (i,j) A
fij		0, (i,j) A
fij	=	0, (i,j) 6 E

From AMPL, using the optimizer Baron, we run this model and obtain the following table for the flow.

	Antwerpen	Arlon	Brugge	Gent	Liege	Mons	Namur	Sinsin	Voeren	Warnant	Zeebrugge	Zomergem
Antwerpen	0	0	0	-4.10082	0	0	0	0	0	0	0	0
Arlon	0	0	0	0	0	0	0	0	0	0	0	0
Brugge	0	0	0	0	0	0	0	0	0	0	0	4.8791
Gent	0	0	0	0	0	0	0	0	0	0	0	-9.43006
Liege	0	0	0	0	0	0	0	0	0	13.9139	0	0
Mons	0	0	0	0	0	0	-11.4722	0	0	0	0	0
Namur	0	0	0	0	0	0	0	0	0	-13.6629	0	0
Sinsin	0	0.251012	0	0	0	0	0	0	0	0	0	0
Voeren	0	0	0	0	20.344	0	0	0	0	0	0	0
Warnant	0	0	0	0	0	0	0	0.251012	0	0	0	0
Zeebrugge	0	0	8.87	0	0	0	0	0	0	0	0	0
Zomergem	0	0	0	0	0	-4.55097	0	0	0	0	0	0

Table 1: Table of flows.

2 Questions, group I

Using the solver Baron!

1. What is the total cost of the gas supplying the demands in Belgium?The total cost is given by

minimize ^XKc_jx_j (2) xI jI

which when running the solver with AMPL returns the value f = 1921171.317 which is in given in $.

2. How much gas should be sent from Zomergem to Gent?

From AMPL we obtain the Table 1 where we note that from Gent to Zomergem there is a flow of -9.43006 which means that from Zomergem to Gent it is 9.43006 million m³/day.

3. How much Algerian gas should be purchased?

Similarly as in the previous question we can note that from the table we send a total of 8.87 million m³ gas from Zeebrugge which means that from Algeria we need to buy that same amount.

4. How much gas is being transported from Warnant to Sinsin as a result of the compressor working on thisactive pipeline?

We note that for the active edge we have the following relation between flow

|f_ij|f_ij C_ij² (p²_i p²_j), (i,j) P (3)

This relationship is equality for a passive edge. We can compare the difference between the left handside and the right handside, which in this case would be

|f_ij|f_ij C_ij² (p²_i p²_j) = 0.251012² 0.00413627 (2160.46 2402.74) = 1.06514252

And this would describe how much gas is being transported as a result of the compressor working on this active pipeline. In this case doing this calculation results in approximately 1.065 million m³ gas being transported.

3 Questions, group II

1. Is the solution obtained locally optimal? Globally optimal? Explain your answers. Also explain if the approach you adopt to verify optimality works in general cases beyond this exercise.

The solution obtained is globally optimal. This is because we buy the lowest amount that is possible from constrains (purchasing 344 from Voeren and x_Zeebrugge = q_Zeebrugge^min = 8.870. Since the objective function is to minimize the cost of purchase, no other purchase from Norway( x_{V oeren}) and Algeria

(x_Zeebrugge) can be better.

This approach of course can not be used in general cases, since an optimum can lie in other points than in the boundary of the constraints.

2. In the given AMPL model, the pressure-related decision variables are not exactly the pressures at the nodes.What are these decision variables? Why can we use these variables, and why do we want to use them?

The decision variables are not the pressure at the nodes, but rather the pressures at the nodes squared. If we look at the constraints

|fij|fij = Cij2 (p2i p2j)

We notice that we can make the p_is linear by squaring them. This makes the constraints easier to solve, since the problem then becomes

|fij|fij = Cij2 (pi pj)

which is more linear than previously. In general linear programs are much easier to solve than nonlinear, hence if it possible to make it more linear by squaring the constants we wish to do so.

3. Describe conceptually how to find a feasible solution without using any given nonlinear programming solver(this is useful in case the solver actually requires you to provide a feasible initial solution).

One method of finding a feasible initial solution can be described as follows.

Fix the flows in all edges, so that the flow in each edge follows the constrains of q_j^min. For example, set and

and x_Zeebrugge = q_max^Zeebrugge. Let us focus on the flow from Voeren. Let the flow from Voeren

to Li`ege equal to the miniumum amount of demand at that node, in this case f<sub>V oeren,Liege`</sub> = 6.365. Now, in the equation

|fij|fij = Cij2 (p2i p2j) (4)

(the index i here being the city Voeren), let the initial pressure p_i = p_initial = p^max_i . By doing this, we now only have one unknown p_j, which is solvable. Solve for p_j. Move from Liege to Warnant, and use the same equation as before. The new p_i in Eq. (4) is the previous p_j that we just solved. Now, since the f_ijs and the p_is are known, we again solve for p_j. If we can make the left hand side equal to the right hand side, then we continue until we have set all the pressures at the nodes (we have a feasible solution). If we can not make the constraint hold by setting a new p_j (the right hand cant be equal to the left hand side by any feasible p_j), then we need to reduce the initial pressure by multiplying the initial pressure as p_initial 0.99 p_initial. And then we repeat this until we obtain a feasible solution.

Of course, we would similarly do this when we consider the flow from Algeria in town Zeebrugge.

4 Questions, group III

1. Assume that Norwegian gas supply is reduced. Specifically, both the minimum and maximum quantities of the supply from Voeren are reduced to 80% of their original values.
2. How does the total amount of Algerian gas purchased change?

When reoptimizing using 80% of the minimum and maximum quantity we obtain a new optimum that instead of buying 8.87 million m³ we instead buy 11.1534. Therefore the change is 11.1534 8.87 = 2.2834.

1. How does the total amount of Norwegian gas purchased change?

We go from having an previous optimum at 20.344 to 17.6096, hence the change is 20.344 17.6096 = 2.7344. c) Explain why the above changes occur!

Previously we bought the minimum requirement from both Norway and Algeria, whereas when changing the lower bound on required purchase from Norway the new amount we buy from Norway is now instead the upperbound of what we can buy. This is most likely because in order to satisfy all towns demand we need to buy more than what is the updated minimum amount from both Norway and Algeria. When this is the case we then notice that we buy the maximum possible from Norway and the reason is quite simple since buying from Norway is cheaper then Algeria.

2. What and how much can be changed in the data of the problem to make the compressor on the pipeline fromWarnant to Sinsin active? How can you tell the compressor is indeed active? Hint: the answer to thisquestion need not be unique.

One idea is changing the demand of the town Arlon and increasing this demand would at some point require that the compressor is active. In this case if we change the required demand of Arlon from 0.222 to 1.8 the compressor becomes activate which is seen easily as the pressure from Warnant to Sinsin is increased. If we keep increasing the demand further we will come to a point where the problem becomes infeasible.

3. Consider the case of increased demands:
4. The demands at all demand nodes are doubled, while the supply ateach supply node remains the same. Is thisoptimization model feasible? Explain your answer.

Before doubling the demands, the total gas demand for all nodes equals 3.9184.0345.2566.3652.120 6.848 + 0.222 = 28.763 which is less than the total capacity of 22.012 + 11.594 = 33.606. But when we double the demands we get that the demand is equal to 28.7632 = 57.526, which is greater than total capcity 33.606.

Hence, we can clearly say that it is infeasible.

1. The demands at all demand nodes are doubled, and the maximum supplies at all supply nodes are also doubled.Is this optimization model feasible? Explain your answer. Hint: make sure you use the appropriate solver to make your statement.

In this case it is not clear to say that it is infeasible. This is because, as previously, we see that the sum of the demands (doubled) is 57.526, but doubling the supply/capacity gives 2 33.606 = 67.212, so the sum of the demands are less than the total capacity. But this does not necessarily mean that we have a feasible solution either, as we have additional constraints that should be met. If we use these new demands and supplies and try to optimize with AMPL we obtain that with both snopt, baron and trying other solvers that the problem is infeasible. With the optimizer snopt there is a statement that infeasibilities minimized, but the problem is still infeasible. We know that if we double the supply and demand the infeasibilities must be connected to the pressure requirements. Particularly we notice that a consequence of this, which is easily checked, is that the intermediate nodes results in not having a zero net flow. Take for example the column of Zomergem in Table

2. 2. The sum of this column is not zero, meaning that the flow is not zero for this intermediate node, leading to a violation of the constraints.

	Antwerpen	Arlon	Brugge	Gent	Liege	Mons	Namur	Sinsin	Voeren
Antwerpen	0	0	0	-8.068	0	0	0	0	0
Arlon	0	0	0	0	0	0	0	0	0
Brugge	0	0	0	0	0	0	0	0	0
Gent	0	0	0	0	0	0	0	0	0
Liege	0	0	0	0	0	0	0	0	0
Mons	0	0	0	0	0	0	-16.924	0	0
Namur	0	0	0	0	0	0	0	0	0
Sinsin	0	0.444	0	0	0	0	0	0	0
Voeren	0	0	0	0	40.688	0	0	0	0
Warnant	0	0	0	0	0	0	0	0.444	0
Zeebrugge	0	0	23.188	0	0	0	0	0	0
Zomergem	0	0	0	0	0	-3.228	0	0	0
	Warnant	Zeebrugge	Zomergem
Antwerpen	0	0	0
Arlon	0	0	0
Brugge	0	0	15.352
Gent	0	0	-18.58
Liege	21.608	0	0
Mons	0	0	0
Namur	-21.164	0	0
Sinsin	0	0	0
Voeren	0	0	0
Warnant	0	0	0
Zeebrugge	0	0	0
Zomergem	0	0	0

Table 2: Table showing the flows of the optimization problem using the optimizer snopt.exe after dubbling the supplies and demands.

4. Consider the marginal reductions of the minimal supplies of Norwegianand Algerian gas. Consider one limit at a time. What are the approxi-mate derivatives of the total cost with respect to changes of the minimalsupplies of Norwegian and Algerian gas, evaluated at the original opti-mal solution? Describe how you obtain these approximate derivatives.In addition, compare the results with the values of the dual variables forthe limiting constraints in the optimal solution to the original problem.

We utilize directional derivative given by

(5)

And similarly defined for ). The idea here is that we can choose equal to a small value, say for example = 0.001, or perhaps even smaller and instead approximate the derivative with numerical answers provided by AMPL. Notice that in this case the function we are trying to minimize depends on two variables, i.e the amount of gas we buy from Norway to Voeren (V) and Algeria to Zeebrugge (Z). Doing these reoptimizations and simple calculations with = 0.00001 we obtain

and

Interestingly one can also compare with the dual variables solution for the limiting constraints and one obtains the numerical values 59328.6 and 80517.4. Illustrating the relationship between the derivative and solution of the dual problem, even though the problem is not entirely linear.