A Polyhedral Approach for Multi-Parametric Linear Programming
Abstract
Mathematical optimization is a powerful tool for solving a huge variety of problems in design, planning, and operation of complex systems. However, the computational time to solve such problems is often too long to be practical for real-time decision-making. Such decision settings typically require to repeatedly solve optimization problems with a fixed structure but varying parameters. This repetitive solving presents an opportunity to perform computations offline, before observing specific parameter realizations, in order to allow quick computation of optimal solutions online, when it is required to quickly solve linear programs defined by specific parameter assignments. This project will study the use of multi-parametric Linear Programming as a tool for real-time decision-making. It will identify and exploit problem structures that ensure both tractability and efficacy of the proposed approach. There are two research thrusts. In the first thrust, investigations will be conducted as to structures of feasible regions and parameter sets that enable efficient computation of sets of candidate solutions which are sufficient to search over in the online phase. The second research thrust will consider the case where the parameters are random, and the research will be to identify probabilistic structures that allow for the computation of an optimal solution (or a good approximation) with high probability. The results will expose the fundamental limits of computations in multi-parametric Linear Programming and will identify large classes of such problems that can be solved efficiently within those limits.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Mar 06, 2024
- Source ID
- FA95502310487
Entities
People
- Carla Michini
Organizations
- Air Force Office of Scientific Research
- Office of the Secretary of Defense
- University of Wisconsin System