Embedding of linear programming in a simulated annealing algorithm for solving a mixed integer production planning problem (Q1917905)

Let \(x_j(j=1,2, \dots,I)\) be binary variables, \(y_{ij}\in \{0,1,2,3,4\}\) \((i,j=1,2, \dots, I)\), \(z_j\geq 0\) be continuous variables. Let us consider the problem to minimize the function \[ C_f \left(\sum^I_{j=1} x_j \right)+ 1.05 C_t \left(\sum^I_{j=1} z_j \right) \] subject to \(\sum^I_{j=1} z_jy_{ij} \geq N_i\), \(i=1, \dots, I\), \(\sum^I_{i=1} y_{ij} =4x_j\), \(j=1, \dots, I\), \(z_i \leq Mx_j\), \(j=1, \dots, I\), where \(M= \max_{i=1, \dots, I} N_i\). Such a problem, with \(I\) of the order 12 and \(C_f\ll C_t\), arises in the publishing industry, namely when one wants to group some different book covers on the same offset plate in order to print them simultaneously. In that case, \(I\) denotes the number of different covers to be printed, \(i=1, \dots,I\) denotes the index of a cover, \(j=1, \dots,I\) the index of a plate (each one may contain four covers, not necessarily of the same book, but in the case \(I\) plates must be used), \(x_j=1\) when the \(j\)-th plate is used, \(y_{ij}\) denotes the number of times cover \(i\) is present on the plate \(j\). \(z_j\) represents the number printed of plate \(j\). \(C_f\) is the unit cost of a plate and \(C_t\) is the unit cost of a sheet of paper. Finally, the \(N_i\)s are the number of needed copies of the \(i\)-th cover. The problem, naturally, consists in the minimization of the global cost. Its constraints of the first type are, unfortunately, nonlinear; there is no commercial software solving efficiently such nonlinear mixed integer programming problems. One may also obtain a linear formulation of the problem, but at the cost of enormous increase of the number of variables and constraints: there are 1176 variables and 1236 constraints in the case \(I=12\). That's why the authors propose another approach, namely a combination of a general heuristic, e.g. the simulated annealing [see \textit{M. Pirlot}, Belg. J. Oper. Res. Stat. Comput. Sci. 32, No. 1-2, 7-67 (1992; Zbl 0768.90062)] with linear programming routine, called at each step of the simulated annealing process. Just the same approach can be applied to any mixed integer linear problem. The paper describes some practical tests of the approach and results of experimental calculations.