CRII: AF: Theory and Algorithms for Maximum Multiplicative Programs Through the Lens of Multi-objective Optimization

自然资源管理的一个基本问题是，在一个地理区域内，哪些地点或地块应该受到保护，以保护生物多样性。这个对人类社会至关重要的问题，以及不同领域的许多其他重要问题，包括但不限于博弈论、系统可靠性和统计估计，都可以表述为一类特定的数学优化问题。然而，解决这类重要优化问题的实际规模实例的现有解决方法通常是缓慢和无效的。因此，这个项目的目标是通过从一个完全不同的角度探索这类优化问题，为它提供新颖有效的方法。该项目将培养两名研究生，其中一名将来自学术界代表性不足的群体。将根据项目结果创建案例研究和教学模块，并将其整合到研究生水平的课程中进行优化。此外，开源软件包将被提供给其他研究人员和从业者，以帮助他们解决类似的问题。最大乘法规划（MMP）是一类单目标非线性优化问题，其目标函数为若干非负线性函数的乘积，约束条件为线性，且决策变量可为连续或整数。虽然MMP只有一个目标函数，但本研究项目将表明，通过将其目标函数分解为单独的线性目标函数，可以通过多目标优化的视角来看待和解决它。已知当不允许使用整数决策变量时，MMPs是多项式可解的；否则它们就会变成np困难，因为单目标混合整数线性规划也是mmp。因此，该研究项目将首先开发新的基于多目标线性规划的算法，用于在多项式时间内求解只有连续决策变量的MMPs。该项目下一步将开发新的基于多目标混合整数线性规划的算法，用于求解具有连续和整数决策变量的MMPs。此外，该项目将为MMPs开发新的基于目标空间的切割生成和分解技术。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

A fundamental problem in natural-resource management is which sites or parcels should be protected within a geographical region for preserving biodiversity. This problem, which is crucial to human societies, and many other important problems in different domains including, but not limited to, game theory, system reliability, and statistical estimation can be formulated as a specific class of mathematical optimization problems. However, the existing solution approaches for solving practical-sized instances of this important class of optimization problems are often slow and ineffective. Hence, the objective of this project is to deliver novel and effective methodologies for this class of optimization problems by exploring it from a completely different perspective. The project will train two graduate students in which one of them will be from groups underrepresented in academia. Case studies and teaching modules will be created based on the results of the project and will be integrated into graduate-level courses in optimization. Also, open-source software packages will be delivered to help other researchers and practitioners working on similar problems.A Maximum Multiplicative Program (MMP) is a single-objective nonlinear optimization problem whose objective function is the product of some non-negative linear functions, whose constraints are linear, and and whose decision variables can be continuous or integers. Although an MMP has only one objective function, this research project will show that it can be viewed and solved through the lens of multi-objective optimization by decomposing its objective function into separate linear objective functions. It is known that when integer decision variables are not allowed, MMPs are polynomially solvable; otherwise they become NP-hard since single-objective mixed integer linear programs are also MMPs. Hence, the research project will first develop novel multi-objective linear programming-based algorithms for solving MMPs with only continuous decision variables in polynomial time. The project will next develop novel multi-objective mixed integer linear programming-based algorithms for solving MMPs with both continuous and integer decision variables. Additionally, the project will result in developing new objective-space-based cut-generating and decomposition techniques for MMPs.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.