# Production Optimization in a Grain Facility through Mixed-Integer Linear Programming +
## 7 Overall Improvement of Solution Time and Solution Quality Using Pre-Computed Bounds  
This section describes a method for speeding up the resolution time, even improving the quality of the computed solutions, for optimization problems such as the one addressed in this article, using pre-computed bounds. The proposed method is called the \"bounds scheme\" and its rationale is to compute bounds for the decision variables of the problem and using the bounds as constraints in the original problem. Depending on the variables bounded, the method is able to improve the two metrics described in Section 6.1, since adding constraints reduces the solution space to explore. On the one hand, the bounds scheme allows speeding up convergence, considering the total execution time (including the time for computing the bounds and the time for solving the problem with the added constraints). On the other hand, the bounds scheme allows reducing the gap between the objective function value of the best solution found and a lower bound computed by the solver. \begin{table}
\begin{tabular}{l r r r r} \hline \hline  & _Heuristic_ & _Proposed MILP_ & \(\Delta\) & \(\Delta\%\) \\ \hline shifts & 58 & 51 & 7 & 12.1\% \\ cleanings & 34 & 22 & 12 & 35.3\% \\ maximum storage used (tons) & 3666 & 2605 & 1061 & 29.4\% \\ \hline overall cost (monetary units) & 81,070 & 72,625 & 8445 & 10.4\% \\ \hline \hline \end{tabular}
\end{table} 
Table 7: Relevant metrics of the plans computed by the proposed MILP method and the comparison with the heuristic method considered to be a reference baseline. The proposed method is described next. We consider the optimization problem \(P\) defined in Equation (28). \[ \begin{array}{ll}\text{problem }P)&\min&c_{1}x_{1}+\cdots+c_{n}x_{n},\text{ with }c_{i}>0,\\ &\text{subject to}&h(x_{1},\ldots,x_{n})\geq 0.\end{array}  \tag{28}\]  
The bounds scheme consists of two steps. The first step considers the set of ancillary problems \(P_{i}\), with index \(i\) in some subset \(S\subset\{1,\ldots,n\}\), defined in Equation (29). Problems \(P_{i}\) are used to find lower bounds for the values of \(x_{i}\)  
\[ \begin{array}{ll}\text{problem }P_{i})&\min&x_{i},\\ &\text{subject to}&h(x_{1},\ldots,x_{n})\geq 0.\end{array}  \tag{29}\]  
Problems \(P_{i}\) are solved to find solutions \(x_{i}^{*}\), for \(i\in S\). Clearly \(x_{i}^{*}=\min\{x_{i}:h(x_{1},\ldots,x_{n})\geq 0\}\), therefore, \(h(x_{1},\ldots,x_{n})\geq 0\) implies \(x_{i}\geq x_{i}^{*}\) Then, the second step considers the original problem \(P\), but including the new set of \(|S|\) constraints defined by \(C_{i})\;x_{i}\geq x_{i}^{*}\), with \(i\in S\). In case a given problem \(P_{i}\) is not solved to optimality, and just a lower bound \(\hat{x}_{i}\), i.e., \(x_{i}^{*}\geq\hat{x}_{i}\) is found, then the new constrains \(C_{i}\) turns to be \(C_{i}^{\prime})\;x_{i}\geq\hat{x}_{i}\). Since \(h(x_{1},\ldots,x_{n})\geq 0\) implies \(x_{i}\geq\hat{x}_{i}\), then, including the new constraints \(C_{i}^{\prime}\) does not modify the problem \(P\). Summarizing, the new formulation of problem \(P\) is in Equation (30). \[ \begin{array}{ll}\text{problem }P)&\min&c_{1}x_{1}+\cdots+c_{n}x_{n},\\ &\text{subject to}&h(x_{1},\ldots,x_{n})\geq 0,\\ &x_{i}\geq\hat{x}_{i},\;\forall i\in S.\end{array}  \tag{30}\]  
Further improvements are obtained by relaxing some constrains in problem \(P\). When the bounds are computed, the time can be lowered by relaxing the constraints \(h(x_{1},\ldots,x_{n})\geq 0\). This can be done, for instance, setting an unlimited storage capacity, though at the expense of a trade-off regarding the quality of the computed bound. The proposed method is instantiated for the grain production optimization problem addressed in this work. The considered objective function is linear with positive coefficients; thus, it verifies the hypothesis of problem \(P\).