Mixed-integer nonlinear programming- Unleashing the full potential of relaxations
Abstract
Mixed-integer optimization techniques have been successfully deployed to tackle decision-making problems in machine learning, robotics, logistics and policy making. However, modern optimization problems arising in highly uncertain environments, or in the presence of multiple agents and adversaries, call for the introduction of nonlinearities and the development of increasingly sophisticated methods. A fundamental technique, convexification, transforms highly complex landscapes that arise in mixed-integer optimization problems into simpler but equivalent forms, ensuring that optimal solutions can be easily spotted. Unfortunately, solvers for mixed-integer problems with nonlinearities, based on the popular branch-and-bound algorithm, struggle to incorporate several convexification results that have been derived in the literature, severely limiting their potential to tackle challenging, large-scale problems. The proposed research will develop novel methods to exploit convexification results, allowing for a natural integration of different convex relaxations. The methods will exploit the strength and quality of the more sophisticated relaxations, and at the same time maintain the tractability of the simpler relaxations. Consequently, the proposed techniques are fully compatible, and will significantly enhance, existing methods. The project will also contribute to the literature in convexification, by developing new theory, producing novel convex relaxations, and proposing new paradigms to tackle challenging nonlinear problems. If successful, the project will lead to significant advances in solving critical problems arising in decision-making with uncertainty, control and machine learning.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 06, 2025
- Source ID
- FA95502410086
Entities
People
- Andres Gomez Escobar
Organizations
- Air Force Office of Scientific Research
- United States Air Force
- University of Southern California