Abstract
We consider a general class of combinatorial optimization problems including among others allocation, multiple knapsack, matching or travelling salesman problems. The standard version of those problems is the maximum weight optimization problem where a sum of values is optimized. However, the sum is not a good aggregation function when the fairness of the distribution of those values (corresponding for example to different agents' utilities or criteria) is important. In this paper, using the generalized Gini index (GGI), a well-known inequality measure, instead of the sum to model fairness, we formulate a new general problem, that we call fair combinatorial optimization. Although GGI is a non-linear aggregating function, a 0,1-linear program (IP) can be formulated for finding a GGI-optimal solution by exploiting a linearization of GGI proposed by Ogryczak and Sliwinski. However, the time spent by commercial solvers (e.g., CPLEX, Gurobi...) for solving (IP) increases very quickly with instances' size and can reach hours even for relatively small-sized ones. As a faster alternative, we propose a heuristic for solving (IP) based on a primal-dual approach using Lagrangian decomposition. We demonstrate the efficiency of our method by evaluating it against the exact solution of (IP) by CPLEX on several fair optimization problems related to matching. The numerical results show that our method outputs in a very short time efficient solutions giving lower bounds that CPLEX may take several orders of magnitude longer to obtain. Moreover, for instances for which we know the optimal value, these solutions are quasi-optimal with optimality gap less than 0.3%.
Introduction
In classic combinatorial optimization—such as the Traveling Salesman Problem or finding a perfect matching in a graph—the standard objective is to maximize the sum of weights. However, the sum is a "blind" aggregator that does not account for how utility is distributed among different agents or criteria. In multi-agent systems, this lack of fairness can lead to highly inequitable outcomes.
To address this, researchers use inequality measures like the Generalized Gini Index (GGI). GGI rewards balanced distributions where resources are spread more equitably. While GGI can be linearized into an integer program (IP), standard commercial solvers like CPLEX struggle as problem sizes grow, often taking hours to solve relatively small instances. This paper introduces a fast primal-dual heuristic to overcome this computational bottleneck.
Methodology
The authors propose a heuristic called AlterOpt, which leverages a primal-dual approach based on Lagrangian decomposition.
The algorithm operates through several key steps:
- Linearization: The GGI objective is linearized using "Lorenz components," representing the cumulative values of the $k$ smallest utilities.
- Lagrangian Relaxation: Difficult fairness constraints are moved into the objective function using Lagrangian multipliers ($\lambda$).
- Iterative Optimization: The algorithm alternates between a Primal Step, where the problem simplifies into a standard weighted combinatorial problem (solvable via efficient algorithms like the Blossom algorithm), and a Dual Step, which updates multipliers using a projected sub-gradient method.
A key innovation is an efficient $O(n^3)$ method for projecting multipliers onto "capped simplices," keeping the search space computationally tractable.
Experimental Results
The algorithm was evaluated on fair assignment and fair general matching problems using "hard" random instances where agents' preferences are positively correlated.
Performance Comparison
- Speed: For a matching problem with 100 vertices, CPLEX required nearly 30,000 seconds (over 8 hours) to find the optimum. In contrast, the AlterOpt heuristic found a solution in just 2.48 seconds.
- Solution Quality: Despite being a heuristic, the optimality gap was remarkably small—typically less than 0.3% for assignment problems and less than 0.1% for general matching.
- Scalability: While CPLEX's runtime increases exponentially, the proposed method scales roughly linearly with problem size.
Key Insights and Theoretical Guarantees
- Weights as Fairness Adjusters: The dual variables effectively act as modified weights, "nudging" the standard solver to select edges that contribute to a fairer global distribution.
- Theoretical Bounds: The paper establishes an optimality condition (Theorem 1) and a theoretical approximation ratio (Theorem 2) that bounds the distance between the standard max-sum solution and the fair optimal solution.
Conclusion
AlterOpt provides a highly efficient alternative for fair combinatorial optimization, achieving near-optimal results in a fraction of the time required by exact solvers. Future research will focus on integrating this heuristic with approximation algorithms for NP-hard base problems, such as the Traveling Salesman Problem, and exploring alternative update rules for Lagrangian multipliers.
Summary updated