LEAPS-MPS: Advancing Approximation of Heterogeneous Multi-Objective Set Covering Problems with Modeling and Applications

该奖项全部或部分由《2021年美国救援计划法案》（公法117-2）资助。本项目的目标是通过理论上健全和高效的模型和算法，近似求解与保护规划和紧急医疗服务管理决策相关的大规模优化解。该项目的广泛适用性在于推进优化工具，整合大量空间数据，有效配置资源，分析物种分布、种群参数、保护区空间配置、土地成本和环境动态等信息。在制定策略时，有必要事先估计近似的质量，以有效地利用可用资源并成功地应对未来的不利条件。为了更好地理解优化问题近似解的极限，所开发算法的一个重要组成部分是预定质量度量，其中最优解集始终保证在预定误差范围内。该项目将教育和推广活动结合起来，目标是扩大代表性不足群体在STEM领域的参与。本项目以多目标优化（MO）为研究重点，研究具有预定质量度量的广义集覆盖问题（MOSCPs）和近似算法，为保护规划和应急医疗服务管理中的决策优化提供解决方案。在MO技术中，广义MOSCP是一种计算密集型的具有挑战性的方法，其理论和方法尚不发达，本项目的技术主题是利用数学规划对其结构特性进行理论和计算研究。MO问题通常不具有单目标优化的全有序意义上的最优解；相反，它们在存在多个相互冲突的目标时具有部分有序意义上的最优解，其应用的成功取决于计算解决集元素的能力，即所谓的帕累托集。这个项目的很大一部分致力于研究混合整数多目标优化问题中近似帕累托集的计算效率替代方法。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This award is funded in whole or in part under the American Rescue Plan Act of 2021 (Public Law 117-2). The goal of this project is to approximate large-scale optimization solutions associated with decision-making in conservation planning and emergency medical service management, through theoretically-sound and efficient models and algorithms. The broad applicability of the project is in advancing optimization tools to integrate voluminous spatial data to effectively allocate resources and analyze information such as species distribution, population parameters, the spatial configuration of reserves, land costs, and environmental dynamics. In establishing a strategy it is necessary to estimate the quality of the approximation beforehand to efficiently use the available resources and successfully address future adverse conditions. To better understand the limits of approximating the solution of an optimization question, a significant component of the developed algorithms is the predetermined quality measure, where the optimal solution set is always guaranteed to be within a predetermined error. The project integrates educational and outreach activities with the goal of broadening participation of underrepresented groups in STEM fields. This project focuses on multiobjective optimization (MO), and specifically on generalized set covering questions (MOSCPs) and approximation algorithms with predetermined quality measures, to enable the solutions of decision-making optimization in conservation planning and emergency medical service management. Among MO techniques, the generalized MOSCP emerges as a computationally intensive challenging method whose theory and methodology remain underdeveloped, the technical theme of this project is the theoretical and computations investigation of its structural properties using mathematical programming. MO questions typically do not have optimal solutions in the totally ordered sense of single objective optimization; instead, they have optimal solutions in a partially ordered sense appropriate in the presence of multiple conflicting objectives, and the success of their application depends on the ability to compute the elements of the solution set, the so-called Pareto set. A large portion of this project is devoted to investigating computationally efficient alternative methods to approximate the Pareto set in mixed integer multiobjective optimization questions.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.