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!


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\}.\]

  • $\begingroup$ Thanks. So after all the problem is not NP-hard! $\endgroup$ – Kuifje Feb 7 '17 at 13:52

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.