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

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.