## 2 Overview of the Basic Concepts of Wind Farm Design and Optimization
### The Computational Complexity of the WFDO Problem
Both the LWFDO and the LWFD problems, as presented, are non-convex, Integer Nonlinear Programming (INLP) problems. It has been shown by [PERSON] (1999) that the general 0-1 integer programing _decision_ problems are NP-complete (problems which are both in the NP and in NP-hard subsets). The demonstration consisted in performing an explicit polynomial-time Turing reduction (or Cook reduction (1950)), showing that the Boolean satisfiability problem (e.g., 3-SAT) is reducible to the general 0-1 integer programing problem. Therefore, the Boolean satisfiability problem can be successfully reduced to the LWFD _decision_ problem, resulting in its NP-completeness. When the decision version of an optimization problem is proved to belong to the class of NP-complete problems, then the optimization version is NPO-complete (1964,147). If the LWFDO problem considers a discretized domain with \(n\) discretized locations, then there are \(2^{n}-n-1\) non-trivial possible configurations to be evaluated. An exhaustive enumeration algorithm applied to the LWFDO problem will have a time complexity of O(\(2^{n}\)); therefore it is considered to be an intractable, exponential time solution procedure and falls into the NEXPTIME complexity class (1930, 1941, 1942), one of the most time-consuming optimization procedures. Optimal solutions to the LWFDO problem can be confirmed only for small instance problems (e.g., instances allowing 30 discretized locations will have a search space of \(1.0737\times 10^{9}\) non-trivial possible solutions). For a particular (non-trivial) instance of the LWFDO problem, there is only one optimal solution (1964). The LWFDO problem model cannot be completely described in an analytical form (_i.e._, providing a closed form analytical expression for the Annual Energy Production [159]) and due to the non-differentiable, non-convex and non-linear behavior of the mono-objective function, calculus-based optimization approaches such as linear/quadratic programming, gradient methods, Newton-Raphson, _etc._ cannot be used to solve the problem. To attempt solving optimization problems of such complexity, heuristic and metaheuristic approaches are commonly employed, yielding near-optimal solutions as discussed in Section 3.3. The LWFDO problem can be further extended to two different problems: (1) the two-dimensional Linear Wind Farm Design and Optimization (2 DLWFDO) problem in which WTs are allowed to have different hub heights [138, 156, 160, 161]; and (2) the two-dimensional Wind Farm Design and Optimization (2 DWFDO) problem in which fixed hub height WTs are located in a finite discretized regular/irregular planar space (which was considered in most of the reviewed works). For both cases, the amount of elementary operations will increase in a polynomial way by considering the partial wake operation of partial wake-affected WTs and by the different inter-distances quantification method. Furthermore, additional elementary operations will be required if multi-directional, anisotropic free-stream wind, realistic WT efficiency and control operation as a function of the inflow condition and other complex objective formulations are considered. However, the total amount of elementary operations can still be described as a polynomial function of the amount of WTs in the two-dimensional array. Nevertheless, depending on the approach taken for the computation of the wind field and the wake interactions (e.g., by using CFD techniques [14, 162]) the elementary operations may grow in an exponential or hyper-exponential way. Therefore, the 2 DLWFDO and the 2 DWFDO problems are NPO-complete as well as their respective decision problem versions. An enumerative algorithm will have the same time complexity, O(2\({}^{n}\)), as in the LWFDO case. Two important differences must be noted for the 2 DWFDO problem in contrast with the LWFDO and 2 DLWFDO problems; the 2 DWFDO problem may have multiple optimal solutions (multimodal space) and typically contains more decision variables, thus being harder to solve.