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

Publication: Research › Report – Annual report year: 2012

### Standard

**A Greedy Algorithm for a Special Class of Geometric Set Covering Problems.** / Stolpe, Mathias; Bechmann, Andreas.

Publication: Research › Report – Annual report year: 2012

### Harvard

*A Greedy Algorithm for a Special Class of Geometric Set Covering Problems*. DTU Wind Energy. DTU Wind Energy E, no. 0013(EN)

### APA

*A Greedy Algorithm for a Special Class of Geometric Set Covering Problems*. DTU Wind Energy. (DTU Wind Energy E; No. 0013(EN)).

### CBE

### MLA

*A Greedy Algorithm for a Special Class of Geometric Set Covering Problems*DTU Wind Energy. 2012. (DTU Wind Energy E; Journal number 0013(EN)).

### Vancouver

### Author

### Bibtex

}

### RIS

TY - RPRT

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

AU - Stolpe,Mathias

AU - Bechmann,Andreas

PB - DTU Wind Energy

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

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - DTU-Wind-Energy-E-0013(EN)

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

T3 - DTU Wind Energy E

T3 - en_GB

ER -