# Knapsack Balancing via Multiobjectivization
## 1 Introduction and Motivation  
The knapsack problem is one of the best studied combinatorial optimization problems (see, e.g., [1, 2]). It is defined as follows: Given a set \(N:=\{1,\ldots,n\}\) of items and a knapsack with a maximal weight \(C\), each item \(i,\ i=1,\ldots,n\), is characterized by its profit \(p_{i}>0\) and weight \(w_{i}>0\). A subset \(S^{\circ}\) of items that together are not heavier than \(C\) and provide the highest sum of profits is to be determined. This problem can be formulated as a Linear Binary Programming (LBP) problem as follows:  
\[ \begin{array}{ll}\mathcal{S}\mathit{um}\ \mathrm{KP}:&\max\quad\mathcal{S} \mathit{um}(x):=\sum_{i=1}^{n}p_{i}x_{i}\\ &\mathrm{s.t.}\quad\quad x\in X_{0}:=\{x\mid\sum_{i=1}^{n}w_{i}x_{i}\leq C,\ x_{i}\in\{0,1\},\ i=1,\ldots,n\}.\end{array}  \tag{1}\]  
Many practical decision problems can be modeled as the knapsack problem or one of its variants (see, e.g., [3]). The knapsack problem can also be used as sub-problems of more complex models (see, e.g., [4, 5]). As an illustration, let us assume that a farmer models the production of the farm using the knapsack problem. The farm consists of several lots; each lot can accommodate just one crop, yielding a given profit for a given workload. The problem is to assign crops to lots to maximize the total profit under a limited workload budget. To mitigate risks inherent to agriculture, a _portfolio_ of crops rather than a single crop is advisable. Crops yielding small profits may be not very desirable. Prices of crops yielding high profits may vary significantly. Likewise, serving a collection of crops with low and high workload may rise logistic concerns. In consequence, a balanced crop portfolio is of interest, even if portfolio balancing inevitably deteriorates the optimal total profit as compared to the total profit when balancing is not accounted for. Although the problem can be modeled by a more complex, and perhaps more realistic, formulation, the knapsack problem has the advantage to be rather simple. A mechanism to confine the objective function and/or the constraint coefficient dispersion at the optimal solution while retaining the knapsack problem structural simplicity would be of interest. The example brings us to the issue of knapsack balancing. We can attempt to balance the objective function coefficients, the constraint coefficients, or both at once. In contrast to balancing mechanisms proposed in the literature on combinatorial optimization (see, e.g., [6]), here we propose to balance with the [PERSON] social welfare function that maximizes the product of all quantities that have to be balanced (in the original work of [PERSON] those were individual utilities) ([7]). A distinguishing property of this function is that when the sum of continuous quantities (all positive) is tied to a certain positive value, the maximum of this function is achieved when all quantities are equal. As seen in Figure 1, function \(y_{1}+y_{2}\) equally assesses all three elements (filled discs), as they all are located on the same contour (the solid line), whereas function \(y_{1}\cdot y_{2}\) differentiates them as they are located on two different contours (dashed lines). Moreover, the latter function has a higher value for the element with \(y_{1}=y_{2}\) than for elements with \(y_{1}\
eq y_{2}\). As shown below, in the context of the knapsack problem, this function has plausible properties, both in terms of balancing and computing. We approach the problem of knapsack balancing through a multiobjective problem formulation. Multiobjective formulations offer a framework by which some seemingly hidden aspects of underlying decision problems can be incorporated into optimization models. A single-objective optimization model is multiobjective by keeping the original objective function and adding new objective functions representing the new aspects that are to be considered.