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

Publication: ResearchReport – Annual report year: 2012

Standard

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

DTU Wind Energy, 2012. 9 p. (DTU Wind Energy E; No. 0013(EN)).

Publication: ResearchReport – Annual report year: 2012

Harvard

APA

CBE

Stolpe M, Bechmann A 2012. A Greedy Algorithm for a Special Class of Geometric Set Covering Problems. DTU Wind Energy. 9 p. (DTU Wind Energy E; No. 0013(EN)).

MLA

Vancouver

Stolpe M, Bechmann A. A Greedy Algorithm for a Special Class of Geometric Set Covering Problems. DTU Wind Energy, 2012. 9 p. (DTU Wind Energy E; No. 0013(EN)).

Author

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

DTU Wind Energy, 2012. 9 p. (DTU Wind Energy E; No. 0013(EN)).

Publication: ResearchReport – Annual report year: 2012

Bibtex

@book{2bb1c791a33c4f49a4dbcce4202ea75a,
title = "A Greedy Algorithm for a Special Class of Geometric Set Covering Problems",
publisher = "DTU Wind Energy",
author = "Mathias Stolpe and Andreas Bechmann",
note = "Contract no: 11/02917; project no: 43087; Sponsor: Business Innovation Fund (www.fornyelsesfonden.dk)",
year = "2012",
series = "DTU Wind Energy E",

}

RIS

TY - RPRT

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

A1 - Stolpe,Mathias

A1 - Bechmann,Andreas

AU - Stolpe,Mathias

AU - Bechmann,Andreas

PB - DTU Wind Energy

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 -