Is this problem that's similar to integer linear programming also an NP-complete problem?

Question

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

Answer 1

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.