On Integer Programs That Look Like Paths

Abstract

Solving integer programs of the form $\min \bigl \{\textbf{x}\bigm \vert A\textbf{x} =\textbf{b},\textbf{l}\leqslant \textbf{x}\leqslant \textbf{u},\textbf{x}\in \mathbb {Z}^n\bigr \}$ is, in general, $\textsf{NP}$-hard. Hence, great effort has been put into identifying subclasses of integer programs that are solvable in polynomial or $\textsf{FPT}$ time. A common scheme for many of these integer programs is a star-like structure of the constraint matrix. The arguably simplest form that is not a star is a path. We study integer programs where the constraint matrix A has such a path-like structure: every non-zero coefficient appears in at most two consecutive constraints. We prove that even if all coefficients of A are bounded by 8, deciding the feasibility of such integer programs is $\textsf{NP}$-hard via a reduction from 3-SAT. Given the existence of efficient algorithms for integer programs with star-like structures and a closely related pattern where the sum of absolute values is column-wise bounded by 2 (hence, there are at most two non-zero entries per column of size at most 2), this hardness result is surprising.

A Example for One Clause

The reduction is from 3-SAT. We want to exemplify the proof idea for checking satisfaction of one clause, which is the most involved part of the construction. Consider a clause $v_1\vee \lnot v_3$. We add the following constraints

where variable lower and upper bounds are given by $f_1,f_2,f_3\in \{0,1,2\}$ and $\alpha _0, \alpha _1, \alpha _2,\alpha '_2, \beta \in \{0,1\}$.

We want to illustrate the effects of the constraints for $y_0\in \mathcal B=\{3,4\} = \{[011]_2, [100]_2\}$. We interpret a number $[b_3b_2b_1]_2$ as the SAT variable assignment with $v_i\mapsto b_i$. Hence, $3=[011]_2$ represents an assignment that satisfies $v_1\vee \lnot v_3$ and $[100]_2$ represents an assignment that does not satisfy $v_1\vee \lnot v_3$. The intended meaning is as follows. Roughly speaking, the first three constraints check whether the assignment of $y_0$ satisfies the clause by checking whether the respective bit yields a positive literal. For example a bit $b_1=1$ represents assigning $v_1\mapsto 1$ and yields a positive literal $v_1$. We remember a positive literal by increasing $f_i$. The last constraint is feasible iff at least one true literal was found, i.e. iff the assignment satisfies $v_1\vee \lnot v_3$. We access the individual bits of $y_0$ using the remainder of a division by 2, compare with  Table 1. In some sense all three constraints are (slight alterations) of combining a division with remainder constraint type for y with a forward constraint type for f.

With the first constraint we want to evaluate the least significant bit of the assignment for $y_0$. For clause $v_1\vee \lnot v_3$ this means we want to get $f_1>0$ iff $\textrm{parity}(y_0) =1$ as this would indicate a true literal. The constraint can be restated as $4y_0-8y_1 = 3\alpha _0+f_1$ and the variable bounds imply $0\leqslant 3\alpha _0+f_1 \leqslant 6$. If we fix $y_0$, there is only one feasible assignment to satisfy the constraint with $y_{1} = \lfloor y_0/2\rfloor$ and $\alpha _0 = f_1 = \textrm{parity}(y_0)$.

• For $y_0=3$ we get $y_1 = 1$ and $\alpha _0 = f_1 = \textrm{parity}(y_0) =1$.

• For $y_0=4$ we get $y_1 = 2$ and $\alpha _0 = f_1 = \textrm{parity}(y_0) =0$.

The clause $v_1\vee \lnot v_3$ does not rely on the assignment for $v_2$. Hence, the goal for the second constraint is to assign $y_2$ to $y_1$ divided by two, ignore the remainder, and forward the value of $f_1$ to $f_2$. This is exactly the combination of the respective constraint types as stated in  Table 1. The constraint uses the forwarded variables $f_1$ and $y_1$. For a fixed $y_1$, a solution to $4y_1 - 8y_2 = f_2-f_1+4\alpha _1$ within the variable bounds requires $y_2=\lfloor y_1/2\rfloor$, $f_2=f_1$, and $\alpha _1 = \textrm{parity}(y_1)$.

• For $(f_1,y_1)=(1,1)$ we get $y_1 = 0$, $f_2 = f_1 =1$, and $\alpha _1= \textrm{parity}(y_1) =1$.

• For $(f_1,y_1)=(0,2)$ we get $y_1 = 1$, $f_2 = f_1 =0$, and $\alpha _1= \textrm{parity}(y_1) =0$.

The clause contains the negative literal $\lnot v_3$. Hence, the third constraint aims to increase $f_3$ compared to $f_2$ iff the third bit of $y_0$ is 0 and hence the literal $\lnot v_3$ is true. The constraint uses the forwarded variables $f_2$ and $y_2$. If $(f_2,y_2)=(1,0)$ we get that the constraint is $\alpha '_2 - 5\alpha _2 - 8y_3-f_3=-1$. This implies $\alpha _2 = y_3 = 0$ due to the variable bounds. The feasible solutions for $(f_2,y_2)=(1,0)$ are thus $(f_3, y_3) \in \{(1,0), (2,0)\}$ since we get $f_3 = \alpha '_2+1$ with $\alpha '_2\in \{0,1\}$.

If $(f_2,y_2)=(0,1)$ we get that the constraint is $\alpha '_2 - 5\alpha _2 - 8y_3-f_3=-4$. This implies $\alpha _2 = 1$ and $y_3 = 0$ due to the variable bounds. The feasible solution for $(f_2,y_2)=(0,1)$ is thus $(f_3, y_3) \in \{(0,0)\}$ since we get $f_3 = \alpha '_2-1$ with $\alpha '_2\in \{0,1\}$ and $f_3>0$ by its lower bound.

Considering the first three constraints with the starting assignment of $y_0=3$ yielded the two feasible assignments for $f_3 \in \{1,2\}$ and the starting assignment $y_0=4$ yielded one feasible assignment for $f_3 \in \{0\}$. The fourth constraint is feasible iff $f_3 >0$. This means, if we start with $y_0=3$ representing a satisfying assignment of $v_1\vee \lnot v_3$, the path-like IP is also feasible. If we start with $y_0=4$ representing an assignment that does not satisfy $v_1\vee \lnot v_3$, then also the path-like IP is not feasible.