# Knapsack Balancing via Multiobjectivization
## 3 Balancing Knapsacks by \(\mathcal{P}rod^{p}\) Objective Function  
The knapsack problem with the product objective function is formulated as the following NLBP problem:  
\[\mathcal{P}rod^{p}\ \mathrm{KP}:\quad\max \mathcal{P}rod^{p}(x)\] (4) s.t. \[x\in X_{0}\,.\]  
In \(\mathcal{P}rod^{p}\ \mathrm{KP}\), a subset \(S\subseteq N\) of items with the most balanced profits is sought by means of maximizing \(\mathcal{P}rod^{p}(x)\). The following example illustrates the effect of item profits balancing at the optimal solution produced by \(\mathcal{P}rod^{p}(x)\) objective function.  
We demonstrate the effect of item profits balancing produced by \(\mathcal{P}rod^{p}(x)\) objective function by the example with profits and weights given in Table 1 (\(n=20\)), for two values of \(C\) (the right-hand side of the constraint), namely \(\mathrm{C}=550\) and \(\mathrm{C}=300\).  
To measure the balance of item profits at optimal solutions (\(x^{opt}\)), we use the sum of squared deviations from their mean (merits of this function in the context of combinatorial optimization are discussed in, already cited, [6]), namely  
\[L_{2}\text{-}DEV\big{(}I(x^{opt})\big{)}:=\sum_{i\in I(x^{opt})}(p_{i}-\mu)^{ 2}\,, \tag{5}\]  
where \(I(x^{opt})=\{i\mid x_{i}^{opt}=1\}\), and mean \(\mu\) is calculated over \(p_{i}\), \(i\in I(x^{opt})\).  
\(L_{2}\text{-}DEV(\cdot)\) is a natural dispersion measure but we cannot use it as an objective function because \(a\). it is nonlinear, \(b\). \(\mu\) is a function of \(x\), and we intend to stay within the class of mixed-integer linear optimization problems. To this aim, \(L_{2}\text{-}DEV(\cdot)\) can be only calculated after the optimization terminates.  
\(\mathrm{C}=550\). The optimal solution to \(\mathcal{P}rod^{p}\ \mathrm{KP}\):  
\(x^{opt\_prod}=(1,1,1,1,0,1,1,1,1,0,1,1,0,1,1,1,1,1,0)\),  
_profits of items selected to \(x^{opt\_prod}\):  
\(p^{opt\_prod}:=\{100,220,90,400,400,205,120,160,580,140,100,650,320,480,80,6 0\}\),  
\(L_{2}\text{-}DEV(I(x^{opt\_prod}))=546635.937\) (further on, we round all numbers to the third decimal place).  
\begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline  & & & & & & \(i=1,\dots,10\) & & & & \\ \hline \(p_{i}\) & 100 & 220 & 90 & 400 & 300 & 400 & 205 & 120 & 160 & 580 \\ \hline \(w_{i}\) & 8 & 24 & 13 & 80 & 70 & 80 & 45 & 15 & 28 & 90 \\ \hline  & & & & &  
where \(\lambda_{l}>0\), \(l=1,\ldots,k,\ e^{k}=(1,1,\ldots,1),\ y_{l}^{*}=\hat{y}_{l}+\varepsilon\), \(\hat{y}_{l}=\max_{x\in X_{0}}f_{l}(x)\), \(l=1,\ldots,k\), \(\varepsilon>0\), and \(\rho\) is a positive \"sufficiently small\" number. We assume that \(\hat{y}_{l}<\infty,\ l=1,\ldots,k\).  
The necessity of resorting to the Chebyshev scalarization instead of the simpler and much more popular linear scalarization, i.e., the weighted sum of the objective functions, comes from that the former can derive any Pareto optimal solution, whereas the latter can derive, in general, only a subset of them.  
The linearized version of problem (7) has the following form.  
\[\begin{array}{ll}\min&s\\ \text{s.t.}&s\geq\lambda_{l}(y_{l}^{*}-f_{l}(x))+\rho e^{k}(y^{*}-f(x)),\ \ l=1,\ldots,k,\\ &x\in X_{0}\,.\end{array} \tag{8}\]  
In particular, if functions \(f_{l}(x),\ l=1,\ldots,k\), are linear and the definition of \(X_{0}\) is consistent with the mixed-integer linear class of problems, then the problem (8) remains linear or mixed-integer linear or integer linear. In the following, we will assume that Pareto optimal solutions are computed by solving problem (8) with varying \(\lambda=(\lambda_{1},...,\lambda_{k})\). Given \(\lambda\), \(x^{\mathcal{P}_{opt}}(\lambda)\) denotes the Pareto optimal solution designated by \(\lambda\), that is a solution to problem (7) with that \(\lambda\).