General Presentation

This year again, the heatwave has ravaged the university campus. Fortunately, the trees and green spaces have helped users endure the temperature. To improve the situation, the university would like to plant trees so that all utilized areas are covered by their shade. However, trees cannot be planted in concrete areas and must be replaced by umbrellas, which are less effective. Concrete areas reflect heat, limiting the spread of coolness.

The project will be carried out in several stages:

  1. Problem modeling;
  2. Implementation of algorithms (brute force, etc...);
  3. Addition of extensions.

About the organization:

Problem

You are presented with the following problems: How can trees be placed so that all utilized areas of the campus (sidewalks, etc.) are covered by shade? What is the minimum number of trees needed to cover these areas?

In a second phase, you will consider additional problems with umbrellas and the variation of the covered distance depending on the terrain.

You may also propose your own variants of the problems, justifying why they are relevant.

You will present your results graphically to facilitate understanding of your proposals.

Data

To carry out the project, you will need the cartographic data of the campus. This data can be retrieved via OpenStreetMap, for example by using Overpass queries. You can also use other open sources that you find. OSMnx may also be useful if you choose to do your project in Python.

By October 2nd

Each group will prepare a mini-presentation of the modeling. The chosen tools for the implementation will also be presented.

Branch and Bound algorithm

dominating_set(graph G, partial dominant S, integer k)
    if k = 0 :
        test if S is a dominant set
    else :
        u <- vertex of minimum degree among the vertices not dominated by S
        for all v in N[u] :
            dominating_set(G, S U {v}, k-1)

First Submission - 16/10

  1. Implement the modelization of the problem using Dominating Set or an equivalent problem;
  2. Implement the Bruteforce and Branch and Bound algorithms for the chosen problem.

Remember to start a report for the upcoming submissions.

Second submission 11/06

You have to write a report covering the following points: