Problème de chemin le plus court avec des variables continues sous-jacentes
Je me suis récemment intéressé à la variante suivante du problème du chemin le plus court. J'ai regardé dans la littérature pendant des jours, mais je n'ai trouvé aucun article étudiant ce problème. Je voudrais vous demander si vous avez déjà vu ce problème (ou tout autre problème similaire) et si vous pouvez m'indiquer une documentation pertinente.
En quelques mots, le problème est le suivant. Nous avons un graphe orienté$G = (V, E)$. Pour chaque sommet$v \in V$ nous avons un ensemble $S_v \in \mathbb R^m$ (dites convexe) et un point dedans $x_v \in S_v$. La longueur du bord$(u,v) \in E$ est, par exemple, la distance euclidienne entre $x_u$ et $x_v$. Un chemin$P$ de la source $s \in V$ à destination $d \in V$est défini de la manière habituelle. La longueur du chemin$P = (v_1=s, v_2, \ldots, v_{n-1}, v_n=d)$, d'autre part, est défini comme le minimum par rapport aux emplacements des points $x_{v_1} \in S_{v_1}, \ldots, x_{v_n} \in S_{v_n}$ de la somme des longueurs des arêtes $(v_1, v_2), \ldots, (v_{n-1}, v_n)$. Parmi tous les chemins de$s$ à $d$, nous cherchons une longueur minimale.
Ce problème a la saveur du "chemin le plus court euclidien" (voir par exemple Sharir et Schorr, "On Shortest Paths in Polyhedral Spaces") qui est courant dans la navigation robotique, mais il présente des différences importantes. J'ai aussi vu des problèmes de chemins plus courts avec des longueurs d'arc généralisées (voir par exemple Frieze, «Minimum Paths in Directed Graphs»), mais cette formulation de problème ne correspond pas tout à fait à celle ci-dessus non plus.
Des pensées / idées?
Réponses
Pour répondre à la question initiale, ce n'est pas un problème que j'ai vu auparavant. J'ai voté pour la réponse de Kuifje, car bien qu'approximative, elle devrait être assez efficace en calcul si la discrétisation ne crée pas trop de points.
Une autre approche qui, je pense, fonctionnerait serait un riff sur la décomposition de Benders. Cela nécessite que les ensembles convexes soient polyédriques et donnés algébriquement (soit comme ensembles de points extrêmes et de rayons extrêmes, soit comme solutions d'ensembles d'inégalités linéaires). Le problème principal serait un programme linéaire à nombres entiers mixtes qui sélectionne le «chemin virtuel» (le chemin dans le graphique). Les ensembles convexes et les points qu'ils contiennent n'apparaissent pas dans le problème principal. Le sous-problème serait un programme de cône du second ordre qui, pour un "chemin virtuel" candidat, calculerait le "chemin physique" correspondant le plus court (en choisissant les points dans les ensembles convexes). Si le problème principal sous-estimait la longueur du chemin physique, une «coupe d'optimalité» serait ajoutée au problème principal et le plaisir reprenait. J'ai une formulation provisoire, mais je ne suis pas sûr qu'elle soit utile.
Mise à jour : Par "demande populaire", voici mon idée. Quelqu'un devrait vérifier mes calculs. Tout d'abord, un peu de terminologie. Le chemin virtuel est le chemin dans le graphique. Le chemin physique est la séquence correspondante de segments de ligne reliant des points dans les ensembles convexes associés. Je vais utiliser$s$ et $t$ pour désigner respectivement l'origine et la destination du chemin virtuel.
Avant de formuler le problème maître, nous calculons la distance physique la plus courte correspondant à chaque arête de $E$. Laisser$$d_{i,j}=\min\left\{ \left\Vert x_{i}-x_{j}\right\Vert :x_{i}\in S_{i},x_{j}\in S_{j}\right\} \ \forall(i,j)\in E.$$
Le problème principal concerne uniquement la partie virtuelle (c'est-à-dire le graphique), pas la partie physique. Pour chaque bord$(i,j)\in E$ nous avons une variable binaire $y_{i,j}$c'est-à-dire 1 si et seulement si cette arête fait partie du chemin choisi. Nous avons également une variable non négative$w$c'est un substitut à la longueur du chemin physique. Le problème principal est:\begin{alignat*}{1} \min & \ \ w\\ \textrm{s.t.} & \sum_{(i,j)\in E}y_{i,j}-\sum_{(j,i)\in E}y_{j,i}=\begin{cases} 1 & i=s\\ -1 & i=t\\ 0 & s\neq i\neq t \end{cases}\forall i\in V\\ & w\ge\sum_{(i,j)\in E}d_{i,j}y_{i,j}\\ & \dots \end{alignat*}où les points de suspension représentent les coupes Benders (à venir). Le premier ensemble de contraintes est le truc habituel de flux de chemin; la dernière contrainte est une borne inférieure valide pour tout chemin possible.
Le sous-problème est un problème de cône de second ordre (je pense - quelqu'un devrait vraiment vérifier cela car je ne joue normalement pas avec les SOCP). Le sous-problème est construit autour d'un chemin virtuel proposé$P$. j'utilise$P_V$ pour désigner les sommets sur le chemin et $P_E$pour désigner les bords sur le chemin, tous deux considérés comme des ensembles. Il utilise des variables non négatives$z_{i,j}$ pour représenter la longueur euclidienne du segment physique correspondant à une arête $(i,j)\in P_E$. \begin{alignat*}{1} \min & \sum_{(i,j)\in P_{E}}z_{i,j}\\ \mathrm{s.t.} & \ \ x_{i}\in S_{i}\ \ \forall i\in P_{V}\\ & z_{i,j}\ge\left\Vert x_{i}-x_{j}\right\Vert \ \ \forall(i,j)\in P_{E}. \end{alignat*}
La première contrainte ($x_i \in S_i$) doit se traduire par des contraintes linéaires d'égalité ou d'inégalité. (Rappelez-vous que je suppose$S_i$ est polyédrique.) Si $S_i$est donné comme un ensemble de points extrêmes (et peut-être un ensemble de rayons extrêmes), cela implique l'ajout d'un groupe de variables de poids utilisées pour prendre des combinaisons convexes de points extrêmes et des combinaisons non négatives de rayons extrêmes. Notez que si le chemin virtuel n'est qu'un seul bord$(i,j)$, ce problème peut être utilisé pour calculer $d_{i,j}$.
L'idée est de résoudre le problème principal et d'obtenir un chemin virtuel candidat $\hat{P}$. Vous pouvez résoudre le maître à l'optimalité, ou si vous utilisez un solveur prenant en charge les rappels, vous pouvez simplement aller jusqu'à la première (ou la suivante) solution candidate. Ce chemin est utilisé pour construire le sous-problème, qui est résolu pour obtenir la représentation physique la plus courte réelle du chemin virtuel. Si la variable de substitution correspond à la longueur physique, acceptez la solution (et, si vous utilisez des rappels, continuez). Sinon, nous ajoutons la coupe Benders suivante:$$w\ge\hat{f}\left(\sum_{(i,j)\in\hat{P}_{E}}y_{i,j}-\left|\hat{P}_{E}\right|+1\right),$$ où $\hat{f}$ est la valeur objective optimale du sous-problème (la longueur la plus courte possible du chemin physique) et $\left|\hat{P}_{E}\right|$est le nombre d'arêtes dans le chemin virtuel. La coupe Benders est garantie non contraignante sauf lorsqu'un chemin virtuel contient toutes les arêtes que contient le chemin actuel, donc ce n'est en aucun cas une coupe forte, mais elle est valide.
Une façon de résoudre ce problème serait de discrétiser les ensembles $S_v$ pour chaque $v \in V$. Autrement dit, définissez un nombre fini de points dans$S_v$, et pour chacun de ces points, définissez un nœud. Reliez ces nœuds à tous les voisins du nœud$v$, mais adaptez la distance à la distance euclidienne réelle.
Une fois que vous avez ce nouveau graphe, exécutez l'algorithme classique du chemin le plus court.
Par exemple, supposons que vous n'ayez qu'un seul bord dans votre graphique: $G=(\{u,v\},(u,v))$. Vous voulez le chemin le plus court depuis$u$ à $v$. Définir des nœuds$u_1,...,u_n$ couvrir l'ensemble $S_u$et nœuds $v_1,...,v_n$ pour $S_v$et ajoutez une arête de chaque sommet $u_i$ à chaque sommet $v_j$, avec coût $d_{u_i,v_j}$, où $d$indique la distance que vous utilisez. Vous pouvez définir une source et la lier à chaque nœud$u_i$, et un évier lié à chacun $v_j$. Maintenant, le chemin le plus court de$u$ à $v$ est le chemin le plus court entre la source et le puits.
Si l'inégalité triangulaire est vraie pour la fonction de distance, je ne peux pas penser à une bonne raison pour laquelle il ne serait pas suffisant de discrétiser uniquement les frontières des ensembles $S_v$. Dans ce cas, vous économiseriez de l'espace et réduiriez la complexité. Cependant, prouver que cela est suffisant reste à faire.