IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v34y2022i1p463-480.html
   My bibliography  Save this article

Learning for Constrained Optimization: Identifying Optimal Active Constraint Sets

Author

Listed:
  • 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)

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.

Suggested Citation

  • Sidhant Misra & Line Roald & Yeesian Ng, 2022. "Learning for Constrained Optimization: Identifying Optimal Active Constraint Sets," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 463-480, January.
  • Handle: RePEc:inm:orijoc:v:34:y:2022:i:1:p:463-480
    DOI: 10.1287/ijoc.2020.1037
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2020.1037
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2020.1037?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Alejandro Marcos Alvarez & Quentin Louveaux & Louis Wehenkel, 2017. "A Machine Learning-Based Approximation of Strong Branching," INFORMS Journal on Computing, INFORMS, vol. 29(1), pages 185-195, February.
    2. Volodymyr Mnih & Koray Kavukcuoglu & David Silver & Andrei A. Rusu & Joel Veness & Marc G. Bellemare & Alex Graves & Martin Riedmiller & Andreas K. Fidjeland & Georg Ostrovski & Stig Petersen & Charle, 2015. "Human-level control through deep reinforcement learning," Nature, Nature, vol. 518(7540), pages 529-533, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Tulika Saha & Sriparna Saha & Pushpak Bhattacharyya, 2020. "Towards sentiment aided dialogue policy learning for multi-intent conversations using hierarchical reinforcement learning," PLOS ONE, Public Library of Science, vol. 15(7), pages 1-28, July.
    2. Mahmoud Mahfouz & Angelos Filos & Cyrine Chtourou & Joshua Lockhart & Samuel Assefa & Manuela Veloso & Danilo Mandic & Tucker Balch, 2019. "On the Importance of Opponent Modeling in Auction Markets," Papers 1911.12816, arXiv.org.
    3. Bissan Ghaddar & Ignacio Gómez-Casares & Julio González-Díaz & Brais González-Rodríguez & Beatriz Pateiro-López & Sofía Rodríguez-Ballesteros, 2023. "Learning for Spatial Branching: An Algorithm Selection Approach," INFORMS Journal on Computing, INFORMS, vol. 35(5), pages 1024-1043, September.
    4. Woo Jae Byun & Bumkyu Choi & Seongmin Kim & Joohyun Jo, 2023. "Practical Application of Deep Reinforcement Learning to Optimal Trade Execution," FinTech, MDPI, vol. 2(3), pages 1-16, June.
    5. Lu, Yu & Xiang, Yue & Huang, Yuan & Yu, Bin & Weng, Liguo & Liu, Junyong, 2023. "Deep reinforcement learning based optimal scheduling of active distribution system considering distributed generation, energy storage and flexible load," Energy, Elsevier, vol. 271(C).
    6. Yuhong Wang & Lei Chen & Hong Zhou & Xu Zhou & Zongsheng Zheng & Qi Zeng & Li Jiang & Liang Lu, 2021. "Flexible Transmission Network Expansion Planning Based on DQN Algorithm," Energies, MDPI, vol. 14(7), pages 1-21, April.
    7. Michelle M. LaMar, 2018. "Markov Decision Process Measurement Model," Psychometrika, Springer;The Psychometric Society, vol. 83(1), pages 67-88, March.
    8. Yang, Ting & Zhao, Liyuan & Li, Wei & Zomaya, Albert Y., 2021. "Dynamic energy dispatch strategy for integrated energy system based on improved deep reinforcement learning," Energy, Elsevier, vol. 235(C).
    9. Wang, Yi & Qiu, Dawei & Sun, Mingyang & Strbac, Goran & Gao, Zhiwei, 2023. "Secure energy management of multi-energy microgrid: A physical-informed safe reinforcement learning approach," Applied Energy, Elsevier, vol. 335(C).
    10. Neha Soni & Enakshi Khular Sharma & Narotam Singh & Amita Kapoor, 2019. "Impact of Artificial Intelligence on Businesses: from Research, Innovation, Market Deployment to Future Shifts in Business Models," Papers 1905.02092, arXiv.org.
    11. Ande Chang & Yuting Ji & Chunguang Wang & Yiming Bie, 2024. "CVDMARL: A Communication-Enhanced Value Decomposition Multi-Agent Reinforcement Learning Traffic Signal Control Method," Sustainability, MDPI, vol. 16(5), pages 1-17, March.
    12. Sun, Hongchang & Niu, Yanlei & Li, Chengdong & Zhou, Changgeng & Zhai, Wenwen & Chen, Zhe & Wu, Hao & Niu, Lanqiang, 2022. "Energy consumption optimization of building air conditioning system via combining the parallel temporal convolutional neural network and adaptive opposition-learning chimp algorithm," Energy, Elsevier, vol. 259(C).
    13. Zhang, Yang & Yang, Qingyu & Li, Donghe & An, Dou, 2022. "A reinforcement and imitation learning method for pricing strategy of electricity retailer with customers’ flexibility," Applied Energy, Elsevier, vol. 323(C).
    14. He, Jing & Liu, Xinglu & Duan, Qiyao & Chan, Wai Kin (Victor) & Qi, Mingyao, 2023. "Reinforcement learning for multi-item retrieval in the puzzle-based storage system," European Journal of Operational Research, Elsevier, vol. 305(2), pages 820-837.
    15. Holger Mohr & Katharina Zwosta & Dimitrije Markovic & Sebastian Bitzer & Uta Wolfensteller & Hannes Ruge, 2018. "Deterministic response strategies in a trial-and-error learning task," PLOS Computational Biology, Public Library of Science, vol. 14(11), pages 1-19, November.
    16. Zhang, Tianhao & Dong, Zhe & Huang, Xiaojin, 2024. "Multi-objective optimization of thermal power and outlet steam temperature for a nuclear steam supply system with deep reinforcement learning," Energy, Elsevier, vol. 286(C).
    17. Taejong Joo & Hyunyoung Jun & Dongmin Shin, 2022. "Task Allocation in Human–Machine Manufacturing Systems Using Deep Reinforcement Learning," Sustainability, MDPI, vol. 14(4), pages 1-18, February.
    18. Sebastian Jaimungal, 2022. "Reinforcement learning and stochastic optimisation," Finance and Stochastics, Springer, vol. 26(1), pages 103-129, January.
    19. Emmanuel Gnabeyeu & Omar Karkar & Imad Idboufous, 2024. "Solving The Dynamic Volatility Fitting Problem: A Deep Reinforcement Learning Approach," Papers 2410.11789, arXiv.org.
    20. Timotei Lala & Darius-Pavel Chirla & Mircea-Bogdan Radac, 2021. "Model Reference Tracking Control Solutions for a Visual Servo System Based on a Virtual State from Unknown Dynamics," Energies, MDPI, vol. 15(1), pages 1-25, December.

    More about this item

    Keywords

    learning; active sets;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:34:y:2022:i:1:p:463-480. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.