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

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

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.