title	Graph Optimization
emoji	📈
colorFrom	blue
colorTo	green
sdk	docker
app_port	7860
pinned	false

Graph Optimization

Application Streamlit pour optimiser la représentation plane d'un graphe non orienté dans le carré unité [0,1] x [0,1].

Le projet reprend l'objectif du notebook graph opti.ipynb : générer un graphe connexe, placer ses sommets aléatoirement, puis améliorer le dessin par recuit simulé.

Lancer en local

pixi run app

Lancer avec Docker

docker build -t graph-optimization .
docker run -p 7860:7860 graph-optimization

Puis ouvrir http://localhost:7860.

Fonction objectif

On cherche une disposition des sommets

$$ X = \left((x_1,y_1), \ldots, (x_n,y_n)\right) \in [0,1]^{2n} $$

qui rend le graphe lisible. Pour deux sommets (i) et (j), on note :

$$ d_{ij} = \sqrt{(x_i-x_j)^2 + (y_i-y_j)^2} $$

La fonction objectif principale est :

$$ J(X) = J_1(X) \times J_2(X) \times \left(J_3(X)+1\right) $$

Elle est minimisée par recuit simulé.

J1 : éloigner les sommets

On pénalise les sommets trop proches :

$$ J_1(X)=\sum_{1 \le i < j \le n} \frac{1}{\max(d_{ij}^2,\varepsilon^2)} $$

La somme est écrite sur (i<j) pour ne pas compter chaque paire deux fois. Une somme sur (i \ne j) donnerait le même optimum, à un facteur constant près.

J2 : rapprocher les sommets reliés

Pour chaque arête ((i,j) \in E), on pénalise sa longueur :

$$ J_2(X)=\sum_{(i,j)\in E} d_{ij}^2 $$

Ce terme favorise des arêtes courtes.

J3 : limiter les croisements

On définit la fonction indicatrice de croisement entre deux segments :

$$ \operatorname{cross}(u,v)= \begin{cases} 1 & \text{si les segments } u \text{ et } v \text{ se coupent},\\ 0 & \text{sinon.} \end{cases} $$

Pour une arête ((i,j)), on note (u_{ij}) le segment entre les positions des sommets (i) et (j). On compte les croisements uniquement entre arêtes disjointes :

$$ J_3(X)= \sum_{\substack{(i,j),(k,l)\in E\ {i,j}\cap{k,l}=\varnothing\ (i,j)<(k,l)}} \operatorname{cross}(u_{ij},u_{kl}) $$

La condition ((i,j)<(k,l)) indique qu'une paire d'arêtes n'est comptée qu'une seule fois. Le (+1) dans (J) évite que l'objectif tombe à zéro quand (J_3=0).

J4 : post-traitement optionnel

(J_4) n'entre pas dans l'objectif principal, car son calcul est plus coûteux. Il sert uniquement de passe locale optionnelle pour éloigner un sommet d'une arête qui n'est pas la sienne.

Pour un segment (u_{ij}) et un sommet (k\notin{i,j}), on note :

$$ D(u_{ij},k)=\min_{p\in u_{ij}} |p-(x_k,y_k)|_2 $$

Le terme utilisé est :

$$ J_4(X)= \sum_{(i,j)\in E} \sum_{\substack{1\le k\le n\ k\notin{i,j}}} \frac{1}{\max(D(u_{ij},k)^2,\varepsilon^2)} $$

La distance est bornée par (\varepsilon=10^{-4}) pour éviter les valeurs infinies.

Recuit simulé

A chaque tentative, l'algorithme choisit un sommet (k) et propose :

$$ (x_k',y_k')=(x_k,y_k)+(\Delta_x,\Delta_y), \qquad \Delta_x,\Delta_y \sim \mathcal{U}(-a,a) $$

La proposition est rejetée si elle sort du carré unité. Sinon, elle est acceptée si elle améliore l'objectif. Si elle le dégrade, elle peut encore être acceptée avec la probabilité de Metropolis :

$$ p=\exp\left(-\frac{J(X')-J(X)}{T}\right) $$

La température baisse après une acceptation. Si aucune proposition n'est acceptée après max_try tentatives, la température baisse aussi d'un palier. Le calendrier de température conserve une phase initiale chaude, puis décroît géométriquement :

$$ T = \left(n\cdot 0.99^i\right)_{i=1}^{89} ;\Vert; \left(n\cdot 0.98^i\right)_{i=45}^{N-44}, \qquad N=\max(10n,300) $$