I have already posted this question [here](https://math.stackexchange.com/questions/2129590/show-0-1-knapsack-is-polynomially-reducible-to-this-problem) 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!



Show $0-1$ Knapsack is polynomially reducible to this problem
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\}.\]


