I have a problem with this exercise.
Consider an oriented graph $G = (V, A)$, with $n = | V |$, with any weights $c_{i j}$ associated with the edges $(i, j)$ in $A$ and with a source vertex, $s$, and a destination, $t$, in $V$.
- Write the Integer Linear Programming (ILP) model of the problem of determining in $G$ a path of minimum length from $s$ to $t$.
- Now consider a vertex $v$ contained in $V\setminus \{s, t\}$. Write the ILP model to find two paths of minimum overall length from $s$ to $t$, with no vertices in common (apart from the source and destination), one of which necessarily passes through $v$.
- Now consider a set of vertices $S$ contained in $V \setminus \{s, t\}$. Write the ILP model to find two paths of minimum overall length from $s$ to $t$, with no vertices in common (apart from the source and destination), which altogether touch all the vertices of $S$ in a balanced way: the vertices in $S$ touched by any one of the two paths must not exceed $3/5$ of all those in $S$.
This is my attempt:
Let $x_{i,j}=1$ if I choose the edge $(i,j)$ and $0$ otherwise. This is my ILP model: \begin{align} \text{minimize} \sum_{(i,j) \in A} c_{i,j}x_{i,j}\\ \sum_{(h,i) \in \delta^+(h)} x_{h,i}-\sum_{(i,h) \in \delta^-(h)} x_{h,i} &= 0&&\text{for every $h\in V\setminus\{s,t\}$} \\ \sum_{(s,i) \in \delta^+(s)} x_{s,i}-\sum_{(i,s) \in \delta^-(s)} x_{i,s} &= 1 \\ \sum_{(t,i) \in \delta^+(t)} x_{t,i}-\sum_{(i,t) \in \delta^-(t)} x_{i,t} &= -1 \\ \sum_{(i,j) \in A(S)} x_{i,j} &\leq |S| -1 && \text{for every $S\subseteq V$} \end{align}
Let $x_{i,j}=1$ if I choose the edge $(i,j)$ and $0$ otherwise. The same for the other walk with the labels $y_{i,j}$. This is my ILP model: \begin{align} \text{minimize} \sum_{(i,j) \in A} c_{i,j}(x_{i,j}+y_{i,j})\\ \sum_{(h,i) \in \delta^+(h)} x_{h,i}-\sum_{(i,h) \in \delta^-(h)} x_{h,i} &= 0 &&\text{for every $h\in V\setminus\{s,t\}$}\\ \sum_{(s,i) \in \delta^+(s)} x_{s,i}-\sum_{(i,s) \in \delta^-(s)} x_{i,s} &= 1 \\ \sum_{(t,i) \in \delta^+(t)} x_{t,i}-\sum_{(i,t) \in \delta^-(t)} x_{i,t} &= -1 \\ \sum_{(i,j) \in A(S)} x_{i,j} &\leq |S| -1 && \text{for every $S\subseteq V$}\\ \sum_{(h,i) \in \delta^+(h)} y_{h,i}-\sum_{(i,h) \in \delta^-(h)} y_{h,i} &= 0 &&\text{for every $h\in V\setminus\{s,t\}$} \\ \sum_{(s,i) \in \delta^+(s)} y_{s,i}-\sum_{(i,s) \in \delta^-(s)} y_{i,s} &= 1 \\ \sum_{(t,i) \in \delta^+(t)} y_{t,i}-\sum_{(i,t) \in \delta^-(t)} y_{i,t} &= -1 \\ \sum_{(i,j) \in A(S)} y_{i,j} &\leq |S| -1 && \text{for every $S\subseteq V$}\\ x_{i,h}+y_{j,h} &\leq 1 && \text{for every $(i,h)\in A$ and $(j,h)\in A$ }\\ \sum_{(v,i) \in \delta^+(v)} y_{v,i}+\sum_{(v,i) \in \delta^-(v)} x_{v,i} &= 1 \\ \end{align}
The same as before with additional condition that $$\sum_{(i,j) \in E(S)} y_{i,j}+\sum_{(i,j) \in E(S)} x_{i,j} \leq 3|S|/4 $$ where $E(S)=\{(i,j)\in E \,|\, i \in S\, , j \in S \}$ ; $\delta^+(a)=\{(i,j)\in E \,|\, i =a\}$
If $c_{i,j}>0$ for all $(i,j)$, you can omit the subtour elimination constraints.
The first two models are correct, but the flow balance constraints can be simplified: $$\sum_{(i,j)\in A} x_{i,j}-\sum_{(j,i)\in A} x_{j,i} = \begin{cases} 1 &\text{if $i=s$}\\ -1 &\text{if $i=t$}\\ 0 &\text{if $i\in V\setminus \{s,t\}$} \end{cases}$$
For the second model, the conflict constraints can be strengthened: $$\sum_{(i,j)\in A} (x_{i,j} + y_{i,j}) \le 1 \quad \text{for $i\in V\setminus \{s\}$}$$
For the third model, replace $3/4$ with $3/5$, only one endpoint of $(i,j)$ needs to be in $S$, and refer to $A$ instead of $E$.