-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathMOGPL_projet.tex
256 lines (244 loc) · 15.1 KB
/
MOGPL_projet.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
\documentclass[10pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{float}
\usepackage{amssymb}
\usepackage{graphicx}
\title{% \vspace{20mm}
\LARGE \textbf {Un problème de tomographie discrète}\\
\vspace{8mm}
\large \textbf{MOGPL}\\
\vspace{10mm}
%\begin{center}
% \includegraphics[scale = 1]{main_image.png}
%\end{center}
\author{Baptiste JARRY \\ Magdaléna TYDRICHOVA}
\large {Master d'informatique M1}\\
\vspace{5mm}
\large {Université Pierre et Marie Curie \vspace{15mm}}\\
\date{\vspace{10mm} \textsf{\textrm{\textit{10 décembre 2017}}}}}
\begin{document}
\maketitle
\thispagestyle{empty}
\newpage
\section*{Introduction}
\addtocounter{page}{-1}
\noindent
Dans le cadre de ce projet, on s'intéresse au problème de tomographie discrète. \\ \\
\noindent
Dans la première partie, on résoud le problème à l'aide de la programmation dynamique, on teste l'algorithme sur plusieurs instances et essaie d'observer et expliquer ses limites. \\ \\
\noindent
Souhaitant pouvoir résoudre des grilles plus complexes, on met en oeuvre la résolution à l'aide d'un PLNE. On modélise d'abord le problème comme un PLNE, puis on le teste et on compare les solutions avec celles de la méthode précédente. \\ \\
\noindent
Dans la dernière section du projet, une brève analyse des résultats ainsi que certaines améliorations possibles sont proposées.
\newpage
\section{Raisonnement par la programmation dynamique}
\subsection{Première étape}
\noindent \textbf{Q1} \\
Si on a calculé tous les $T(i,j)$, la case $T(m-1, k)$ nous indique si on peut colorier les $m$ premières cases de la ligne $l_i$ (donc la ligne entière) avec les $k$ premiers blocs (i.e. la séquence entière). \\ \\
\noindent \textbf{Q2}
\begin{itemize}
\item[1.] Si $l = 0$ et $j \in \lbrace 0, \hdots, m-1 \rbrace$, alors $T(j,l) = 0$. En effet, on peut "colorier" n'importe quel nombre de cases avec zéro bloc. \\
\item[2.] On suppose maintenant $l \geq 1$.
\begin{itemize}
\item[(a)] $j < s_l -1 \Rightarrow T(j,l) = FALSE$. En effet, cette inégalité signifie que le nombre de cases à colorier ($j+1$) est strictement plus petit que la longueur du dernier bloc. On ne peut donc pas colorier les $j+1$ premières cases avec le bloc $s_l$, et on ne peut donc pas non plus les colorier avec la sous-séquence des blocs $(s_1, \hdots, s_l)$.
\item[(b)] $j = s_l -1 \Leftrightarrow j+1 = s_l$, ce qui signifie que la longueur du dernier bloc est exactement égale au nombre de cases à colorier. On en déduit que $T(j,1) = TRUE$ et $T(j,l) = FALSE$ pour $l > 1$.
\end{itemize}
\end{itemize}
\noindent
\textbf{Q3} \\
On considère dans cette question le dernier cas non traité, c'est-à-dire le cas où $l \geq 1, j > s_l -1$. Il y a deux possibilités:
\begin{itemize}
\item Soit la case $(i,j)$ sera blanche après la coloration : dans ce cas on aura $T(j,l) = T(j-1,l)$.
\item Soit la case $(i,j)$ sera noire après la coloration, ce qui signifie que le bloc $s_l$ se termine à la case $(i,j)$. On en déduit qu'il commence à la case $(i, j - (s_l -1))$. Les blocs étant séparés par au moins une case blanche, la case $(i, j-s_l)$ sera blanche. Si $j-s_l > 0$, alors $T(j, l) = T(j-s_l -1, l-1)$. Si $j-s_l = 0$, alors $T(j,l) = TRUE$ si et seulement si $l = 1$.
\end{itemize}
\subsection{Généralisation}
\noindent\textbf{Q5} \\
\begin{itemize}
\item[1.] Si $l = 0$ et $j \in \lbrace 0, \hdots, m-1 \rbrace$: On peut colorier les $j+1$ premières cases avec zéro bloc si aucune des cases $0, \hdots, j$ n'est pas déjà coloriée en noir (ce qui impliquerait la présence d'un bloc ou au moins d'une partie d'un bloc). \\
\item[2.] On suppose maintenant $l \geq 1$.
\begin{itemize}
\item[(a)] $j < s_l - 1 \Rightarrow T(j,l) = FALSE $ pour la même raison que précédemment.
\item[(b)] $j = s_l -1$ Comme dans la question 2, $T(j,l) = FALSE $ pour $l>1$. Si $l=1$, $T(j,l) = TRUE$ si et seulement si il n'y a pas de case déjà coloriée en noir avant la case $(i,j)$.
\item[(c)] Supposons $j > s_l -1$. On distingue toujours deux cas.
\begin{itemize}
\item Soit le $l$-ième bloc finit sur la case $(i,j)$. Dans ce cas, il faut que la case $(i,j+1)$ ne soit pas en noir (si elle existe). De plus, il ne faut aucune case blanche jusqu'à la case $(i,j-s_l+1)$ ; en outre, la case $(i,j-s_l)$ qui précède le bloc ne doit pas etre coloriée en noir. $T(j,l) = TRUE$ si toutes ces conditions sont vérifiées et si on a également $T(j-s_l, l-1) = TRUE$.
\item Soit le $l$-ième bloc ne finit pas sur la case $(i,j)$. Dans ce cas, on a $T(j,l) = TRUE$ si et seulement si on a $T(j-1,l) = TRUE$ et si la case $(i,j)$ n'est pas déjà noire (auquel cas on ne pourrait pas colorier les $j+1$ premières cases uniquement avec les $l$ premiers blocs, car il y aurait au moins une case du bloc suivant). \\
\end{itemize}
Dans les deux cas, on calcule en plus le nombre de cases noires entre les positions $(i,0)$ et $(i,j)$. Si ce nombre dépasse la somme des longueurs des $l$ premiers blocs, alors on ne peut pas colorier les $j+1$ premières cases uniquement avec ces $l$ blocs, et on aura donc $T(j,l) = FALSE$. \\ \\
\noindent
De la même manière, si la somme des cases noires entre $(i,j+1) $ et $(i,N-1)$ dépasse la somme des longueurs des blocs $s_{l+1}, \hdots s_k$, on en déduit que $T(j,l) = FALSE$.
\end{itemize}
\end{itemize}
\noindent
\textbf{Q8}
\\
\noindent
Voici le tableau des temps de résolution pour les instances 1-10: \\ \\
\begin{tabular}{|c|c|}
\hline
numéro d'instance & temps de résolution [s]\\
\hline
\hline
1 & 0.013\\
\hline
2 & 5.8\\
\hline
3 & 4.2\\
\hline
4 & 10.7\\
\hline
5 & 7.7\\
\hline
6 & 22.7\\
\hline
7 & 10.7\\
\hline
8 & 18.5\\
\hline
9 & 342.7\\
\hline
10 & 349.2\\
\hline
\end{tabular}
\\ \\ \\
\newpage
\noindent
La grille obtenue pour le fichier \textit{9.txt} est la suivante:
\begin{figure}[H]
\includegraphics[scale=0.3]{09_dynam_fin.png}
\end{figure}
\noindent
\textbf{Q9} \\
\noindent
Si on applique l'algorithme sur l'instance \textit{11.txt}, on observe qu'aucune case n'a pu être coloriée. Si on essaie de résoudre cette instance "de tête", on voit que pour satisfaire les conditions il y a exactement une case noire dans la colonne, et que les blocs sont séparés par au moins une case blanche, il y a une unique solution qui est la suivante: \\
\begin{figure}[H]
\includegraphics[scale=0.5]{image11_algo_PLNE.png}
\end{figure}
\noindent
Pourtant, l'algorithme dynamique ne regarde qu'une seule ligne ou colonne en même temps (il ne regarde pas ce qui se passe "dans le futur"). Pour cette raison, d'après lui, chacune des cases peut être coloriée en noir ou en blanc au début. Il ne peut donc rien colorier dans la figure.
\newpage
\section{La PLNE}
\subsection{Modélisation}
\noindent
\textbf{Q10} \\
\noindent
Soit $l_i$ la i-ième ligne avec une séquence associée $(s_1, \hdots ,s_k)$. Si le bloc $t$ de longueur $s_t$ commence par la case $(i,j)$, alors les cases $(i,j)$ à $(i,j+s_t-1)$ doivent être noires, ce qui s'exprime comme: \footnote{Cette formulation n'est pas exacte. En fait, elle ne prend pas en compte le fait qu'on peut potentiellement dépasser les bords dans la somme. Ce problème est reglé dans la question 13 en limitant le nombre de variables.}
$$ y_{ij}^{t} \leq \frac{\sum_{l = j}^{j+s_t-1} x_{il}}{s_t}$$\\
\noindent
De manière analogue, on a pour la j-ième colonne $c_j$ possédant la séquence $(s'_{1}, \hdots , s'_{k'})$ :
$$ z_{ij}^{t} \leq \frac{\sum_{l = i}^{i+s'_t-1} x_{lj}}{s_t}$$
\textbf{Q11} \\
Avec les notations de la question précédente, on souhaite exprimer le fait que si le bloc $t$ de la i-ième ligne commence à la case $(i,j)$, alors le $(t+1)$-ième bloc ne peut pas commencer avant la case $(i, j+ s_t +1)$. Ce qui se formule par:
$$ y_{ij}^t \leq \sum_{l = j+s_t+1}^{N-1} y_{il}^{t+1} , t \in \lbrace 1, \hdots, k-1 \rbrace$$
\noindent
De manière analogue, on obtient pour les colonnes:
$$ z_{ij}^t \leq \sum_{l = j+s_t+1}^{M-1} z_{lj}^{t+1} , t \in \lbrace 1, \hdots, k'-1 \rbrace$$
\textbf{Q12} \\
\noindent
Pour formuler le PLNE, il faut exprimer à l'aide des variables définies précédemment les contraintes suivantes: \\
\begin{itemize}
\item[(1)] Un bloc ne doit apparaître qu'une seule fois sur une ligne.
\item[(2)] Un bloc ne doit apparaître qu'une seule fois sur une colonne.
\item[(3)] Il doit y avoir le bon nombre de cases noires par ligne.
\item[(4)] Il doit y avoir le bon nombre de cases noires par colonne.
\item[(5)] Le bloc $t+1$ d'une ligne doit se trouver après le bloc $t$.
\item[(6)] Le bloc $t+1$ d'une colonne doit se trouver après le bloc $t$.
\item[(7)] Si le bloc $t$ d'une ligne demarre à la colonne $j$, alors les cases qui suivent doivent être noires sur la longueur du bloc.
\item[(8)] Si le bloc $t$ d'une colonne demarre à la colonne $i$, alors les cases qui suivent doivent être noires sur la longueur du bloc. \\ \\
\end{itemize}
\noindent
On en déduit alors le PLNE suivant: \\ \\
$$\min \sum_{i = 0}^{M-1} \sum_{j = 0}^{N-1} x_{ij}$$
\begin{eqnarray}
\sum_{j = 0}^{N-1} y_{ij} & = & 1 \ \ \ \forall i \in \lbrace 0, \hdots, M-1 \rbrace \\
\sum_{i = 0}^{M-1} z_{ij} & = & 1 \ \ \ \forall j \in \lbrace 0, \hdots, N-1 \rbrace \\
\sum_{j = 0}^{N-1} x_{ij} - \sum_{l = 1}^k s_l & = & 0 \ \ \ \forall i \in \lbrace 0, \hdots, M-1 \rbrace \\
\sum_{i = 0}^{M-1} x_{ij} - \sum_{l = 1}^{k'} s_l & = & 0 \ \ \ \forall j \in \lbrace 0, \hdots, N-1 \rbrace \\
y_{ij}^t & \leq & \sum_{l = j+s_t+1}^{N-1} y_{il}^{t+1} , t \in \lbrace 1, \hdots, k-1 \rbrace, i \in \lbrace 0, \hdots, M-1 \rbrace \\
z_{ij}^t & \leq & \sum_{l = j+s_t+1}^{M-1} z_{lj}^{t+1} , t \in \lbrace 1, \hdots, k'-1 \rbrace, j \in \lbrace 0, \hdots, N-1 \rbrace \\
y_{ij}^{t} & \leq & \frac{\sum_{l = j}^{j+s_t-1} x_{il}}{s_t} , i \in \lbrace 0, \hdots, M-1 \rbrace, t \in \lbrace 1, \hdots, k-1 \rbrace \\
z_{ij}^{t} & \leq & \frac{\sum_{l = i}^{i+s'_t-1} x_{lj}}{s_t}, j \in \lbrace 0, \hdots, N-1 \rbrace, t \in \lbrace 1, \hdots, k'-1 \rbrace
\end{eqnarray}
\subsection{Implantations et tests}
\noindent
\textbf{Q13} \\
\noindent
Soit $l_i$ la i-ième ligne avec la séquence associée $(s_1, \hdots, s_k)$. Le $l$-ième bloc peut commencer au plus tôt sur la case $(i,j_d)$ avec $$j_d = l + \sum_{t = 1}^ {l-1} s_t$$
Ceci correspond au cas dans lequel le premier bloc commence par la première case de $l_i$ et tous les prédécesseurs du $l$-ième bloc sont separés entre eux par exactement une case. \\ \\
\noindent
De manière analogue, le bloc doit finir strictement avant la case $(i, j_f)$ avec :
$$ j_f = (N-1) - (k-l) - \sum_{t = l+1}^k s_t$$
\\ \\
\noindent
Voici le tableau des temps de calcul avec la méthode PLNE (sans le timeout de 2 minutes) : \\
\begin{tabular}{|c|c|}
\hline
numéro d'instance & temps de résolution [s]\\
\hline
\hline
1 & 0.01\\
\hline
2 & 28.47\\
\hline
3 & 0.05\\
\hline
4 & 29.45\\
\hline
5 & 9.54\\
\hline
6 & 756\\
\hline
7 & 0.27\\
\hline
8 & 1.36\\
\hline
9 & ?\\
\hline
10 & 5.64\\
\hline
12 & 216.41\\
\hline
13 & 0.88\\
\hline
14 & 0.26\\
\hline
15 & 176.52\\
\hline
16 & 536.6\\
\hline
\end{tabular}
\\ \\ \\
\noindent
En employant l'algorithme dynamique sur les instances \textit{12.txt} - \textit{16.txt}, nous avons observé qu'aucune des instances n'a été complétement résolue. La comparaison des temps d'exécution (cette fois-ci avec un timeout de 2 minutes) se lit dans le graphe ci-dessous. Les deux grilles obtenues pour l'instance \textit{15.txt} sont fournies ci-dessous. \\
\begin{figure}[H]
\includegraphics[scale=0.7]{temps_exec.png}
\end{figure}
\section{Pour aller plus loin}
\noindent
Dans les sections précédentes, on a pu observer qu'en général, l'algorithme dynamique semble être plus efficace en termes de la complexité temporelle que celui du PLNE. Pourtant, l'algorithme dynamique n'assure pas la résolution complète d'une grille. On a alors codé une méthode globale proposée dans le sujet : on a d'abord appliqué l'algorithme dynamique sur la grille. Puis, on a utilisé le PLNE de la section précédente sur les cases non déterminées. Pour exprimer que la case $(i,j)$ est déjà coloriée, on fixe la borne inférieure de la variable $x_{ij}$ à 1 si la case était noire, ou bien la borne supérieure à 0 si la case était blanche. \\ \\
\noindent
Dans le graphique suivant, on donne les temps d'exécution en employant l'algorithme hybride ou bien le PLNE. Pour avoir une idée sur l'impact de l'étape de prétraitement sur la vitesse de résolution par le PLNE, on trace également la durée de l'étape du pretraitement. Pour bien voir les différences temporelles entre algorithmes, on ne considère pas le timeout de 2 minutes : \\
\begin{figure}[H]
\includegraphics[scale=0.6]{temps_exec_tout.png}
\end{figure}
\noindent
On peut constater qu'en général, la durée de l'étape du PLNE est plus courte si on fait l'étape de prétraitement. Cette tendance est logique parce que l'algorithme \textit{Branch \& Bound} utilisé pour la résolution du PLNE est de complexité exponentielle. Fixer la valeur de certaines variables peut considérablement réduire l'arbre de recherche. Pourtant, on voit que sur les instances 13 et 14, l'algorithme hybride est moins efficace que la résolution par PLNE pure. Ceci est dû au fait que la durée d'exécution du PLNE est négligeable devant la durée de l'étape du prétraitement. \\ \\
\noindent
\section*{Conclusion}
\noindent
On a codé plusieurs méthodes de résolution d'un problème de tomographie discrète. \\ \\
\noindent
On a vu pas mal d'instances résolvables complètement par l'algorithme dynamique. En revanche, nous avons constaté que cette méthode n'est pas suffisante pour la résolution des grilles plus complexes. On peut en conclure qu'il n'est pas souhaitable d'utiliser la méthode dynamique pure. \\ \\
\noindent
Puis, on a pu comparer expérimentalement l'algorithme de PLNE avec l'algorithme hybride (avec l'étape de pretraitement). Sur la plupart des grilles complexes, l'algorithme hybride avait de meilleures performances. Sur les grilles plus simples (grilles \textit{1.txt} - \textit{10.txt}), l'algorithme hybride ne diffère pas de l'algorithme dynamique pur - l'étape de prétraitement est suffisante pour résoudre la grille. Etant donné que sur cette classe d'instances l'algorithme dynamique performait légèrement mieux que l'algorithme de PLNE, il semble être souhaitable de préférer l'algorithme hybride à celui de PLNE. \\ \\
\noindent
Pourtant, il y a aussi plusieurs instances sur lesquelles l'algorithme de PLNE fonctionne beaucoup mieux que l'algorithme hybride. Idéalement, il faudrait être capable de classifier (facilement) les instances avant la résolution pour savoir s'il s'agit d'une instance facilement résolvable par la méthode dynamique, par la méthode de PLNE ou bien par l'algorithme dynamique. \\ \\
\noindent
Pour conclure, il nous semble souhaitable d'utiliser la méthode hybride qui donne en général des résultats solides. Il faudrait faire plus de tests et analyses sur d'autres instances pour avoir des conclusions plus précises. \\
\noindent
\newpage
\end{document}