Project Details
Description
In many cutting-edge paradigms that have been developed for joint optimization of multiple systems, it may be unrealistic to expect solutions that are guaranteed to be feasible with respect to all possible constraints of each system. This is particularly the case in systems that operate under dynamic environments and are subject to uncertain events such as terrorist attacks or natural disasters. Even when feasibility may be guaranteed, the resulting solutions could be overly conservative. In this project, we will consider one such paradigm for optimization, which we refer to as optimization problems with system choice (OPSC). This class of problems includes as special cases multiple-choice constrained optimization, optimization under sparsity constraints, linear programs with constraint selection, and chance-constrained programs. While convex conic optimization problems are efficiently solvable, the presence of nonconvexities, such as systems choice decisions, present significant new challenges and the state-of-the-art algorithms do not scale well. The prevailing approach to address related problems is to introduce additional binary variables to represent the constraint choice and use big-M formulations to enforce constraints that are chosen. Branch-and-bound solvers are used to solve the resulting mixed-integer representation, but it is well-known that the continuous relaxations of the big-M formulations are weak, which affects the performance of the branch-and-bound algorithm negatively. In special cases of this problem, there is some work to improve the relaxation bounds by deriving valid inequalities from individual constraints. However, when multiple constraints define a system, as in the general case of OPSC, ignoring the interactions between the constraints may lead to weak inequalities. The proposed foundational research will establish frameworks that overcome these challenges by exploiting valuable structural information in a unified manner. The main develo
Status | Finished |
---|---|
Effective start/end date | 5/1/19 → 4/30/23 |
Funding
- Office of Naval Research (N00014-19-1-2321 P00001)
Fingerprint
Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.