Bin packing with load fairness across the bins

Question

The bin pack problem denotes the process of assigning a set of n items into a minimal number of bins of capacity c. It can be simply formulated as an ILP as per the below description:

My question is : how to express an additional constraint in the ILP formulation such that the load on the used bins is as much as possible balanced or fair across the used bins.

Thank you.

Answer 1

You could use minimizing the sum of absolute deviations approach.

Minimizing the sum of absolute deviations

Let deviations be represented by $$\epsilon_i = Y_i - \sum_{j} X_{ji}b_i,$$ where $i$ is the $i^{th}$ observation, $\epsilon_i$ gives the deviation, $Y_i$ is an observation. To minimize the deviation, the problem is formulated in a basic form as: $$\ Min \sum_{i} |\epsilon_i|$$ as the objective function, and linear constraints are $$\ s.t. \epsilon_i + \sum_{j}X_{ji}b_i=Y_i \text{ } \forall i, \ \epsilon_i, b_i \in \mathbb{R} $$

See primary source: https://optimization.mccormick.northwestern.edu/index.php/Optimization_with_absolute_values for details on how to linearize this.

Answer 2

The first question you need to address is whether the fairness aspect will be handled as a constraint or as a second criterion (objective). For convenience, assume we have added continuous variables $z_j$ representing the load in bin $j.$

If you try to make it a constraint, one approach is to add constraints of the form $$L y_j \le z_j \le U y_j$$ where $L$ and $U$ are lower and upper limits on what you would consider to be a "fair" load. The problem is that you need to guess values for $L$ and $U,$ and if you make the range too tight you may force the solution to use more bins that it would need (or, worse, make the problem infeasible). You can also add constraints that limit the absolute difference between $z_j$ and $z_k$ for every $j\neq k,$ but you run into the same issues with guessing appropriate limits.

If you make it a second objective, then you need to decided how you will measure evenness of loads (for instance, by taking the difference between the largest and smallest load), and then decide how to prioritize the two (possibly competing objectives). The "preemptive" approach is to solve two problems. First, solve the bin packing problem without regard to fairness. Once you know the minimum number of bins to use, add a constraint limiting you to that many bins, change the objective to maximizing your fairness measure, and solve again. As an alternative to the preemptive approach, the "weighted" approach adds a measure of unfairness to the objective function, multiplied by some positive weight factor. You now solve a problem that minimizes a combination of bin count and unfairness, with the weight factor determining how much emphasis goes into reducing the bin count and how much goes into making the loads fairer.