3
$\begingroup$

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

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.

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ Nov 29, 2022 at 21:55

1 Answer 1

4
$\begingroup$

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} $$

  1. 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.

  2. 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)$.

  3. 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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Maltus
    Nov 19, 2022 at 9:07
  • $\begingroup$ 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$. $\endgroup$
    – Neal Young
    Nov 19, 2022 at 15:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – Maltus
    Nov 24, 2022 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.