Search

Statistical parity metrics have been widely studied and endorsed in the AI community as a means of achieving fairness, but they suffer from at least two weaknesses. They disregard the actual welfare consequences of decisions and may therefore fail to achieve the kind of fairness that is desired for disadvantaged groups. In addition, they are often incompatible with each other, and there is no convincing justification for selecting one rather than another. This paper explores whether a broader conception of social justice, based on optimizing a social welfare function (SWF), can be useful for assessing various definitions of parity. We focus on the well-known alpha fairness SWF, which has been defended by axiomatic and bargaining arguments over a period of 70 years. We analyze the optimal solution and show that it can justify demographic parity or equalized odds under certain conditions, but frequently requires a departure from these types of parity. In addition, we find that predictive rate parity is of limited usefulness. These results suggest that optimization theory can shed light on the intensely discussed question of how to achieve group fairness in AI.

Geographical considerations such as contiguity and compactness are necessary elements of political districting in practice. Yet an analysis of the problem without such constraints yields mathematical insights that can inform real-world model construction. In particular, it clarifies the sharp contrast between proportionality and competitiveness and how it might be overcome in a properly formulated objective function. It also reveals serious weaknesses of the much-discussed efficiency gap as a criterion for gerrymandering.

We propose social welfare optimization as a general paradigm for formalizing fairness in AI systems. We argue that optimization models allow formulation of a wide range of fairness criteria as social welfare functions, while enabling AI to take advantage of highly advanced solution technology. Rather than attempting to reduce bias between selected groups, one can achieve equity across all groups by incorporating fairness into the social welfare function. This also allows a fuller accounting of the welfare of the individuals involved. We show how to integrate social welfare optimization with both rule-based AI and machine learning, using either an in-processing or a post-processing approach. We present empirical results from a case study as a preliminary examination of the validity and potential of these integration strategies., Comment: 23 pages, 3 figures

We apply logic-based Benders decomposition (LBBD) to two-stage stochastic planning and scheduling problems in which the second-stage is a scheduling task. We solve the master problem with mixed integer/linear programming and the subproblem with constraint programming. As Benders cuts, we use simple nogood cuts as well as analytical logic-based cuts we develop for this application. We find that LBBD is computationally superior to the integer L-shaped method, with a branch-and-check variant of LBBD faster by several orders of magnitude, allowing significantly larger instances to be solved. This is due primarily to computational overhead incurred by the integer L-shaped method while generating classical Benders cuts from a continuous relaxation of an integer programming subproblem. To our knowledge, this is the first application of LBBD to two-stage stochastic optimization with a scheduling second-stage problem, and the first comparison of LBBD with the integer \mbox{L-shaped} method. The results suggest that LBBD could be a promising approach to other stochastic and robust optimization problems with integer or combinatorial recourse.

Optimization models generally aim for efficiency by maximizing total benefit or minimizing cost. Yet a trade-off between fairness and efficiency is an important element of many practical decisions. We propose a principled and practical method for balancing these two criteria in an optimization model. Following a critical assessment of existing schemes, we define a set of social welfare functions (SWFs) that combine Rawlsian leximax fairness and utilitarianism and overcome some of the weaknesses of previous approaches. In particular, we regulate the equity/efficiency trade-off with a single parameter that has a meaningful interpretation in practical contexts. We formulate the SWFs using mixed integer constraints and sequentially maximize them subject to constraints that define the problem at hand. After providing practical step-by-step instructions for implementation, we demonstrate the method on problems of realistic size involving healthcare resource allocation and disaster preparation. The solution times are modest, ranging from a fraction of a second to 18 seconds for a given value of the trade-off parameter.

Logic-based Benders decomposition (LBBD) is a substantial generalization of classical Benders decomposition that, in principle, allows the subproblem to be any optimization problem rather than specifically a linear or nonlinear programming problem. It is amenable to a wide variety large-scale problems that decouple or otherwise simplify when certain decision variables are fixed. This chapter presents the basic theory of LBBD and explains how classical Benders decomposition is a special case. It also describes branch and check, a variant of LBBD that solves the master problem only once. It illustrates in detail how Benders cuts and subproblem relaxations can be developed for some planning and scheduling problems. It then describes the role of LBBD in three large-scale case studies. The chapter concludes with an extensive survey of the LBBD literature, organized by problem domain, to allow the reader to explore how Benders cuts have been developed for a wide range of applications.

We present a general method for obtaining strong bounds for discrete optimization problems that is based on a concept of branching duality. It can be applied when no useful integer programming model is available, and we illustrate this with the minimum bandwidth problem. The method strengthens a known bound for a given problem by formulating a dual problem whose feasible solutions are partial branching trees. It solves the dual problem with a "worst-bound" local search heuristic that explores neighboring partial trees. After proving some optimality properties of the heuristic, we show that it substantially improves known combinatorial bounds for the minimum bandwidth problem with a modest amount of computation. It also obtains significantly tighter bounds than depth-first and breadth-first branching, demonstrating that the dual perspective can lead to better branching strategies when the object is to find valid bounds., Comment: 18 figures

We introduce a general method for relaxing decision diagrams that allows one to bound job sequencing problems by solving a Lagrangian dual problem on a relaxed diagram. We also provide guidelines for identifying problems for which this approach can result in useful bounds. These same guidelines can be applied to bounding deterministic dynamic programming problems in general, since decision diagrams rely on DP formulations. Computational tests show that \mbox{Lagrangian} relaxation on a decision diagram can yield very tight bounds for certain classes of hard job sequencing problems. For example, it proves for the first time that the best known solutions for Biskup-Feldman instances are within a small fraction of 1% of the optimal value, and sometimes optimal., Comment: 2 figures

The hamiltonian circuit polytope is the convex hull of feasible solutions for the circuit constraint, which provides a succinct formulation of the traveling salesman and other sequencing problems. We study the polytope by establishing its dimension, developing tools for the identification of facets, and using these tools to derive several families of facets. The tools include necessary and sufficient conditions for an inequality to be facet defining, and an algorithm for generating all undominated circuits. We use a novel approach to identifying families of facet-defining inequalities, based on the structure of variable indices rather than on subgraphs such as combs or subtours. This leads to our main result, a hierarchy of families of facet-defining inequalities and polynomial-time separation algorithms for them.

Concepts of consistency have long played a key role in constraint programming but never developed in integer programming (IP). Consistency nonetheless plays a role in IP as well. For example, cutting planes can reduce backtracking by achieving various forms of consistency as well as by tightening the linear programming (LP) relaxation. We introduce a type of consistency that is particularly suited for 0-1 programming and develop the associated theory. We define a 0-1 constraint set as LP-consistent when any partial assignment that is consistent with its linear programming relaxation is consistent with the original 0-1 constraint set. We prove basic properties of LP-consistency, including its relationship with Chvatal-Gomory cuts and the integer hull. We show that a weak form of LP-consistency can reduce or eliminate backtracking in a way analogous to k-consistency but is easier to achieve. In so doing, we identify a class of valid inequalities that can be more effective than traditional cutting planes at cutting off infeasible 0-1 partial assignments.