Show $0-1$ Knapsack is polynomially reducible to this problem

Question

I have already posted this question here but have not received an answer so I am cross-posting with hope to reach a larger amount of mathematicians:

Let $T=\{1,\cdots,n\}$ and consider the following mixed integer linear problem $P$: $$ \max \sum_{t\in T} x_{t} $$ subject to $$ I_t=I_{t-1}+a_{t}-x_{t}\quad t\in T\\ I_t \le M_t(1-y_t)\quad t\in T\\ x_t \le M_ty_t \quad t\in T\\ I_t,x_t \ge 0 \quad t\in T\\ y_t \in \{0,1\}\quad t\in T $$ $I_0$ and $a_t$ are given parameters in $\mathbb{R}^+$ and $M_t$ is a large constant. This problem is quite similar to a lot-sizing problem with capacities $M_t$, production variables $x_t$, demands $a_t$, in which we have constraints $I_t=I_{t-1}\color{red}{-}a_{t}\color{red}{+}x_{t}$ (but no constraints $I_t \le M_t(1-y_t)$).

I would like to show that $P$ is NP-hard. The decision version of $P$ is clearly in NP. I am trying to show that the binary knapsack problem reduces to $P$ in polynomial time.

---

My try: I consider the following knapsack problem : $$ \min\{ \sum_{t \in T}c_t y_t\;|\;\sum_{t\in T}v_t y_t \ge b, \; y_t\in \{0,1\} \} $$ and solve an instance of $P$ with:

• $M_t = v_t\quad \forall t \in T$
• $a_t =0 \quad \forall t=1,...,n-1$
• $a_n = b$
• $I_0 = 0$

Variables $I_t$ can be eliminated by noting that $$ I_t = I_0 + \sum_{j=1}^t(a_j-x_j) $$ and so the decision version of $P$ is equivalent to finding a feasible solution of $$ I_0 + \sum_{j=1}^t(a_j-x_j) \ge 0 \quad t \in T\\ I_0 + \sum_{j=1}^t(a_j-x_j) \le M_t(1-y_t) \quad t \in T \\ x_t \le M_ty_t \quad t\in T\\ x_t \ge 0 \quad t\in T\\ y_t \in \{0,1\}\quad t\in T $$ With the chosen data, we get: $$ b-\sum_{j=1}^t x_j \ge 0 \quad t \in T\\ b- \sum_{j=1}^t x_j \le v_t(1-y_t) \quad t \in T \\ x_t \le v_t y_t \quad t\in T\\ x_t \ge 0 \quad t\in T\\ y_t \in \{0,1\}\quad t\in T $$

Now, if I were able to show that $b-\sum_{j=1}^t x_j = 0 \; \forall t \in T$, by combining it with $x_t \le v_t y_t \; \forall t \in T$, I would get $$ b \le \sum_{t\in T} v_t y_t $$ which would finish the proof. For every $t\in T$ such that $y_t =1$ it is the case since the equations become $b-\sum_{j=1}^t x_j \ge 0$ and $b-\sum_{j=1}^t x_j \le 0$.

---

1. Is there any way to prove this this way? How can I deal with the cases for which $y_t =0$?
2. I am pretty sure that if $M_t=M\; \; \forall t \in T$, then $P$ is no longer NP-hard. Can anyone confirm this?

Another intuitive approach would be to reduce the lot sizing problem to $P$, but I did not get very far. Any help is appreciated!

Answer 1

Your constraints imply that \begin{align*} y_t=0 &\implies x_t=0\text{ and }I_t=I_{t-1}+a_t\\ y_t=1 &\implies I_t=0\text{ and }x_t=I_{t-1}+a_t \end{align*} As a consequence, if the problem is feasible then the objective value is $a_0+a_1+\cdots+a_T$ for every feasible solution. Feasibility can be decided by looking for a path from $0$ to $T$ in the following digraph $G=(V,A)$. The node set is $V=\{0,1,\ldots,T\}$ and the arc set is \begin{multline*} A=\{(0,j)\ :\ I_0+a_1+\cdots+a_t\leqslant M_t\text{ for all }t\in\{1,\ldots,j\}\}\\ \cup\{(i,j)\ :\ 1\leqslant i<j\leqslant T,\ a_{i+1}+\cdots+a_t\leqslant M_t\text{ for all }t\in\{i+1,\ldots,j\}\} \end{multline*} There is a one-to-one correspondence between feasible solutions for your problem and paths $(i_0=0,i_1,\ldots,i_k=T)$ given by \[y_t=1\iff t\in\{i_1,\ldots,i_k\}.\]