Identifying optimal basic feasible solutions to linear programming problems is a critical task for mixed integer programming and other applications. The crossover method, which aims at deriving an optimal extreme point from a suboptimal solution (the output of a starting method such as interior-point methods or first-order methods), is crucial in this process. This method, compared with the starting method, frequently represents the primary computational bottleneck in practical applications. We propose approaches to overcome this bottleneck by exploiting problem characteristics and implementing customized strategies. For problems arising from network applications and exhibiting network structures, we take advantage of the graph structure of the problem and the tree structure of the optimal solutions. Based on these structures, we propose a tree-based crossover method, aiming to recovering basic solutions by identifying nearby spanning tree structures. For general linear programs, we propose recovering an optimal basic solution by identifying the optimal face and employing controlled perturbations based on the suboptimal solution provided by interior-point methods. We prove that an optimal solution for the perturbed problem is an extreme point, and its objective value is at least as good as that of the initial interior-point solution. Computational experiments show significant speed-ups achieved by our methods compared with state-of-the-art commercial solvers on classical linear programming problem benchmarks, network flow problem benchmarks, and optimal transport problems. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Funding: D. Ge was supported by the National Natural Science Foundation of China [Grants 72150001, 72225009, 72394360, and 72394365]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0291 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0291 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Recent years have seen a surge of machine learning approaches aimed at reducing disparities in model outputs across different subgroups. In many settings, training data may be used in multiple downstream applications by different users, which means it may be most effective to intervene on the training data itself. In this work, we present FairWASP, a novel pre-processing approach designed to reduce disparities in classification datasets without modifying the original data. FairWASP returns sample-level weights such that the reweighted dataset minimizes the Wasserstein distance to the original dataset while satisfying (an empirical version of) demographic parity, a popular fairness criterion. We show theoretically that integer weights are optimal, which means our method can be equivalently understood as duplicating or eliminating samples. FairWASP can therefore be used to construct datasets which can be fed into any classification method, not just methods which accept sample weights. Our work is based on reformulating the pre-processing task as a large-scale mixed-integer program (MIP), for which we propose a highly efficient algorithm based on the cutting plane method. Experiments demonstrate that our proposed optimization algorithm significantly outperforms state-of-the-art commercial solvers in solving both the MIP and its linear program relaxation. Further experiments highlight the competitive performance of FairWASP in reducing disparities while preserving accuracy in downstream classification settings.

Data distillation and coresets have emerged as popular approaches to generate a smaller representative set of samples for downstream learning tasks to handle large-scale datasets. At the same time, machine learning is being increasingly applied to decision-making processes at a societal level, making it imperative for modelers to address inherent biases towards subgroups present in the data. While current approaches focus on creating fair synthetic representative samples by optimizing local properties relative to the original samples, their impact on downstream learning processes has yet to be explored. In this work, we present fair Wasserstein coresets ($\texttt{FWC}$), a novel coreset approach which generates fair synthetic representative samples along with sample-level weights to be used in downstream learning tasks. $\texttt{FWC}$ uses an efficient majority minimization algorithm to minimize the Wasserstein distance between the original dataset and the weighted synthetic samples while enforcing demographic parity. We show that an unconstrained version of $\texttt{FWC}$ is equivalent to Lloyd's algorithm for k-medians and k-means clustering. Experiments conducted on both synthetic and real datasets show that $\texttt{FWC}$: (i) achieves a competitive fairness-performance tradeoff in downstream models compared to existing approaches, (ii) improves downstream fairness when added to the existing training data and (iii) can be used to reduce biases in predictions from large language models (GPT-3.5 and GPT-4).

Computing the Wasserstein barycenter of a set of probability measures under the optimal transport metric can quickly become prohibitive for traditional second-order algorithms, such as interior-point methods, as the support size of the measures increases. In this paper, we overcome the difficulty by developing a new adapted interior-point method that fully exploits the problem's special matrix structure to reduce the iteration complexity and speed up the Newton procedure. Different from regularization approaches, our method achieves a well-balanced tradeoff between accuracy and speed. A numerical comparison on various distributions with existing algorithms exhibits the computational advantages of our approach. Moreover, we demonstrate the practicality of our algorithm on image benchmark problems including MNIST and Fashion-MNIST.