Pareto-optimal linear programming
Abstract
Pareto-optimality plays a central role in evaluating the efficiency of solutions to allocation problems, such as house allocation, school choice, and kidney exchange. We introduce a general linear programming problem subject to Pareto-optimality conditions, which we call Max-Pareto . Using the novel result that Pareto-optimal bipartite matchings are fractionally Pareto-optimal, we prove that Max-Pareto is NP -complete. We propose a bilinear programming formulation of Max-Pareto , and evaluate its computational performance on the problem of finding Pareto-optimal allocations of highest welfare.
Fields of Study & Subjects
Advanced Optimization Algorithms Research
Optimization and Mathematical Programming
Optimization and Variational Analysis
Publication details
- Journal / source
- Operations Research Letters
- Publisher
- Elsevier BV
- Volume
- 67
- Pages
- 107455–107455
- Publication date
- 19 April 2026
- Language
- EN