Learning for Constrained Optimization: Identifying Optimal Active Constraint Sets

Sidhant Misra (), Line Roald () and Yeesian Ng ()
Additional contact information
Sidhant Misra: Applied Mathematics and Plasma Physics, Los Alamos National Laboratory, Los Alamos, New Mexico 87545
Line Roald: Department of Electrical and Computer Engineering, University of Wisconsin, Madison, Wisconsin 53706
Yeesian Ng: Google, Mountain View, California 94043

INFORMS Journal on Computing, 2022, vol. 34, issue 1, 463-480

Abstract: In many engineered systems, optimization is used for decision making at time scales ranging from real-time operation to long-term planning. This process often involves solving similar optimization problems over and over again with slightly modified input parameters, often under tight latency requirements. We consider the problem of using the information available through this repeated solution process to learn important characteristics of the optimal solution as a function of the input parameters. Our proposed method is based on learning relevant sets of active constraints, from which the optimal solution can be obtained efficiently. Using active sets as features preserves information about the physics of the system, enables interpretable results, accounts for relevant safety constraints, and is easy to represent and encode. However, the total number of active sets is also very large, as it grows exponentially with system size. The key contribution of this paper is a streaming algorithm that learns the relevant active sets from training samples consisting of the input parameters and the corresponding optimal solution, without any restrictions on the problem type, problem structure or probability distribution of the input parameters. The algorithm comes with theoretical performance guarantees and is shown to converge fast for problem instances with a small number of relevant active sets. It can thus be used to establish simultaneously learn the relevant active sets and the practicability of the learning method. Through case studies in optimal power flow, supply chain planning, and shortest path routing, we demonstrate that often only a few active sets are relevant in practice, suggesting that active sets provide an appropriate level of abstraction for a learning algorithm to target.

Keywords: learning; active sets (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.1037 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:1:p:463-480

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().