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

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)367-381
Number of pages15
JournalEngineering Optimization
Volume50
Issue number3
DOIs
StatePublished - Mar 4 2018

Fingerprint

Knapsack Problem
Farms
Layout
Turbines
Turbine
Upper bound
Grid
Optimization
Greedy Algorithm
Computational complexity
Vertex of a graph
Optimization Model
Complete Graph
Optimality
Computational Complexity
Optimal Solution
Heuristics
Farm
Knapsack problem
Formulation

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.

In: Engineering Optimization, Vol. 50, No. 3, 04.03.2018, p. 367-381.

Research output: Contribution to journalArticle

@article{979eb070b2ad4a208da4021e40eeca30,
title = "A tight upper bound for quadratic knapsack problems in grid-based wind farm layout optimization",
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.",
keywords = "Wind farm, greedy algorithm, layout optimization, mixed integer programming, quadratic knapsack problem, upper bound",
author = "Ning Quan and Kim, {Harrison Hyung Min}",
year = "2018",
month = "3",
day = "4",
doi = "10.1080/0305215X.2017.1316844",
language = "English (US)",
volume = "50",
pages = "367--381",
journal = "Engineering Optimization",
issn = "0305-215X",
publisher = "Taylor and Francis Ltd.",
number = "3",

}

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 -