<p>Assuming none of the <span class="math-container">$w_{ij}$</span> variables are constrained to be non-negative, your problem can be recast as a particular min-cost flow problem, and via that solved by solving just one all-pairs shortest-path problem, as follows.</p>
<ol>
<li><p>The original LP is equivalent (after negating the objective) to
<span class="math-container">$$\displaystyle\max \{x_2 - x_1 +x_4 - x_3 + x_6 - x_5 : (\forall (i, j)\in C)~ x_i - x_j \le c_{ij}\}.$$</span></p>
</li>
<li><p>The dual is to minimize <span class="math-container">$\displaystyle\sum_{(i,j)\in C} c_{ij} f_{ij}$</span> subject to <span class="math-container">$f_{ij} \ge 0$</span> and</p>
</li>
</ol>
<p><span class="math-container">$$\sum_{i : (i, k)\in C} f_{ik} 
- \sum_{j : (k, j)\in C} f_{kj}
=
\begin{cases}
-1 &amp; (k\in \{1, 3, 5\}) \\
1 &amp; (k\in \{2, 4, 6\}) \\
0 &amp; (k\not\in[6]).
\end{cases}
$$</span></p>
<ol start="4">
<li><p>This is equivalent to the following minimum-cost flow problem. Create a flow network <span class="math-container">$G=(V,E)$</span> with a vertex <span class="math-container">$i\in V$</span> for each index <span class="math-container">$i$</span>, an infinite-capacity edge <span class="math-container">$(i, j)$</span> of cost <span class="math-container">$c_{ij}$</span> for each <span class="math-container">$(i, j)\in C$</span>, and artificial source and sink vertices <span class="math-container">$s$</span> and <span class="math-container">$t$</span> with edges <span class="math-container">$(s, 2)$</span>, <span class="math-container">$(s, 4)$</span>, <span class="math-container">$(s, 6)$</span>, <span class="math-container">$(1, t)$</span>, <span class="math-container">$(3, t)$</span>, and <span class="math-container">$(5, t)$</span> with cost zero and capacity 1.  Now ask for a minimum-cost <span class="math-container">$s$</span>-<span class="math-container">$t$</span> flow <span class="math-container">$f$</span> of value 3 in this network.</p>
</li>
<li><p>In this particular network, this is equivalent to finding three shortest paths <span class="math-container">$p_2$</span>, <span class="math-container">$p_4$</span>, <span class="math-container">$p_6$</span> such that for some bijection <span class="math-container">$\pi:\{2,4,6\}\leftrightarrow\{1,3,5\}$</span> each path <span class="math-container">$p_i$</span> goes from <span class="math-container">$i$</span> to <span class="math-container">$\pi(i)$</span>.</p>
</li>
<li><p>There are only nine possible pairs <span class="math-container">$(i, \pi(i))$</span>, so your problem can be solved by solving just one all-pairs shortest-path problem in <span class="math-container">$G$</span> (or three single-source problems), then considering the six possible bijections <span class="math-container">$\pi$</span> and taking the best.</p>
</li>
</ol>
<p>One downside is that these shortest-path problems presumably involve negative weights.  (But no negative-weight cycles unless your original problem is infeasible, I think.)</p>
<p>Hopefully this gives you something to work with.  Perhaps you can exploit the structure to get further improvements.</p>

CC BY-SA 4.0
2022-11-19T09:07:37.053Z
Thanks, Neal. This actually sounds like an interesting approach. I believe there may be something in this direction. I will run some experiments and report back whether it worked.
Maltus
CC BY-SA 4.0
2022-11-19T15:05:40.963Z
If the $w_{ij}$'s are constrained to be non-negative, then the starting LP is different.  But I think a small modification of the approach above will work.  I can write it out if you are interested in that case.  Briefly, the dual LP is then to minimize $\sum_{(i,j)\in C} c_{ij} f_{ij}$ subject to $\sum_{j:(k,j)\in C'} f_{kj} = \sum_{i:(i,k)\in C'} f_{ik}$ and $0\le f_{ij} \le 1$ for $(i,j)\in B$ and $0\le f_{ij}$ for $(i,j)\in C$ where $B=\{(1,2), (3,4), (5,6)\}$ and $C'=C\cup B$.
Neal Young
CC BY-SA 4.0
2022-11-24T10:18:32.623Z
Oh yes, almost forgot. Thanks for the help! I implemented and things appear to be working out. Speedup is between 3x-14x compared to CPLEX just in case anyone in the future wonders about that. The speedup depends on the instance, of course.
Maltus
CC BY-SA 4.0
2022-11-19T03:11:38.990Z
2022-11-24T15:35:09.373Z
2022-11-24T15:35:09.373Z
Neal Young
<p>We have an application and at some point we need to solve a linear programming problem that looks like this:</p>
<p><span class="math-container">$$
\min\ w_{1,2} + w_{3,4} + w_{5,6}\\
x_i - x_j \leq c_{ij},\ \forall\ (i,j) \in C\\
x_1 - x_2 \leq w_{1,2}\\
x_3 - x_4 \leq w_{3,4}\\
x_5 - x_6 \leq w_{5,6}
$$</span></p>
<p>where <span class="math-container">$x_i, x_j$</span> and <span class="math-container">$w_{1,2}, w_{3,4}, w_{5,6}$</span> are variables of <span class="math-container">$\mathbb{R}$</span> and <span class="math-container">$c_{ij} \in \mathbb{R}$</span> are constants. Set <span class="math-container">$C$</span> is the set of difference constraints for which the RHS is a constant. We know that pairs <span class="math-container">$(1,2),(3,4),(5,6) \notin C$</span>.</p>
<p>Obviously this can be solved with any linear programming tool out there. And because of this, we know this problem is solvable in polynomial time. Unfortunately, most LP solvers are very slow for our purposes so we are looking for some other technique that could exploit this structure somehow, if one exists.</p>
<p><strong>What we know:</strong> It is well known that</p>
<p><span class="math-container">$$ x_i - x_j \leq c_{ij},\ \forall\ (i,j) \in C$$</span></p>
<p>can be solved using shortest path algorithms by creating a distance graph from these constraints and running, for example, Bellman-Ford or Floyd-Warshall algorithms. If our objective function is only</p>
<p><span class="math-container">$$ \min\ w_1$$</span></p>
<p>it is possible to solve the problem with a trivial binary search. However, when there are three values which interplay with each other this is not straightforward (we believe).</p>
<p><strong>Question</strong>: Is there any known algorithm or technique that can solve this problem and which is <em>not</em> a Linear Programming algorithm (e.g., Simplex, Ellipsoid, etc.)? It would be helpful just to point us into some direction because so far we have not found anything remotely close that can help. Additionally, is there some special cases from this system which may have a known algorithm to be solved (say, if all <span class="math-container">$c_{ij} \geq 0$</span> or something)?</p>
<hr />
<p><strong>Counter example:</strong> Here is a counter example to the approach proposed in the answer <a href="https://cstheory.stackexchange.com/a/52165">https://cstheory.stackexchange.com/a/52165</a> (now deleted). It refers to the following system:</p>
<p><span class="math-container">$$
\min\ w_{1,2} + w_{3,4} + w_{5,6}\\
x_2 - x_5 \leq -5\\
x_2 - x_7 \leq 5\\
x_5 - x_1 \leq -5\\
x_4 - x_6 \leq -5\\
x_6 - x_3 \leq -5\\
x_6 - x_5 \leq -21\\
x_7 - x_3 \leq 0\\
x_7 - x_5 \leq -15\\
x_1 - x_2 \leq w_{1,2}\\
x_3 - x_4 \leq w_{3,4}\\
w_{5,6} = 0,\ \text{(to simplify)}
$$</span></p>
<p>If we construct the proposed graph, we have the following:
<a href="https://i.sstatic.net/n7OCs.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/n7OCs.png" alt="Equivalent graph from the counter example" /></a></p>
<p>Computing the shortest paths with Floyd-Warshall, we have:
<span class="math-container">$$
d_{2,1} = -15\\
d_{4,3} = -10
$$</span></p>
<p>which would imply a solution of value 25.
However, if we check the system replacing <span class="math-container">$w_{1,2} = 15$</span> and <span class="math-container">$w_{3,4}=10$</span> we will notice that this creates an infeasible system (the graph has a negative cycle).
Indeed, the optimal solution is 26, created with <span class="math-container">$w_{1,2}=15$</span> and <span class="math-container">$w_{3,4}=11$</span>. This is caused due to the interplay between the constraints <span class="math-container">$(1,2)$</span> and <span class="math-container">$(3,4)$</span> with the others in our system.</p>
<p>The current proposed solution is a valid <em>lower bound</em> but it is not guaranteed to produce the optimal solution.</p>
<p>We have tried using off-the-shelf LP solvers, including CPLEX, Gurobi, and GLPK, but are hoping for something faster.  We are also hoping for something that doesn't rely on expensive commercial software, so a dedicated algorithm for this class of problem would be very helpful.</p>

CC BY-SA 4.0
2022-11-29T21:55:52.260Z
Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/140939/discussion-on-question-by-maltus-solving-linear-programs-with-special-structure).
Bjørn Kjos-Hanssen
<graph-algorithms><optimization><linear-programming>
Solving linear programs with special structure
Maltus
# Solving linear programs with special structure

(Asked by: username_0 on 2022-11-18)

We have an application and at some point we need to solve a linear programming problem that looks like this:

$$
\min\ w\_{1,2} + w\_{3,4} + w\_{5,6}\\
x\_i - x\_j \leq c\_{ij},\ \forall\ (i,j) \in C\\
x\_1 - x\_2 \leq w\_{1,2}\\
x\_3 - x\_4 \leq w\_{3,4}\\
x\_5 - x\_6 \leq w\_{5,6}
$$

where $x\_i, x\_j$ and $w\_{1,2}, w\_{3,4}, w\_{5,6}$ are variables of $\mathbb{R}$ and $c\_{ij} \in \mathbb{R}$ are constants. Set $C$ is the set of difference constraints for which the RHS is a constant. We know that pairs $(1,2),(3,4),(5,6) \notin C$.

Obviously this can be solved with any linear programming tool out there. And because of this, we know this problem is solvable in polynomial time. Unfortunately, most LP solvers are very slow for our purposes so we are looking for some other technique that could exploit this structure somehow, if one exists.

**What we know:** It is well known that

$$ x\_i - x\_j \leq c\_{ij},\ \forall\ (i,j) \in C$$

can be solved using shortest path algorithms by creating a distance graph from these constraints and running, for example, Bellman-Ford or Floyd-Warshall algorithms. If our objective function is only

$$ \min\ w\_1$$

it is possible to solve the problem with a trivial binary search. However, when there are three values which interplay with each other this is not straightforward (we believe).

**Question**: Is there any known algorithm or technique that can solve this problem and which is *not* a Linear Programming algorithm (e.g., Simplex, Ellipsoid, etc.)? It would be helpful just to point us into some direction because so far we have not found anything remotely close that can help. Additionally, is there some special cases from this system which may have a known algorithm to be solved (say, if all $c\_{ij} \geq 0$ or something)?

---

**Counter example:** Here is a counter example to the approach proposed in the answer <https://cstheory.stackexchange.com/a/52165> (now deleted). It refers to the following system:

$$
\min\ w\_{1,2} + w\_{3,4} + w\_{5,6}\\
x\_2 - x\_5 \leq -5\\
x\_2 - x\_7 \leq 5\\
x\_5 - x\_1 \leq -5\\
x\_4 - x\_6 \leq -5\\
x\_6 - x\_3 \leq -5\\
x\_6 - x\_5 \leq -21\\
x\_7 - x\_3 \leq 0\\
x\_7 - x\_5 \leq -15\\
x\_1 - x\_2 \leq w\_{1,2}\\
x\_3 - x\_4 \leq w\_{3,4}\\
w\_{5,6} = 0,\ \text{(to simplify)}
$$

If we construct the proposed graph, we have the following:
[![Equivalent graph from the counter example](https://i.sstatic.net/n7OCs.png)](https://i.sstatic.net/n7OCs.png)

Computing the shortest paths with Floyd-Warshall, we have:
$$
d\_{2,1} = -15\\
d\_{4,3} = -10
$$

which would imply a solution of value 25.
However, if we check the system replacing $w\_{1,2} = 15$ and $w\_{3,4}=10$ we will notice that this creates an infeasible system (the graph has a negative cycle).
Indeed, the optimal solution is 26, created with $w\_{1,2}=15$ and $w\_{3,4}=11$. This is caused due to the interplay between the constraints $(1,2)$ and $(3,4)$ with the others in our system.

The current proposed solution is a valid *lower bound* but it is not guaranteed to produce the optimal solution.

We have tried using off-the-shelf LP solvers, including CPLEX, Gurobi, and GLPK, but are hoping for something faster. We are also hoping for something that doesn't rely on expensive commercial software, so a dedicated algorithm for this class of problem would be very helpful.

**Tags:** graph-algorithms, optimization, linear-programming
> **Comments:**
> **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/140939/discussion-on-question-by-maltus-solving-linear-programs-with-special-structure).  

---

## 1 answers

### Answer by username_2 on 2022-11-19. Score: 4 | Accepted answer

Assuming none of the $w\_{ij}$ variables are constrained to be non-negative, your problem can be recast as a particular min-cost flow problem, and via that solved by solving just one all-pairs shortest-path problem, as follows.

1. The original LP is equivalent (after negating the objective) to
   $$\displaystyle\max \{x\_2 - x\_1 +x\_4 - x\_3 + x\_6 - x\_5 : (\forall (i, j)\in C)~ x\_i - x\_j \le c\_{ij}\}.$$
2. The dual is to minimize $\displaystyle\sum\_{(i,j)\in C} c\_{ij} f\_{ij}$ subject to $f\_{ij} \ge 0$ and

$$\sum\_{i : (i, k)\in C} f\_{ik}
- \sum\_{j : (k, j)\in C} f\_{kj}
=
\begin{cases}
-1 & (k\in \{1, 3, 5\}) \\
1 & (k\in \{2, 4, 6\}) \\
0 & (k\not\in[6]).
\end{cases}
$$

4. This is equivalent to the following minimum-cost flow problem. Create a flow network $G=(V,E)$ with a vertex $i\in V$ for each index $i$, an infinite-capacity edge $(i, j)$ of cost $c\_{ij}$ for each $(i, j)\in C$, and artificial source and sink vertices $s$ and $t$ with edges $(s, 2)$, $(s, 4)$, $(s, 6)$, $(1, t)$, $(3, t)$, and $(5, t)$ with cost zero and capacity 1. Now ask for a minimum-cost $s$-$t$ flow $f$ of value 3 in this network.
5. In this particular network, this is equivalent to finding three shortest paths $p\_2$, $p\_4$, $p\_6$ such that for some bijection $\pi:\{2,4,6\}\leftrightarrow\{1,3,5\}$ each path $p\_i$ goes from $i$ to $\pi(i)$.
6. There are only nine possible pairs $(i, \pi(i))$, so your problem can be solved by solving just one all-pairs shortest-path problem in $G$ (or three single-source problems), then considering the six possible bijections $\pi$ and taking the best.

One downside is that these shortest-path problems presumably involve negative weights. (But no negative-weight cycles unless your original problem is infeasible, I think.)

Hopefully this gives you something to work with. Perhaps you can exploit the structure to get further improvements.

> **Comments:**
> **username_0**: Thanks, Neal. This actually sounds like an interesting approach. I believe there may be something in this direction. I will run some experiments and report back whether it worked.  
> **username_2**: If the $w_{ij}$'s are constrained to be non-negative, then the starting LP is different.  But I think a small modification of the approach above will work.  I can write it out if you are interested in that case.  Briefly, the dual LP is then to minimize $\sum_{(i,j)\in C} c_{ij} f_{ij}$ subject to $\sum_{j:(k,j)\in C'} f_{kj} = \sum_{i:(i,k)\in C'} f_{ik}$ and $0\le f_{ij} \le 1$ for $(i,j)\in B$ and $0\le f_{ij}$ for $(i,j)\in C$ where $B=\{(1,2), (3,4), (5,6)\}$ and $C'=C\cup B$.  
> **username_0**: Oh yes, almost forgot. Thanks for the help! I implemented and things appear to be working out. Speedup is between 3x-14x compared to CPLEX just in case anyone in the future wonders about that. The speedup depends on the instance, of course.  

---

