A Greedy Algorithm for a Special Class of Geometric Set Covering Problems

Publication: ResearchReport – Annual report year: 2012


View graph of relations

We consider the problem of covering a set of given points in the plane by the smallest number of axis aligned squares of a given fixed size. This problem is of importance for computational fluid dynamics simulations of both onshore and offshore wind turbine parks. For this special case of a geometric set covering problem we propose a greedy type algorithm. We also propose a linear mixed 0 – 1 formulation of the problem. For each problem instance this formulation is solved by a commercial branch-andcut solver and the results are used to validate the quality of the solution from the greedy algorithm. The greedy algorithm finds the minimum number of squares for all but one problem instances from a set of 26 representative real-world examples.
Original languageEnglish
Publication date2012
PublisherDTU Wind Energy
Number of pages9
ISBN (electronic)978-87-92896-19-3
NameDTU Wind Energy E

Bibliographical note

Contract no: 11/02917; project no: 43087; Sponsor: Business Innovation Fund (www.fornyelsesfonden.dk)


  • DTU-Wind-Energy-E-0013(EN)
Download as:
Download as PDF
Select render style:
Download as HTML
Select render style:
Download as Word
Select render style:

Download statistics

No data available

ID: 12460452