# Applied Algorithms project M2 (2023-2024)

## General introduction

The European Parliament recently adopted a new rule on the placement of charging stations for electric cars on motorways. By 2026, all motorways will have to be equipped with at least one charging station every 60km.

To meet this requirement, it will be necessary to be able to give the location of the charging stations to be installed so that for every shortest freeway journey of at least 60km, there will be at least one charging station accessible. The aim is to minimize the number of stations installed.

The project will be carried out in several stages:

1. modeling the problem ;
2. implementation of algorithms (brute force, etc…);
3. possible extensions.

• groups of 3 or 4 students;
• the final version must be submitted before the Christmas vacations, and oral presentations will take place in January;
• several intermediate submission.

## Problem

The problem is to place a minimum number of stations on the motorways. These stations will have to be placed in such a way as to satisfy certain constraints. Any path longer than 60km must be covered by a station. Charging stations can only be placed where the infrastructure allows, at rest areas and existing stations.

The input will therefore be the motorway network, the rest areas and the maximum number of km. The output will be a list of rest areas.

You will have to provide a visualization of the results including equipped freeways and stations.

## Data

To solve this problem, we suggest you use openstreetmap data. You can retrieve them in json format by writing queries to overpass-turbo.eu.

The following query retrieves freeways in France:

``````[out:json];
area[name = "France"];
(way(area)["highway"~"^(motorway|trunk)\$"];>;);
out;
``````

The `highway=services` and `highway=rest_area` correspond to existing service stations and rest areas. Refer to the openstreetmap wiki to retrieve other necessary information.

You will create instances of different sizes to be able to test even the slowest algorithms.

From this data, you will automatically build the problem instances.

## First submission for 10/15

This submission is optional (but recommended).

What is expected (by priority):

1. Simplification of the graph;
2. Use an implementation of Floyd-Warshall on the graph or implement your modified version of the algorithm that stops for paths already covered;
3. For each shortest path, list the stations that cover it.

You have to provide a short report to explain your progress and your difficulties.

## Reduction to Dominating Set

Annotated Dominant Set:

• Instance: a graph G with marked vertices and an integer k
• Question: does G have a set of vertices S of size k such that any unmarked vertex is in S or has a neighbor in S?

Based on the point 3 of the first submission, code a (polynomial) reduction of the problem to Dominating Set or Annotated Dominating Set. (What do you conclude about the complexity of the problem?)

## Second submission for 10/29

1. All points from the first submission;
2. Reduce Highway coverage problem to Dominating Set (DS)
3. Implement a checker for DS ;
4. Implement a brute-force solution for DS or/and a reduction to SAT or/and ILP.
5. Bonus: other algorithms, e.g. approximation, gready, etc… (as you wish)

For Dominating Set algorithms, you will make them possible to be called on graphs in text format. (.dot for example)

run example:

``./my_program.py -SAT -g my_graph_20_vertices.dot -k 10``

Provide a report detailing the work carried out and any difficulties encountered. The report will examine both the theoretical and practical complexity (execution time) of the algorithms implemented.

## Final submission and defense

The final submission is due no later than 01/12.

You will provide a report covering the following points:

1. All points from previous reports;
2. the progress algorithm;
3. any other algorithms you have implemented.

You will describe in detail how to run your project on the CREMI machines, with examples. The project will be evaluated mainly on the report; anything not explained in the report will not be considered.

The defense will take place on 01/16 at CREMI (A28 room 203). They will last 20 to 25 minutes.

Here are the times for each group:

• 3:40pm: BLEAU Adrien, MASTOURI Amira and Boivin Morgan;
• 4:05pm: HOUPLAIN Antoine, LACOSTE Theo, MARCE Tassïr and GHIGO Vincent;
• 4:30pm: AMOSSE Nikolai, LEROY Valentin and TALBI Simon;