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

Ning Quan, Harrison M. Kim

Research output: Contribution to journalArticlepeer-review


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
Issue number3
StatePublished - Mar 4 2018


  • 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


Dive into the research topics of 'A tight upper bound for quadratic knapsack problems in grid-based wind farm layout optimization'. Together they form a unique fingerprint.

Cite this