Notice: Trying to get property of non-object in /var/www/examples/offshore-wind-farming/index.php on line 53

Notice: Trying to get property of non-object in /var/www/examples/offshore-wind-farming/index.php on line 82

Notice: Trying to get property of non-object in /var/www/examples/offshore-wind-farming/index.php on line 96

Offshore Wind Farming

with integer programming and Gurobi

In this example we'll solve the problem of how to minimize the cost of laying underwater cables to collect electricity produced by an offshore wind farm.

We'll construct a mathematical model of the business problem, implement this model in Gurobi's Python interface, and compute and visualize an optimal solution.

Although your own business may not involve operating a wind farm, the same basic techniques used in this example can be used for other applications like the planning of communication and transportation networks.

Problem Description

An offshore wind farm is a collection of wind turbines placed at sea to take advantage of the strong offshore winds. These strong winds produce more electricity, but offshore wind farms are more expensive to install and operate, than those on land.

We will use integer programming to reduce part of the cost of building an offshore wind farm. We will compute a plan for how to lay the underwater cables that connect the turbines. These cables are necessary to transfer the power produced by the turbines to land. The plan we compute will minimize the cost to install the underwater cables, while ensuring that each turbine is connected to the shore and each cable has sufficent capacity to handle the electrical current generated.

In our example, a wind farm is being built off the west coast of Denmark. There is a power station on the coast where all the electricity must be transferred to be distributed to the electric grid. There are also transfer stations in the wind farm where the power from several turbines can be collected and transferred along a single cable to the shore.

There are two factors we must consider when installing the cables. First, there is a fixed cost to lay a cable on the sea floor. This cost is proportional to the distance between the two stations the cable connects. Second, we must consider how much current will flow through the cables. Connections that carry large currents need thick cables. Thick cables are more expensive than thin cables.

Mathematical Model

The wind farm optimization model is an instance of a more general optimization model known as fixed charge network flow. Fixed charge network flow can be applied to a large number of business problems, for example in the planning of communication and transport networks. We'll describe the mathematical model for this problem in terms of turbines and underwater cables, but it's important to remember that the techniques used here can be applied to a very large set of business problems.

We represent the wind farm as a graph $G(V,E)$ of vertices $V$ and edges $E$. The turbines, transfer stations, and power stations are vertices in the graph. The set of potential cables are the edges of the graph.

The goal of our optimization model is decide which of these potential edges in the graph should be used. Or equivalently, which cables should be laid to connect the wind farm power network.

For each edge $(i,j) \in E$ we associate the following quantites:
• a flow: $x_{ij}$
• a maximum capacity: $u_{ij}$
• a cost per unit flow: $c_{ij}$
• a fixed cost: $f_{ij}$.

The flow is the amount of current flowing through the cable. The maximum capacity is the maximum current a cable can handle. The cost per unit flow, is the price we must pay to increase the thickness of the cable to handle an increase in current. The fixed cost is the price to lay the cable.

We also define a variable $y_{ij}$ on each edge, such that $y_{ij} = \begin{cases} 1 & \text{if we use edge (i,j)} \\ 0 & \text{otherwise.} \end{cases}$

For each vertex $i$ in the graph we define $s_i$ to be the power supplied at that vertex. Since turbines supply power they are sources with $s_i > 0$. Transfer stations do not supply or remove power from the network so they have $s_i = 0$. The power station on the coast is a sink that remove all power from the wind farm so it has $s_i < 0$.

With these quanities defined we now state the optimization model: \begin{align*} \mathrm{minimize} & \sum_{(i,j) \in E} c_{ij} x_{ij} + \sum_{(i,j) \in E} f_{ij} y_{ij}} \\ \mathrm{subject\ to} & \sum_{(i,j) \in E} x_{ij} - \sum_{(j,i) \in E} x_{ji} = s_i} && \forall i \in V \label{flow} \tag{1}\\ & 0 \leq x_{ij} \leq u_{ij} y_{ij} && \forall (i,j) \in E \label{cap} \tag{2}\\ & y_{ij} \in \{0,1\} && \forall (i, j) \in E. \end{align*} We now discuss each part of the model in detail.

The objective that we seek to minimize is given by $\sum_{(i,j) \in E} c_{ij} x_{ij} + \sum_{(i,j) \in E} f_{ij} y_{ij}.$ This is the total cost to install the cables. The term on the left is the variable costs (i.e. those that vary according to the current in the cable). The term on right is the fixed cost to install the cable.

If $y_{ij} = 1$, meaning that we decide to install a cable between nodes $i$ and $j$, then we pay a fixed cost $f_{ij}$. We also pay a cost $c_{ij} x_{ij}$ porportional to the amount of current that flows between nodes $i$ and $j$. This models the fact that cables that carry more current must be thicker (and thus more expensive).

Constraints \eqref{cap} enforces the limits on the maximum current capacity of each cable. If we install a cable between nodes $i$ and $j$, then $y_{ij} = 1$, and the flow $x_{ij}$ on that cable must statisfy $0 \le x_{ij} \le u_{ij}.$ If we don't install a cable between nodes $i$ and $j$, than $y_{ij} = 0$, and the flow $x_{ij} = 0$. For a cable that is not installed, both $x_{ij}$ and $y_{ij}$ are zero, meaning that this cable does not contribute to the cost in the objective.

Constraints \eqref{flow} enforce conservation of current in the network. Each constraint is the difference of two terms: $\sum_{(i,j) \in E} x_{ij} - \sum_{(j,i)} x_{ji} = s_i$ The term on the left is the sum of the currents flowing out of node $i$. The term on the right is the sum of the current flowing into node $i$. Their difference is the supply $s_i$ at node $i$.

When we solve the optimization problem in the variables $x_{ij}$ and $y_{ij}$ we compute the optimal cable layout.

Implementation

Below is the full implementation of the model (and the associated data) in Gurobi's Python interface:

from gurobipy import * # Vertices and associated supply vertices = {0: 4, 1: 3, 2: 2, 3: 0, 4: -6, 5: -3} # Dict key: edge, value: (capacity, cost per flow, fixed cost) edges = {(0,4): (4,1,1), (0,3): (2,1,1), (1,3): (3,1,1), (2,5): (2,1,1), (3,4): (2,1,1), (3,5): (1,1,1)} m = Model() x = {} # Flow on each edge y = {} # Binary variable for each edge # key: vertex, value: list of edges entering/leaving the vertex edgeIn = { v:[] for v in vertices } edgeOut = { v:[] for v in vertices } # Add variables for edge in edges: u = edge v = edge y[edge] = m.addVar(vtype=GRB.BINARY, name="y" + str(edge)) x[edge] = m.addVar(lb=0, vtype=GRB.CONTINUOUS, name="x" + str(edge) ) edgeIn[v] = edgeIn[v] + [x[edge]] edgeOut[u] = edgeOut[u] + [x[edge]] m.update() # Add constraints for v in vertices: m.addConstr(quicksum(edgeOut[v]) - quicksum(edgeIn[v]) == vertices[v], name="v%d" % v) for edge in edges: m.addConstr(x[edge] <= edges[edge]*y[edge], name=str(edge)) # Set objective m.setObjective(quicksum((edges[edge]*x[edge] + edges[edge]*y[edge]) for edge in edges)) m.optimize()

Live Demo

Below is a visualization of the example we have discussed.

• Turbines are represented by white circles:
• Transfer stations are represented by black circles: .
• The power station is represented by a green circle:

You can click anywhere in the sea to add a turbine. Clicking on an existing turbine will remove it. Click Compute Optimal Layout to solve and display the optimal cable network. The thickness of the edges in the network correspond to the amount of current transfered along that edge.

You can explore different scenarios by using the slider to vary the cost to lay an underwater cable. Changing this cost corresponds to changing $f_{ij}$ in the model, while holding $c_{ij}$ fixed. See if you can generate solutions with few long cables as well as solutions with many short cables.

5500 dollars per meter