### Abstract

The 0-1 quadratic knapsack problem (QKP) in wind farm layout optimization models possible turbine locations as nodes, and power loss due to wake effects between pairs of turbines as edges in a complete graph. The goal is to select up to a certain number of turbine locations such that the sum of selected node and edge coefficients is maximized. Finding the optimal solution to the QKP is difficult in general, but it is possible to obtain a tight upper bound on the QKP's optimal value which facilitates the use of heuristics to solve QKPs by giving a good estimate of the optimality gap of any feasible solution. This article applies an upper bound method that is especially well-suited to QKPs in wind farm layout optimization due to certain features of the formulation that reduce the computational complexity of calculating the upper bound. The usefulness of the upper bound was demonstrated by assessing the performance of the greedy algorithm for solving QKPs in wind farm layout optimization. The results show that the greedy algorithm produces good solutions within 4% of the optimal value for small to medium sized problems considered in this article.

Original language | English (US) |
---|---|

Pages (from-to) | 367-381 |

Number of pages | 15 |

Journal | Engineering Optimization |

Volume | 50 |

Issue number | 3 |

DOIs | |

State | Published - Mar 4 2018 |

### Fingerprint

### Keywords

- Wind farm
- greedy algorithm
- layout optimization
- mixed integer programming
- quadratic knapsack problem
- upper bound

### ASJC Scopus subject areas

- Computer Science Applications
- Control and Optimization
- Management Science and Operations Research
- Industrial and Manufacturing Engineering
- Applied Mathematics

### Cite this

**A tight upper bound for quadratic knapsack problems in grid-based wind farm layout optimization.** / Quan, Ning; Kim, Harrison Hyung Min.

Research output: Contribution to journal › Article

*Engineering Optimization*, vol. 50, no. 3, pp. 367-381. https://doi.org/10.1080/0305215X.2017.1316844

}

TY - JOUR

T1 - A tight upper bound for quadratic knapsack problems in grid-based wind farm layout optimization

AU - Quan, Ning

AU - Kim, Harrison Hyung Min

PY - 2018/3/4

Y1 - 2018/3/4

N2 - The 0-1 quadratic knapsack problem (QKP) in wind farm layout optimization models possible turbine locations as nodes, and power loss due to wake effects between pairs of turbines as edges in a complete graph. The goal is to select up to a certain number of turbine locations such that the sum of selected node and edge coefficients is maximized. Finding the optimal solution to the QKP is difficult in general, but it is possible to obtain a tight upper bound on the QKP's optimal value which facilitates the use of heuristics to solve QKPs by giving a good estimate of the optimality gap of any feasible solution. This article applies an upper bound method that is especially well-suited to QKPs in wind farm layout optimization due to certain features of the formulation that reduce the computational complexity of calculating the upper bound. The usefulness of the upper bound was demonstrated by assessing the performance of the greedy algorithm for solving QKPs in wind farm layout optimization. The results show that the greedy algorithm produces good solutions within 4% of the optimal value for small to medium sized problems considered in this article.

AB - The 0-1 quadratic knapsack problem (QKP) in wind farm layout optimization models possible turbine locations as nodes, and power loss due to wake effects between pairs of turbines as edges in a complete graph. The goal is to select up to a certain number of turbine locations such that the sum of selected node and edge coefficients is maximized. Finding the optimal solution to the QKP is difficult in general, but it is possible to obtain a tight upper bound on the QKP's optimal value which facilitates the use of heuristics to solve QKPs by giving a good estimate of the optimality gap of any feasible solution. This article applies an upper bound method that is especially well-suited to QKPs in wind farm layout optimization due to certain features of the formulation that reduce the computational complexity of calculating the upper bound. The usefulness of the upper bound was demonstrated by assessing the performance of the greedy algorithm for solving QKPs in wind farm layout optimization. The results show that the greedy algorithm produces good solutions within 4% of the optimal value for small to medium sized problems considered in this article.

KW - Wind farm

KW - greedy algorithm

KW - layout optimization

KW - mixed integer programming

KW - quadratic knapsack problem

KW - upper bound

UR - http://www.scopus.com/inward/record.url?scp=85019040329&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85019040329&partnerID=8YFLogxK

U2 - 10.1080/0305215X.2017.1316844

DO - 10.1080/0305215X.2017.1316844

M3 - Article

AN - SCOPUS:85019040329

VL - 50

SP - 367

EP - 381

JO - Engineering Optimization

JF - Engineering Optimization

SN - 0305-215X

IS - 3

ER -