Problema del percorso minimo con variabili continue sottostanti
Recentemente mi sono interessato alla seguente variazione del problema del percorso più breve. Ho cercato in letteratura per giorni ma non sono riuscito a trovare alcun documento che studiasse questo problema. Vorrei chiederti se hai già visto questo problema (o un problema simile) e se puoi indicarmi della letteratura pertinente.
In poche parole, il problema è il seguente. Abbiamo un grafico diretto$G = (V, E)$. Per ogni vertice$v \in V$ abbiamo un set $S_v \in \mathbb R^m$ (diciamo convesso) e un punto in esso $x_v \in S_v$. La lunghezza del bordo$(u,v) \in E$ è, ad esempio, la distanza euclidea tra $x_u$ e $x_v$. Un sentiero$P$ dalla fonte $s \in V$ a destinazione $d \in V$è definito nel solito modo. La lunghezza del percorso$P = (v_1=s, v_2, \ldots, v_{n-1}, v_n=d)$, d'altra parte, è definito come il minimo rispetto alle posizioni dei punti $x_{v_1} \in S_{v_1}, \ldots, x_{v_n} \in S_{v_n}$ della somma delle lunghezze dei bordi $(v_1, v_2), \ldots, (v_{n-1}, v_n)$. Tra tutti i percorsi da$s$ per $d$, ne cerchiamo uno di lunghezza minima.
Questo problema ha il sapore del "percorso euclideo più breve" (vedere ad esempio Sharir e Schorr, "Su percorsi più brevi in spazi poliedrici") che è comune nella navigazione robotica, ma presenta importanti differenze. Ho anche visto problemi di percorso più breve con lunghezze d'arco generalizzate (vedi ad esempio Frieze, "Percorsi minimi nei grafici orientati"), ma questa formulazione del problema non corrisponde nemmeno a quella sopra.
Qualche pensiero / idea?
Risposte
Per rispondere alla domanda originale, questo non è un problema che ho visto prima. Ho votato contro la risposta di Kuifje, perché sebbene approssimativa dovrebbe essere abbastanza efficiente dal punto di vista computazionale se la discretizzazione non crea troppi punti.
Un altro approccio che penso funzionerebbe sarebbe un riff sulla decomposizione di Benders. Richiede che gli insiemi convessi siano poliedrici e dati algebricamente (o come insiemi di punti estremi e raggi estremi o come soluzioni di insiemi di disuguaglianze lineari). Il problema principale sarebbe un programma lineare intero misto che seleziona il "percorso virtuale" (il percorso nel grafico). Gli insiemi convessi e i punti in essi contenuti non apparirebbero nel problema principale. Il sottoproblema sarebbe un programma cono del secondo ordine che, per un candidato "percorso virtuale", calcola il "percorso fisico" corrispondente più breve (selezionando i punti negli insiemi convessi). Se il problema principale sottostimasse la lunghezza del percorso fisico, al problema principale verrebbe aggiunto un "taglio di ottimalità" e il divertimento riprenderà. Ho una formulazione provvisoria, ma non sono sicuro che sia utile.
Aggiornamento : per "richiesta popolare", ecco la mia idea. Qualcuno dovrebbe controllare la mia matematica. Innanzitutto, un po 'di terminologia. Il percorso virtuale è il percorso nel grafico. Il percorso fisico è la sequenza corrispondente di segmenti di linea che collegano i punti negli insiemi convessi associati. Io userò$s$ e $t$ per indicare rispettivamente l'origine e la destinazione del percorso virtuale.
Prima di formulare il problema principale, calcoliamo la distanza fisica più breve corrispondente a ciascun bordo in $E$. Permettere$$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.$$
Il problema principale coinvolge solo la parte virtuale (cioè il grafico), non la parte fisica. Per ogni bordo$(i,j)\in E$ abbiamo una variabile binaria $y_{i,j}$cioè 1 se e solo se quel bordo fa parte del percorso scelto. Abbiamo anche una variabile non negativa$w$che è un surrogato della lunghezza del percorso fisico. Il problema principale è:\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*}dove i puntini di sospensione rappresentano i tagli di Benders (a venire). Il primo insieme di vincoli è la solita roba del flusso di percorso; l'ultimo vincolo è un limite inferiore valido per ogni possibile percorso.
Il sottoproblema è un problema del cono di secondo ordine (penso - qualcuno dovrebbe davvero controllarlo perché normalmente non scherzo con i SOCP). Il sottoproblema è costruito attorno a un percorso virtuale proposto$P$. Io uso$P_V$ per indicare i vertici sul percorso e $P_E$per denotare i bordi del percorso, entrambi visti come insiemi. Utilizza variabili non negative$z_{i,j}$ per rappresentare la lunghezza euclidea del segmento fisico corrispondente a un bordo $(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*}
Il primo vincolo ($x_i \in S_i$) deve essere tradotto in uguaglianza lineare o vincoli di disuguaglianza. (Ricorda che presumo$S_i$ è poliedrico.) Se $S_i$è dato come un insieme di punti estremi (e forse un insieme di raggi estremi), ciò comporta l'aggiunta di un gruppo di variabili di peso usate per prendere combinazioni convesse di punti estremi e combinazioni non negative di raggi estremi. Nota che se il percorso virtuale è solo un singolo bordo$(i,j)$, questo problema può essere utilizzato per calcolare $d_{i,j}$.
L'idea è di risolvere il problema principale e ottenere un percorso virtuale candidato $\hat{P}$. Puoi risolvere il master con l'ottimalità o, se utilizzi un risolutore che supporta i callback, puoi semplicemente arrivare alla prima (o successiva) soluzione candidata. Questo percorso viene utilizzato per costruire il sottoproblema, che viene risolto per ottenere la rappresentazione fisica più breve effettiva del percorso virtuale. Se la variabile surrogata corrisponde alla lunghezza fisica, accetta la soluzione (e, se si utilizzano i callback, continua). In caso contrario, aggiungiamo il seguente taglio Benders:$$w\ge\hat{f}\left(\sum_{(i,j)\in\hat{P}_{E}}y_{i,j}-\left|\hat{P}_{E}\right|+1\right),$$ dove $\hat{f}$ è il valore obiettivo ottimale del sottoproblema (la lunghezza più breve possibile del percorso fisico) e $\left|\hat{P}_{E}\right|$è il numero di bordi nel percorso virtuale. Il taglio Benders è garantito non vincolante tranne quando un percorso virtuale contiene tutti i bordi di quello attuale, quindi non è un taglio forte in alcun modo, ma è valido.
Un modo per affrontare questo problema sarebbe discretizzare gli insiemi $S_v$ per ciascuno $v \in V$. Cioè, definire un numero finito di punti all'interno$S_v$e per ciascuno di questi punti, definire un nodo. Collega questi nodi a tutti i vicini di node$v$, ma adattare la distanza con la distanza euclidea effettiva.
Una volta che hai questo nuovo grafico, esegui il classico algoritmo del percorso più breve.
Ad esempio, supponi di avere un solo margine nel grafico: $G=(\{u,v\},(u,v))$. Vuoi il percorso più breve da$u$ per $v$. Definisci i nodi$u_1,...,u_n$ per coprire il set $S_u$e nodi $v_1,...,v_n$ per $S_v$e aggiungi un bordo da ogni vertice $u_i$ a ogni vertice $v_j$, con il costo $d_{u_i,v_j}$, dove $d$denota la distanza che stai utilizzando. È possibile definire una sorgente e collegarla a ciascun nodo$u_i$e un lavandino collegato a ciascuno $v_j$. Ora, il percorso più breve da$u$ per $v$ è il percorso più breve dalla sorgente al sink.
Se la disuguaglianza triangolare vale per la funzione distanza, non riesco a pensare a una buona ragione per cui non sarebbe sufficiente discretizzare solo i bordi degli insiemi $S_v$. In questo caso risparmieresti un po 'di spazio e ridurrai la complessità. Tuttavia, dimostrare che è sufficiente deve ancora essere fatto.