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

点击翻译按钮获取中文摘要

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.