4
$\begingroup$

I've come across this problem while trying to work out a table-formatting algorithm.

It's very similar to standard linear programming (though it uses $>$ instead of $<$; I'm not extremely familiar with linear programming, but I believe this doesn't matter much).

Let $\vec v = (v_1, \dots, v_n)$ be a vector of positive-integer variables.

The problem is to find if there is an assignment to $\vec v$ such that

$$ v_1 + \dots + v_n = c $$

and

$$ A \vec v \geq \vec w $$

where $c$ is a known constant, $\vec w$ is a known constant, and $A$ is a matrix with the special property that each row of $A$ is of the form $(0, \dots, 0, 1, \dots, 1, 0, \dots, 0)$.

That is, each inequality constraint only uses coefficients 1 and 0, and only "consecutive" variables appear in each linear constraint.


I think that this problem is NP-complete, but I haven't been able to prove it.

I think a reduction to exactly-1-in-3-SAT or set-cover is most likely to succeed (variables would be literals/values respectively and rows in the matrix would correspond to clauses/sets), but the restriction that constraints only refer to consecutive variables doesn't seem strong enough to describe arbitrary clauses/sets.

Alternatively, I might be wrong, and this problem actually has an algorithm that I have been missing. (The problem I'm actually interested in solving is finding the smallest $c$ such that constraints remain satisfiable, but I've phrased the problem this way so that it remains a simple decision problem)


As an example, here's a small instance of this problem:

$$ \begin{array}{} v_1 + v_2 + v_3 + v_4&=& 10 \\ v_1 &\geq& 1 \\ v_2 &\geq& 1 \\ v_2 + v_3 &\geq & 3 \\ v_3 + v_4 & \geq & 4 \\ v_3 &\geq& 1 \\ v_4 &\geq& 1 \end{array} $$

which has a possible assignment $\vec v = (1, 1, 6, 2) $.

$\endgroup$
  • 1
    $\begingroup$ Your problem is a special case of integer programming (IP). While IP is hard in general, there are some special cases that are polynomial time solvable. One such case is when your matrix $A$ is totally unimodular. I don't think that this is true for every matrix that matches your current description. Is there a more precise description of $A$, or can all possible cases of $A$ according to your current restriction occur? $\endgroup$ – Discrete lizard Apr 23 at 17:47
  • $\begingroup$ @Discretelizard There are a few minor restrictions, which I don't think affect the problem. Every column has at least one $1$, there are no rows of all $0$s, and if any two variables always appear together, they should instead be replaced by a single variable. We can also say all of the rows must be distinct. (These are all implicit in having a 'nice' constraint problem, because otherwise you have unnecessary variable). The matrix $A$ isn't necessarily square, it has up to $\Theta(n^2)$ rows. $\endgroup$ – Curtis F Apr 23 at 18:48
  • $\begingroup$ If you wanted to show hardness, remember that you should reduce SAT or set cover to your problem and not the other way around. $\endgroup$ – Juho Apr 23 at 20:43
  • $\begingroup$ @Juho ah, that's what I was describing; I just wrote the word to instead of the word from $\endgroup$ – Curtis F Apr 23 at 23:16
3
$\begingroup$

Your problem is solvable in polynomial time.

Your problem is equivalent to ILP with difference constraints, i.e., every linear inequality has the form $x_j - x_i \ge c_{i,j}$. (Why? Set $x_i = v_1 + \dots + v_i$; then $v_{i+1} + \dots + v_j = x_j - x_i$.)

Such a system of inequalities can be solved with shortest-path algorithms. In particular, if we didn't have the restriction to integer values, this becomes the standard problem of solving a system of difference constraints. You can solve this by creating a graph with one vertex per variable and one edge per constraints, and finding shortest paths using Bellman-Ford. See, e.g., Algorithms: Difference Constraints, Decide whether a set of inequalities is solvable, http://videolectures.net/mit6046jf05_demaine_lec18/, or a good textbook (I think this is described in CLRS).

As stated, those algorithms don't take into account the restriction to integer solutions. But if you examine how shortest path algorithms work, if all of the constants are integers, then the solution will be an integer solution as well. So, that ensures you get an integer solution.

Lastly, the requirement that $v_1 + \dots + v_n = c$ is equivalent to $x_n = c$, which can be handled using the shortest paths algorithm. In particular, find a solution; then if $x_n \ne c$, then set $c' = c - x_n$ and add the constant $c'$ to all variables; the result will be another solution that satisfies all the inequalities, and also satisfies the equality $x_n = c$.

Finally, once you've solved to find a solution for the $x$'s, you can recover a solution for the $v$'s by setting $v_i = x_i - x_{i-1}$.

One catch is that this solution might not be all positive. To handle this, I suggest adding the inequalities $x_i - x_{i-1} \ge 0$ before solving. That will then meet all of your needs.

$\endgroup$
  • $\begingroup$ The substitution $x_i = v_1 + \dots + v_i$ is a great trick that I'll have to remember -- it looks obvious in retrospect. I think this will work; I'm going to try fitting this into my implementation and make sure I didn't miss anything. $\endgroup$ – Curtis F Apr 23 at 20:14

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.