Theoretical Foundations and Scalable Algorithms for Mixed-Integer Convex Optimization with System Choice
Abstract
In many existing paradigms that can be applied to joint optimization problems of multiple systems, it may be unrealistic to expect solutions that are guaranteed to be feasible with respect to the constraints for all systems. This is particularly the case in systems that operate under dynamic environments and are subject to uncertain events (e.g., terrorist attacks or natural disasters). Even when feasibility can be guaranteed, the resulting solutions are often overly conservative. In this project, we will consider a novel paradigm for optimization insuch environments, which we refer to as optimization problems with system choice (OPSC). This problem class entails the selection of which systems of constraints to satisfy as part of the decisions. In our study, we will focus on systems that have constraints in conic form, such as linear or second-order cone constraints. Special cases of this class of problems include 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, systems choice decisions present nonconvexities and result in significant new challenges. Due to the exponential growth of the search space, the state-of-the-art algorithms do not scale well in these cases. The prevailing approach to address related problems is to introduce additional binary variables to represent the system choice and use big-M formulations to enforce all constraints of the chosen systems. Branch-and-bound solvers are used to solve the resultingmixed-integer representation. But, it is well known that the continuous relaxations of the big-M formulations are weak, and this hinders the performance of the branch-and-bound algorithm. As a remedy to this, in certain special cases of this problem with linear structure, such big-M formulations are further enhanced in a systemic way by deriving new valid inequalities from individual system constraints. However, when multiple constraints definea system, as in the general case of OPSC, ignoring the interactions between the constraints, even if the original system constraints are linear, may lead to weak inequalities. The proposed foundational research will establish unifying frameworks that address these challenges by exploiting valuable structural information embedded in the joint nature of the systems constraints. The research outcomes will advance our understanding of the key trade-offs between relaxation quality and computational tractability for OPSC.The overarching goal of the proposed project is to establish foundational polyhedral theory of the structured nonconvex sets arising in OPSC, and to devise scalable algorithms that rely on efficient separation schemes for the strengthened formulations. Our primary focus will be on developing new systemic techniques to generate classes of strong valid (linear or conic) inequalities to improve the continuous relaxations that can be easily incorporated into existing algorithmic frameworks. The proposed research will introduce novel paradigms for incorporating more information into the convexification process, by exploiting the interactions between the multiple (conic) structures simultaneously present. The proposed research will provide rigorous analysis of the strength of the proposed inequalities, as well as explicit results on convex hull characterizations, whenever possible. In addition, thesetheoretical developments will be supplemented with a study of efficient separation algorithms to further enhance the scalability of this approach. The resulting algorithms will be extensively tested on practical problems that entail the systems choice aspect.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- May 23, 2019
- Source ID
- N000141912321
Entities
People
- Si̇mge Küçükyavuz
Organizations
- Northwestern University
- Office of Naval Research
- United States Navy