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

CRII：AF：多目标优化视角下的最大乘法程序的理论和算法

• 批准号: 1849627
• 负责人: Hadi Gard
• 金额: $ 17.5万
• 依托单位: University of South Florida
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-07-15 至 2021-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1849627&HistoricalAwards=false
• 关键词: CRII; AF; Theory; Algorithms; Maximum

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.

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