# Production Optimization in a Grain Facility through Mixed-Integer Linear Programming +
## 4 Problem Complexity and Lower Bounds
### NP-Completeness  
This subsection presents a demonstration of the NP-completeness of the decision problem of determining if there is a solution whose cost is smaller than a given value \(C\). Let this decision problem be called \(\mathrm{SOJA}(C)\). The first important remark is that \(\mathrm{SOJA}(C)\) is in \(NP\), since it takes a polynomial time to verify the feasibility of a solution. Therefore, it is enough to polynomially reduce \(\mathrm{SOJA}(C)\) to any NP-Complete problem. Let the chosen problem be the PARTITION problem, i.e., the one of deciding, given positive integers \(n_{1},\ldots,n_{k}\), whether there is a subset of them that sum \(h:=(n_{1}+\cdots+n_{k})/2\), i.e, if there is a subset \(S\subset\{1,\cdots,k\}\) of the indices such that Equation (17) holds.  
\[\sum_{i\in S}n_{i}=\sum_{i\
ot\in S}n_{i}=h. \tag{17}\]  
We consider two production lines of equal productivity, i.e., \(\pi_{1}=\pi_{2}=1\) tons per week; \(k\) product types; equal week withdrawals for all the products, i.e., \(r=1\) and \(S_{i}^{\prime}=T+h+1\) weeks; demands \(d_{i}^{1}=d_{i}=n_{i}\) with \(i=1,\cdots,k\); equal cleaning times \(L_{1}=L_{2}=1/k\) and cleaning cost \(R>0\). Next it is proven that if PARTITION has a solution, then \(\mathrm{SOJA}(C)\) has solution if and only if \(C\geq 2h+R(k-2)\); and that conversely, if there exists a solution to \(\mathrm{SOJA}(2h+R(k-2))\), then PARTITION has a solution.  
The following statement holds: if line 1 produces \(a_{0},\cdots,a_{k_{1}}\) tons of products of type \(t_{0},\cdots,t_{k_{1}}\) with \(t_{i}\
eq t_{i+1}\) and line 2 produces \(b_{0},\cdots,b_{k_{2}}\) tons of products of type \(t_{0}^{\prime},\cdots,t_{k_{2}}^{\prime}\) with \(t_{i}^{\prime}\
eq t_{i+1}^{\prime}\), then the total number of cleaning is \(k_{1}+k_{2}\) and the total time \(T^{\prime}\) spend on production is given by Equation (18).  
\[T^{\prime}=\max\biggl{\{}\frac{k_{1}}{k}+A,\frac{k_{2}}{k}+B\biggr{\}}\quad \text{with}\quad A=\sum_{i=0}^{k_{1}}a_{i},\quad\text{and}\quad B=\sum_{i=0}^ {k_{2}}b_{i}. \tag{18}\]  
The overall cost of production is \(\hat{C}=2h+(k_{1}+k_{2})R\), which is at least \(2h+(k-2)R\).  
For proving that if PARTITION has a solution, then \(\mathrm{SOJA}(C)\) has a solution of cost \(2h+R(k-2)\), consider the solution \(S\) to PARTITION, with parameters \(k_{1}=|S|-1\), \(k_{2}=k-k_{1}-2\), \(a_{i}=n_{i}\) for \(i\in A\) and \(b_{i}=n_{i}\) for \(i\in S^{c}\). With this assignment, the total time is given by Equation (19), so the solution is feasible.  
\[T^{\prime}=\max\biggl{\{}\frac{k_{1}}{k}+h,\frac{k_{2}}{k}+h\biggr{\}}=h+\max \biggl{\{}\frac{k_{1}}{k},\frac{k_{2}}{k}\biggr{\}}\leq h+\frac{k-2}{k}<h+1. \tag{19}\]  
The overall cost \(\hat{C}=2h+(k_{1}+k_{2})R=2h+(k-2)R\) is optimal, so \(\mathrm{SOJA}(C)\) has solution if and only if \(\hat{C}\leq C\).  
Conversely, if \(\mathrm{SOJA}(2h+(k-2)R)\) has a solution, then PARTITION has as well. Indeed, first observe that \(k_{1}+k_{2}=k-2\) since \(k_{1}+k_{2}\geq k-1\) and the cost is at least \(2h+(k-1)R\). Therefore, since the number of cleanings \((k-2)\) is the minimum possible, all product types should be different, and for each \(i\) there exists one and only one \(j_{i}\) such that \(a_{i}=n_{j_{i}}\), and the same for \(b_{i}\). Finally, since the solution is feasible, then \(A+k_{1}/k<h+1\) and \(B+k_{2}/k<h+1\), thus \(A<h+(1-k_{1}/k)<h+1\) and \(B<h+(1-k_{2}/k)<h+1\), i.e., \(A\leq h\) and \(B\leq h\). However, \(A+B=2h\), then \(A=B=h\), and PARTITION has solution \(S=\{j_{i}:i=0,\cdots,k_{1}\}\).