Solving linear programs with special structure

Question

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:

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.

Answer 1

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.