기본 연속 변수의 최단 경로 문제
최근에 나는 최단 경로 문제의 다음 변형에 관심을 가졌습니다. 며칠 동안 문헌을 살펴 봤지만이 문제를 연구하는 논문을 찾을 수 없었습니다. 이전에이 문제 (또는 유사한 문제)를 본 적이 있는지, 그리고 관련 문헌을 알려줄 수 있는지 물어보고 싶습니다.
간단히 말해서 문제는 다음과 같습니다. 방향 그래프가 있습니다.$G = (V, E)$. 각 정점에 대해$v \in V$ 우리는 세트가 있습니다 $S_v \in \mathbb R^m$ (볼록한 말) 그리고 그 안에 포인트 $x_v \in S_v$. 가장자리의 길이$(u,v) \in E$ 예를 들어, 사이의 유클리드 거리 $x_u$ 과 $x_v$. 경로$P$ 출처에서 $s \in V$ 목적지까지 $d \in V$일반적인 방식으로 정의됩니다. 경로의 길이$P = (v_1=s, v_2, \ldots, v_{n-1}, v_n=d)$반면에, 포인트 위치의 최소 wrt로 정의됩니다. $x_{v_1} \in S_{v_1}, \ldots, x_{v_n} \in S_{v_n}$ 모서리 길이의 합계 $(v_1, v_2), \ldots, (v_{n-1}, v_n)$. 모든 경로 중$s$ ...에 $d$, 우리는 최소 길이 중 하나를 찾습니다.
이 문제는 로봇 내비게이션에서 흔히 볼 수있는 "Euclidean 최단 경로"(예 : Sharir and Schorr, "On Shortest Paths in Polyhedral Spaces"참조)의 풍미를 가지고 있지만 중요한 차이점이 있습니다. 또한 일반화 된 호 길이 (예 : Frieze, "방향성 그래프의 최소 경로"참조)에서 최단 경로 문제를 보았습니다. 그러나이 문제 공식은 위의 것과 완전히 일치하지 않습니다.
어떤 생각 / 아이디어?
답변
원래의 질문에 답하기 위해 이것은 이전에 본 문제가 아닙니다. 나는 Kuifje의 대답을 찬성했습니다. 왜냐하면 근사치이지만 이산화가 너무 많은 포인트를 생성하지 않으면 상당히 계산적으로 효율적이어야하기 때문입니다.
내가 효과가 있다고 생각하는 또 다른 접근 방식은 Benders 분해에 대한 리프입니다. 볼록 세트는 다면체이고 대수적으로 제공되어야합니다 (극단 점 및 극단 광선 세트 또는 선형 부등식 세트에 대한 솔루션으로). 마스터 문제는 "가상 경로"(그래프의 경로)를 선택하는 혼합 정수 선형 프로그램입니다. 볼록한 집합과 그 안의 점은 마스터 문제에 나타나지 않습니다. 하위 문제는 후보 "가상 경로"에 대해 가장 짧은 해당 "물리적 경로"를 계산하는 2 차 원뿔 프로그램입니다 (볼록 세트에서 점 선택). 마스터 문제가 물리적 경로의 길이를 과소 평가하면 마스터 문제에 "최적화 컷"이 추가되고 재미가 다시 시작됩니다. 나는 잠정적 인 공식을 가지고 있지만 그것이 유용하다고 확신하지 않습니다.
업데이트 : "인기있는 요청"으로, 여기 내 생각이 있습니다. 누군가 내 수학을 확인해야합니다. 첫째, 몇 가지 용어입니다. 가상 경로 그래프에서 경로이다. 물리적 경로는 연관된 볼록한 세트의 점을 연결하는 선분의 상응하는 서열이다. 나는 사용할 것이다$s$ 과 $t$ 가상 경로의 출발지와 목적지를 각각 나타냅니다.
마스터 문제를 공식화하기 전에 각 모서리에 해당하는 가장 짧은 물리적 거리를 계산합니다. $E$. 허락하다$$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.$$
마스터 문제는 물리적 부분이 아닌 가상 부분 (즉, 그래프)에만 관련됩니다. 각 모서리에 대해$(i,j)\in E$ 이진 변수가 있습니다 $y_{i,j}$해당 가장자리가 선택한 경로의 일부인 경우에만 1입니다. 음이 아닌 변수도 있습니다.$w$그것은 물리적 경로의 길이에 대한 대리입니다. 마스터 문제는 다음과 같습니다.\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*}줄임표는 벤더스 컷을 나타냅니다. 첫 번째 제약 조건은 일반적인 경로 흐름 항목입니다. 마지막 제약은 가능한 모든 경로에 대해 유효한 하한입니다.
하위 문제는 2 차 콘 문제 (- 누군가가 내 생각이다 정말 SOCPs와 I하지 일반적으로 엉망으로 이것을 확인해야합니다). 하위 문제는 제안 된 가상 경로를 중심으로 구성됩니다.$P$. 나는 사용한다$P_V$ 경로의 정점을 표시하고 $P_E$경로의 가장자리를 나타 내기 위해 둘 다 세트로 표시됩니다. 음이 아닌 변수를 사용합니다.$z_{i,j}$ 가장자리에 해당하는 물리적 세그먼트의 유클리드 길이를 나타냅니다. $(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*}
첫 번째 제약 ($x_i \in S_i$)는 선형 평등 또는 부등 제약으로 변환되어야합니다. (내가$S_i$ 다면체입니다.) $S_i$극단 점 집합 (그리고 극단 광선 집합 일 수도 있음)으로 주어지며, 이는 극단 점과 극단 광선의 음이 아닌 조합의 볼록 조합을 취하는 데 사용되는 가중치 변수를 추가하는 것을 수반합니다. 가상 경로가 단일 에지 인 경우$(i,j)$,이 문제는 계산하는 데 사용할 수 있습니다. $d_{i,j}$.
아이디어는 마스터 문제를 해결하고 후보 가상 경로를 얻는 것입니다. $\hat{P}$. 마스터를 최적으로 풀거나 콜백을 지원하는 솔버를 사용하는 경우 첫 번째 (또는 다음) 후보 솔루션까지만 갈 수 있습니다. 이 경로는 가상 경로의 실제 가장 짧은 물리적 표현을 얻기 위해 해결되는 하위 문제를 구성하는 데 사용됩니다. 대리 변수가 실제 길이와 일치하면 솔루션을 수락하고 콜백을 사용하는 경우 계속합니다. 그렇지 않은 경우 다음 벤더 컷을 추가합니다.$$w\ge\hat{f}\left(\sum_{(i,j)\in\hat{P}_{E}}y_{i,j}-\left|\hat{P}_{E}\right|+1\right),$$ 어디 $\hat{f}$ 하위 문제의 최적 객관적 값 (물리적 경로의 가능한 가장 짧은 길이)이고 $\left|\hat{P}_{E}\right|$가상 경로의 가장자리 수입니다. Benders 컷은 가상 경로에 현재의 모든 가장자리가 포함 된 경우를 제외하고는 바인딩되지 않음이 보장되므로 어떤 방식 으로든 강력한 컷은 아니지만 유효합니다.
이 문제를 해결하는 한 가지 방법은 세트를 이산화하는 것입니다. $S_v$ 각각 $v \in V$. 즉, 한정된 수의 점을 정의합니다.$S_v$그리고 이러한 각 점에 대해 노드를 정의합니다. 이 노드를 노드의 모든 인접 노드에 연결$v$하지만 실제 유클리드 거리로 거리를 조정합니다.
이 새로운 그래프가 있으면 기존의 최단 경로 알고리즘을 실행하십시오.
예를 들어 그래프에 단 하나의 간선 만 있다고 가정합니다. $G=(\{u,v\},(u,v))$. 최단 경로를 원합니다.$u$ ...에 $v$. 노드 정의$u_1,...,u_n$ 커버 세트 $S_u$및 노드 $v_1,...,v_n$ ...에 대한 $S_v$, 각 정점에서 가장자리 추가 $u_i$ 각 정점에 $v_j$, 비용 포함 $d_{u_i,v_j}$, 어디 $d$사용중인 거리를 나타냅니다. 소스를 정의하고 각 노드에 연결할 수 있습니다.$u_i$및 각각에 연결된 싱크 $v_j$. 자, 최단 경로$u$ ...에 $v$ 소스에서 싱크까지의 최단 경로입니다.
삼각형 부등식이 거리 함수를 유지한다면 집합의 경계 만 이산화하는 것만으로는 충분하지 않은 이유를 생각할 수 없습니다. $S_v$. 이 경우 약간의 공간을 절약하고 복잡성을 줄일 수 있습니다. 그러나 그것으로 충분하다는 것을 증명하는 것은 아직 이루어지지 않았습니다.