MIXED-INTEGER QUADRATIC OPTIMIZATION: STRUCTURAL RESULTS AND PRACTICAL RELAXATIONS
Abstract
Modern decision-making problems require increasingly sophisticated algorithms and methods for their effective solving. Many such problems are naturally modeled as mixed-integer nonlinear programming problems (MINLPs), that is, problems involving a combination of: continuous variables, often used to model the actual decisions being made; discrete variables, used to encode logical constraints; and nonlinear terms, used to capture uncertainty and other physical characteristics of the problem. However, due to the nonlinearities, most MINLPs cannot be efficiently solved using current mixed-integer programming technology and solvers. The goal of this research is to pinpoint, at a fundamental level, precisely how nonlinearities affect problem structures, to develop methodologies that allow for formal characterizations of the effectiveness of a given approach, and to ultimately develop practical methods that are informed by theory, and based upon a solid understanding of the characteristics of the problems being tackled. If successful, the research will pave the way for the development of specialized MINLP software that can effectively solve challenging decision-making problems in control, (for example, planning trajectories of a fleet of unmanned vehicles to accomplish a mission), machine learning (for example, obtaining an interpretable prediction of security risks in a network), and related areas.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Apr 20, 2023
- Source ID
- FA95502210369
Entities
People
- Andres Gomez Escobar
Organizations
- Air Force Office of Scientific Research
- United States Air Force
- University of Southern California