patternMinor
Path finding under constraints
Viewed 0 times
constraintspathunderfinding
Problem
Let $ G=(V,E) $ be a directed graph with a real weight function $w$ defined on the edges and $ a,b \in V$. Let $\alpha$ denote the minimal weight of all paths from $a$ to $b$ and $\beta$ denote the minimal weight of all paths from $b$ to $a$. How do you find two paths $l_1,l_2$ such that:
Less formally, I want to find a path starting at $a$ ending with $b$ and returning to $a$ such that the path is not too long (at most 10% longer than the optimal solution) and tries to use as much as different roads as possible (if it used some road $(x,y)$ when going from $a$ to $b$ , it would try to avoid the road $(y,x)$ when going back to $a$)
- $l_1=(a,v_1,..,v_n,b)$
- $l_2=(b,u_1,..,u_m,a)$
- $w(l_1) + w(l_2)\leq 1.1(\alpha + \beta)$
- From all the paths holding the above, bring to minimum the sum of weights on the edges $e=(u,v)\in l_1$ such that $(v,u)\in l_2$
Less formally, I want to find a path starting at $a$ ending with $b$ and returning to $a$ such that the path is not too long (at most 10% longer than the optimal solution) and tries to use as much as different roads as possible (if it used some road $(x,y)$ when going from $a$ to $b$ , it would try to avoid the road $(y,x)$ when going back to $a$)
Solution
One solution would be to use integer linear programming (ILP). This is not guaranteed to have a polynomial worst-case running time (ILP can take exponential time), but ILP solvers are pretty impressive, and for reasonable-sized graphs, this might just be an effective solution in practice.
For each edge $e \in E$, let $x_e,y_e,z_e$ be integer variables with the constraint $0 \le x_e \le 1$, $0 \le y_e \le 1$, $0 \le z_e \le 1$ (so that $x_e,y_ez_e$ are forced to be either 0 or 1). The meaning of $x_e=1$ is that $e$ is part of the path $l_1$, and the meaning of $y_e=1$ is that $e$ is part of $l_2$, and the meaning of $z_e$ is that $e$ is part of both $l_1$ and $l_2$.
Now introduce the following constraints:
-
$\sum_{(a,v) \in E} x_{(a,v)} = 1$ (i.e., at least one of the edges out of $a$ must be selected in $l_1$).
-
$\sum_{(v,b) \in E} x_{(v,b)} = 1$ (i.e., $l_1$ contains an edge into $b$).
-
For each vertex $v \in V \setminus \{a,b\}$, $\sum_{(u,v) \in E} x_{(u,v)} = \sum_{(v,w) \in E} x_{(v,w)}$ (if there's an edge entering $v$, there has to be an edge leaving $v$).
-
$\sum_{(b,v) \in E} y_{(b,v)} = 1$ (i.e., $l_2$ contains an edge out of $b$).
-
$\sum_{(v,a) \in E} y_{(v,a)} = 1$ (i.e., $l_1$ contains an edge into $a$).
-
For each vertex $v \in V \setminus \{a,b\}$, $\sum_{(u,v) \in E} y_{(u,v)} = \sum_{(v,w) \in E} y_{(v,w)}$ (if there's an edge entering $v$, there has to be an edge leaving $v$).
-
$\sum_{e \in E} w(e) (x_e + y_e) \le 1.1 (\alpha+\beta)$ (condition 3 in the question holds).
-
For each $e \in E$, $z_e \ge x_e + y_{-e} - 1$, $z_e \le x_e$, and $z_e \le y_{-e}$, where $-e$ is the reversal of the edge $e$ (i.e., if $e=(u,v)$, then $-e=(v,u)$). (This enforces that $z_e = 1$ if and only if $x_e = y_{-e} = 1$.)
Now minimize $\sum_{e \in E} w(e) z_e$. This will minimize the total weight of the edges that are common to both $l_1$ and $l_2$.
For each edge $e \in E$, let $x_e,y_e,z_e$ be integer variables with the constraint $0 \le x_e \le 1$, $0 \le y_e \le 1$, $0 \le z_e \le 1$ (so that $x_e,y_ez_e$ are forced to be either 0 or 1). The meaning of $x_e=1$ is that $e$ is part of the path $l_1$, and the meaning of $y_e=1$ is that $e$ is part of $l_2$, and the meaning of $z_e$ is that $e$ is part of both $l_1$ and $l_2$.
Now introduce the following constraints:
-
$\sum_{(a,v) \in E} x_{(a,v)} = 1$ (i.e., at least one of the edges out of $a$ must be selected in $l_1$).
-
$\sum_{(v,b) \in E} x_{(v,b)} = 1$ (i.e., $l_1$ contains an edge into $b$).
-
For each vertex $v \in V \setminus \{a,b\}$, $\sum_{(u,v) \in E} x_{(u,v)} = \sum_{(v,w) \in E} x_{(v,w)}$ (if there's an edge entering $v$, there has to be an edge leaving $v$).
-
$\sum_{(b,v) \in E} y_{(b,v)} = 1$ (i.e., $l_2$ contains an edge out of $b$).
-
$\sum_{(v,a) \in E} y_{(v,a)} = 1$ (i.e., $l_1$ contains an edge into $a$).
-
For each vertex $v \in V \setminus \{a,b\}$, $\sum_{(u,v) \in E} y_{(u,v)} = \sum_{(v,w) \in E} y_{(v,w)}$ (if there's an edge entering $v$, there has to be an edge leaving $v$).
-
$\sum_{e \in E} w(e) (x_e + y_e) \le 1.1 (\alpha+\beta)$ (condition 3 in the question holds).
-
For each $e \in E$, $z_e \ge x_e + y_{-e} - 1$, $z_e \le x_e$, and $z_e \le y_{-e}$, where $-e$ is the reversal of the edge $e$ (i.e., if $e=(u,v)$, then $-e=(v,u)$). (This enforces that $z_e = 1$ if and only if $x_e = y_{-e} = 1$.)
Now minimize $\sum_{e \in E} w(e) z_e$. This will minimize the total weight of the edges that are common to both $l_1$ and $l_2$.
Context
StackExchange Computer Science Q#18725, answer score: 2
Revisions (0)
No revisions yet.