An Efficient Primal-Dual Algorithm for Fair Combinatorial Optimization Problems

Viet Hung Nguyen, Paul Weng

TL;DR

This paper introduces a fast primal-dual heuristic for "fair" combinatorial optimization, using the Generalized Gini Index (GGI) to ensure balanced outcomes across different agents or criteria. By leveraging Lagrangian decomposition, the authors' algorithm achieves near-optimal results (within 0.3% of the true optimum) while running orders of magnitude faster than commercial integer programming solvers.

What Problem Does This Paper Address?

In classic combinatorial optimization—think of the Traveling Salesman Problem or finding a perfect matching in a graph—we typically aim to maximize the sum of weights. However, the sum is a "blind" aggregator: it doesn't care if one agent gets a massive utility while everyone else gets zero. In multi-agent systems or multi-criteria decision-making, this lack of "fairness" is a dealbreaker.

To fix this, researchers use inequality measures like the Generalized Gini Index (GGI). GGI rewards "balanced" distributions where resources are spread more equitably. The catch? GGI is non-linear. While you can use mathematical tricks to turn a GGI-based problem into a linear integer program (IP), standard solvers like CPLEX or Gurobi struggle as the problem size grows, often taking hours to solve even relatively small instances. The authors address this computational bottleneck.

Methods

The authors propose a heuristic called AlterOpt, based on a primal-dual approach using Lagrangian decomposition.

  1. Linearization: They start with a known technique to linearize the GGI objective using "Lorenz components," which represent the cumulative values of the $k$ smallest utilities.
  2. Lagrangian Relaxation: They relax the difficult fairness constraints, moving them into the objective function with Lagrangian multipliers ($\lambda$).
  3. The Iterative Loop: The algorithm alternates between two steps:
  4. Primal Step: For a fixed set of multipliers, the problem simplifies into a standard weighted version of the original combinatorial problem (e.g., a standard maximum weight matching). This can often be solved very efficiently using specialized algorithms like the Blossom algorithm.
  5. Dual Step: They update the multipliers using a projected sub-gradient method. A key innovation here is an efficient $O(n^3)$ method for projecting these multipliers onto "capped simplices," which keeps the search space constrained and computationally tractable.

Datasets

The authors evaluated their algorithm on two primary types of problems:

  • Fair Assignment: Bipartite matching problems where $n$ tasks are assigned to $n$ agents.
  • Fair General Matching: Matching problems on complete graphs.

They generated "hard" random instances for these problems. In these instances, agents' preferences are positively correlated (meaning many agents want the same items), which makes finding a "fair" solution significantly more difficult than in uncorrelated cases.

Key Insights and Ideas

  • Weights as Fairness Adjusters: The algorithm essentially treats the dual variables as "modified weights." By iteratively adjusting these weights, the algorithm "nudges" the standard solver to pick edges that contribute to a fairer global distribution.
  • Efficiency through Structure: Instead of treating the fair optimization as a generic black-box IP, the authors exploit the fact that the underlying combinatorial problem (like matching) has a structure that is easy to solve once the fairness constraints are relaxed.
  • Theoretical Guarantees: The paper provides an optimality condition (Theorem 1) and a theoretical approximation ratio (Theorem 2) that bounds how far the standard "max-sum" solution can be from the "fair" optimal solution.

Key Results

The numerical results demonstrate a massive disparity in performance between the proposed heuristic and exact solvers:

  • Speed: For a matching problem with 100 vertices (v10-50), CPLEX took nearly 30,000 seconds (over 8 hours) to find the optimum. The AlterOpt heuristic found a solution in just 2.48 seconds.
  • Quality: Despite being a heuristic, the "optimality gap" (the distance from the true optimal value) was remarkably small—typically less than 0.3% for assignment problems and less than 0.1% for general matching.
  • Scalability: While CPLEX's runtime increased exponentially with problem size, the authors' method scaled much more gracefully, appearing to increase roughly linearly.

Limitations and Future Work

The current study focuses on base problems that are solvable in polynomial time (like matching). However, many combinatorial problems are NP-hard even in their standard "max-sum" versions (like the Traveling Salesman Problem). The authors acknowledge that integrating their heuristic with approximation algorithms for these NP-hard problems is a necessary next step.

Additionally, they suggest exploring other linearization techniques and different update rules for the Lagrangian multipliers to further tighten the theoretical bounds and improve performance on even more complex constraints.

Summary updated

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 [21]. 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%.
BibTeX
@inproceedings{nguyen2017efficient,
  author = {Viet Hung Nguyen and Paul Weng},
  title = {{An Efficient Primal-Dual Algorithm for Fair Combinatorial Optimization Problems}},
  booktitle = {COCOA},
  year = {2017},
  url = {https://openreview.net/forum?id=WsYN2lNZvV},
}

Loading related content...

Figure