Applied algorithmics project (2021-2022)

General overview

In this project, the goal is to cleverly build vaccination centers in a city so that everyone lives near a vaccination center. This project will involve several steps:

  1. modeling the problem;
  2. implementation of algorithms solving the problem: brute force, algorithms based on dynamic programming, progressive algorithms, approximation algorithms etc.;
  3. testing your algorithms on different instances;
  4. possible extensions.

About the organization:

Input file format

There are two main formats that must be able to be taken into account as input files:

  1. a stored image in PPM format;
  2. as a graph, which can be represented for example by its adjacency list.

The PPM format

Description

The PPM format (for Portable Pixmap) is a very simple way to describe an image in textual form. In our case, we will use ASCII files of this format (see Wikipedia):

P3 # PPM ASCII file in RGB format
3 2 # the image contains 3 columns and 2 rows
255 # each R, G, B component is represented by an integer between 0 and 255
255  0    0     0  255  0       0   0  255 # first row 
0   255   0     0   0  255     255  0   0  # second row

The associated configuration file

In addition to the PPM format file, we use a configuration file config.txt to indicate :

The scale level scale is an integer greater than or equal to 1 which allows the image to be partitioned into disjoint squares of scale * scale pixels. The goal is to reduce the size of your instances (you have to decide how!), which may be too big depending on the size of the image chosen.

Finally, associating to each color in the image an index allows to represent the potential cost to cross this area (i.e. this pixel). For example, to move in (x+1,y) from (x,y) by moving one pixel to the right, the cost is given by cost[(x,y)] + cost[(x+1,y)]. This can be seen as the weight of the edge (x,y) - (x+1,y). Finally, note that it is not always possible to cross a pixel (for instance if it is located on water): we will use in this case the index 0 for the corresponding color.

If we take the example of the PPM file above, we see that it contains only 3 different colors:

  1. (0, 0, 255): blue;
  2. (0, 255, 0): green;
  3. (255, 0 ,0): red.

An example of a configuration file config.txt associated with this image could be is given below:

1 # scale 1, i.e., the image is not modified
0 255  0  0 # the index  of color (255,0,0) is 0
1 0 0 255 0 # the index of the green color is 1
3 0 0 255

In this example, we indicate that it is not possible to move on a pixel of red color.

A concrete example

Here is a concrete example of an image that you should be able to manipulate:

The PPM file associated with this image can be downloaded here. If you open this file, you can notice that the size of the image is 1727*764 pixels, and that each line of the file contains only one triple (R,G,B), and not as many triples as there are columns (i.e. the width of the image). This is a storage corresponding to a row-major order (see Wikipedia): the first 1727 triples represent the first row, triples 1728 to 3454 the second row and so on. This image contains seven different colors:

  1. (0,0,0): black;
  2. (0,0,255) blue;
  3. (0,255,0): green;
  4. (255,0,0): red;
  5. (255,0,255): magenta;
  6. (255,255,0): yellow;
  7. (255,255,255): white.

One can thus note that the black color represents the water zones (like the Seine), the magenta color the main roads etc. We can thus associate the following configuration file:

1 # scale 1, i.e., we do not modify the image
0   0   0   0 # the black color has the index 0
1  255  0  255  
3  255 255 255
4  255  0   0
7   0   0  255
10  0  255  0
17 255 255  0 

Creating other PPM images

You can easily create other instances of your choice. To do this, you must:

  1. go to uMap then click on “Créer une carte”;
  2. change the map background (vertical menu on the right, click on “Changer le fond de carte”) and choose “OSM Watercolor”;
  3. take a screenshot of the desired area in a file.png file.

To export the image in the PPM format:

  1. open file.png with GIMP;
  2. Fichier > Exporter Sous > file.ppm > Exporter;
  3. choose ASCII.

You will then need to run the following command from in the console:

foo@bar:~$ awk '{ ++x; if(x<=3) print $0; else { l1=$0; getline; l2=$0; getline; print l1 " " l2 " " $0; }}' file.ppm > res.ppm

We will obtain the final PPM file in a file named res.ppm. Here, the x<=3 means that the color of the pixel of coordinates (0,0) is on line 4 of file.ppm. Attention, Gimp tends to add a comment line (line beginning with the character #). If this is the case, remove the comments lines before running the command.

You can also modify the image and reduce the number of colors by using GIMP:

  1. Image > Mode > Couleurs indexées;
  2. “Générer une palette optimale” and choose the maximum number of colors.

Finally, for each indexed color you can specify the (R,G,B) value:

  1. Fenêtres > Fenêtres ancrables > Palette des couleurs indexées;
  2. Click on the desired color;
  3. In “Notation HTML”, write the desired color in hexadecimal (000000 to ffffff).

Then remember to export the image again in PPM format and run the awk command.

The graph format

Your program must also be able to read graphs as input files. These graphs are represented by their adjacency list in the following way:

0: 3 5 7 
1: 2 3
2: 1 4 ...
...
n-1: ...

To generate examples of graphs, you can use gengraph.c whose documentation is available here. To compile gengraph under Linux:

foo@bar:~$ gcc gengraph.c -lm -lbsd -o gengraph

or under MacOS :

foo@bar:~$ gcc gengraph.c -o gengraph

For example, you can generate a grid of size 3x3 by doing :

foo@bar:~$ ./gengraph mesh 3 3 -format list
0: 1 3
1: 0 2 4
2: 1 5
3: 0 4 6
4: 1 3 5 7
5: 2 4 8
6: 3 7
7: 4 6 8
8: 5 7

You can also test ./gengraph mesh 3 3 -format list -header which will give you additional information, and ./gengraph -list for the list of the 207 graphs that you can view with, for instance:

foo@bar:~$ gengraph mesh 10 10 -dele 0.2 -visu; open g.pdf

The option dele 0.2 allows to delete each edge of the generated graph with probability 0.2. The option delv p works in a similar way for vertices.

We will then consider that the costs are all equal (to 1 for instance) for all the vertices of the graph. There is then no associated configuration file.

A more formal statement of the problem

Thus, we can see that we can represent each instance as a graph. It is up to you to model the problem as a graph problem. The problem we are interested in is therefore the following:

Given a graph whose vertices are weighted, and a positive real number r, we want to build the smallest number of vaccination centers in such a way that each person (no matter where he/she is located) is at distance at most r from a vaccination center (it is up to you to define the notion of distance).

Now let us assume that we have a limited budget that allows us to build only k centers. The question is then to know where to place these k centers on the city in orderto minimize the maximum distance of any point of the map (i.e. a pixel of the image) to a center.

First Report

We ask you to write a small report (text or PDF file) explaining:

Deadline: Friday, October 1st

Formal statements

As we have seen, we are going to design algorithms to solve a graph problem, namely the Dominating Set problem. For this purpose, we have a weighted graph G = (V, E), where V represents the vertex set of G, and E its edge set. Each vertex u ∈ V has a weight omega(u) ∈ ℕ*. For every edge e = (u, v) ∈ E, we then define ω(e) = ω(u) + ω(v).

The cost of a path C (denoted cost[C]) is the sum of the weights of the edges of C. The distance between two vertices u and v (denoted by dist(u, v)) is the cost of a shortest path from u to v, i.e. the cost of a path from u to v of minimum weight. Let dist(u, u) = 0.

Given a (real or integer) number r, an r-dominating set of G is a subset of vertices S ⊆ V such that any vertex of G is at distance at most r from a vertex of S, i.e. u ∈ V, ∃v ∈ S s.t. dist(u, v) ≤ r.

Thus, the first student problem is the following:

Input : a graph G = (V, E) with a weight on each edge, a number r

Question : what is the smallest integer k such that G admits an r-dominating set of size at most k?

Le second problem is the following:

Input: a graph G = (V, E) with a weight on each edge, a positive integer k

We want: the smallest r such that G admits an r-dominating set of size at most k

Note that the second question can be solved using the first one. The idea is to fix r, and then find the size of a smallest r-dominating set of G. By dichotomy on r (to go faster) depending on the returned value, we will be able to answer the question.

Indeed, let us denote by the radius of G. First we fix $r = . We know that there is a r-dominating set of size 1. We now fix r = ℓ/2. If there is an r-dominating set of size k, we start again with r = ℓ/4 and so on. Otherwise, we try between 3/4ℓ (the value in the middle between ℓ/2 and ) and and so on…

Exact algorithm

First, we want to design and implement an exact algorithm for the first question, i.e., an algorithm that computes the size of a smallest r-dominating set of G, with r fixed. You can use a bruteforce algorithm, and/or use a solver (SAT, ILP)…

Exact Algorithms for Dominating Set

In this section, we are interested in exact algorithms for solving the Dominating Set problem, which corresponds to finding a 1-dominant set in a graph where each edge has weight one. Note that we can easily transform an instance (G=(V,E), r) of the r-Dominant Set problem into an instance (G’=(V’,E’)) of Dominating Set, where G is an unweighted graph such that:

Branch-and-Bound algorithm

A first possibility is to implement a Branch and bound algorithm. The idea is to notice that S ⊆ V is a dominating set of G if and only if u ∈ V, N[u] ∩ V ≠ ∅, where N[u] represents the closed neighborhood of u, i.e. the set containing u and all its neighbors. One can then imagine a recursive algorithm that will test, given a vertex u, all the possible ways to dominate u, i.e. that an algorithm that will branch on each vertex of N[u]. This creates a tree of height at most k (because we are only interested in sets S of size  ≤ k), but of unbounded width. To do this, we select a vertex of smallest degree. This gives an algorithm as follows:

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

And the first call must be dominating_set(G, , k).

Second report

We ask you to write a small report (text or PDF file) explaining:

Deadline: Friday, November 19th

Dynamic programming algorithm

In this section, we present a dynamic programming algorithm based on an article available here.

We recall that given a graph G = (V, E), an independent set (or stable) is a subset of vertices I ⊆ V such that for any pair of vertices u, v ∈ I, uv ∉ E. The problem of finding the maximum size of an independent set of G is NP-complete. On the other hand, we can find a maximal independent set very easily, using a greedy algorithm for example.

Let I = {v1, v2, …, vk} be an independent set of G, and let J = V \ I. Now the algorithm proceeds in two steps:

  1. we precompute for each subset X ⊆ J a subset of smallest cardinality Dx ⊆ I that dominates X ;
  2. we compute for each subset DJ ⊆ J a dominating set of G such that D ∩ J = DJ.

First step

For each subset X ⊆ J and for each integer , 1 ≤ ℓ ≤ k, we note by Opt(X, ) a set DX, ℓ of minimum cardinality (if any) such that:

  1. DX, ℓ ⊆ {v1, v2, …, v};
  2. X ⊆ N[DX, ℓ].

In other words, given a subset of vertices X of J and an integer between 1 and k (with k = |I|), we are looking for a subset DX, ℓ which uses only (but not necessarily all) the first vertices of I, and which dominates X. So we will compute in a table all the values DX, ℓ using dynamic programming, and by increasing values of .

Figure 1: Opt[X,4] = \{v_1, v_2, v_4\} with Opt[X,4] \subseteq \{v_1, v_2, v_3, v_4\} and Opt[X,4] dominates X.
Figure 1: Opt[X, 4] = {v1, v2, v4} with Opt[X, 4]  ⊆ {v1, v2, v3, v4} and Opt[X, 4] dominates X.

Some values of this table are very easy to compute, and represent the “basic cases”:

Figure 2: Opt[X,1] = \{v_1\} because v_1 dominates X and Opt[X',1] = \{\infty\} because v_1 is not adjacent to all the vertices of X'.
Figure 2: Opt[X, 1] = {v1} because v1 dominates X and Opt[X′, 1] = {∞} because v1 is not adjacent to all the vertices of X.

We can now compute Opt[X, ] for any non-empty subset of J and for any 2 ≤ ℓ ≤ k using the following recurrence:

Figure 3 : Opt[X,5] = Opt[X,4] but Opt[X',5] = \{v_5\} \cup Opt[X'',4] with X'' = X' \setminus N[v_5].
Figure 3 : Opt[X, 5] = Opt[X, 4] but Opt[X′, 5] = {v5} Opt[X″, 4] with X = X \ N[v5].

Indeed, in a dominating set of minimum size DX, ℓ ⊆ {v1, v2, …, v} of X we have:

Note that we have 2|V| − k subsets X ⊆ J and k values to compute for each X, which gives a table of size k × 2|V| − k.

Second step

In this step, given a set DJ ⊆ J, we wish to compute a dominating set D = DJ ∪ DI of G of minimum size with DI ⊆ I. The set DI can be partitioned into two sets DI1 and DI2. DI1 = I \ N(Dj), i.e., DI1 contains all the vertices of I that are not dominated by DJ. Since V = I ∪ J and I is an independent set, we must take all of them in D in order to dominate them. Note that the vertices of DI1 dominate some vertices of J, which we denote by N(DI1). Thus, DI1 ∪ DJ dominates all the vertices of I. It only remains to dominate the vertices of J \ (N[DJ] N(DI1)). For this, we fix DI2= Opt[J \ (N[DJ] N(DI1)), k].

Figure 4: Dominating set D = D_J \cup D^1_I \cup D^2_I of a graph G=(V,E) with V = I \cup J where I is a stable set of G.
Figure 4: Dominating set D = DJ ∪ DI1 ∪ DI2 of a graph G = (V, E) with V = I ∪ J where I is a stable set of G.

The set D thus computed corresponds to the smallest size of a dominating set of G containing DJ. By enumerating all the subsets DJ ⊆ J, we can then compute the size of a smallest dominating set of G (don’t forget the case DJ = ∅!).

The final algorithm

The final algorithm starts by computing a maximal independent set I of the graph G = (V, E) using a greedy algorithm. Let k = 0.2271 × |V|. If |I| ≥ k|, we execute steps 1 and 2. Otherwise, |I| < k and thus the size of a smallest dominating set of G is strictly less than k (since for any graph, any maximal independent set is also a dominating set). We can then enumerate all subsets of vertices of size at most k to find a minimum dominating set of G.

Third report

You ask you to write a small report (text or PDF file) explaining:

Deadline: Friday, December 10th

Progressive algorithm

We ask you to implement the progressive algorithm presented in course (see Section 2.12 of the course notes here).

Independent work

The last part of this project is free. You can for example decide:

Each time, you are asked to experimentally test your algorithms (make benchmarks), to explain the gain in time and/or memory if you have optimized your code etc.

Defenses

We ask you to send your final report (PDF format) by January 27. The defenses will take place on February 3 (CREMI, room 202) and will last 20-25 minutes per group. Here are the times for each group:

We ask that you discreetly enter the room 10 minutes before your time and log on to a computer in order to avoid any loss of time. You will have to quickly present what you have done, we will then ask you questions about your project. You can use slides, but it is not mandatory.