# [BCH14] Cabling optimization of a windfarm and capacitated K-Steiner tree

**Conférence Internationale avec comité de lecture : **
PGMO-COPI'14 Gaspard Monge Program for Optimization - Conference on Optimization & Practices in Industry,
October 2014,

pp.4 pages,
Palaiseau (91),
France,

**Mots clés: ** Steiner tree, graph, wind-farm optimization, mathematical programming.

**Résumé: **
A wind farm is composed of wind turbines producing energy and cables used to
collect this energy and send it to a specific sub-station which then distributes power to customers. The cables laid between given connecting nodes. Engineering constraints impose that the energy flowing through a cable is unsplittable, i.e. the energy routed from turbines to a connecting node through different cables is then routed through a unique cable path from this node to the root. Knowing the location and production of turbines and the location, capacity and cost of all possible cables with their connecting nodes, the wind farm network design problem is to optimize the total length of required cables to install. A version of the problem including the possibility of parallel cables between connecting nodes and other constraints is studied in [4] where an approach based on integer linear programming is proposed to solve real-world instances.
The problem is in closed relation with the well-know Steiner tree problem: given a
weighted graph G, the K-Steiner tree problem is to find in G a minimum length
tree S spanning a specified set T of K vertices called terminals. More precisely, the basic network design problem corresponds to the capacitated rooted K-Steiner tree problem. In our problem, the sub-station is the root of the graph and the wind turbines are the terminals. The possible cables are the edges of the graph and the connecting nodes are the Steiner nodes. Any solution of
the network design problem corresponds to an anti-rooted Steiner tree.
We pesent some complexity results, algorithms solving special cases and a solution based on mathematical programming to solve the general problem.