Dear All,
Thank you for sharing your thoughts, and experiences, and for initiating this discussion at INFORMS. Your efforts in facilitating this conversation are truly appreciated.
Throughout my collaborations with professionals from diverse fields, including Operations Research, Computer Science, Electrical and Computer Engineering, and Industrial Engineering, I have experienced firsthand the vast potential that interdisciplinary connections offer. This realization emphasizes the importance of bridging the gaps between disciplines in order to discover innovative solutions and advance our understanding of complex problems.
I believe that Machine Learning (ML) is not merely a buzzword or a one-size-fits-all solution; it represents an established and growing trend with the capability to reveal new approaches for efficiently tackling critical challenges through collaborative efforts. In some instances, ML has proven to be the missing "piece of the puzzle" that enables effective problem resolution in areas of societal importance. Although my primary research focus is in ECE, with most of my publications in IEEE journals, I have expanded my contributions to address pressing societal concerns by working across departments and exploring the intersection of Operations Research (OR) and ML. I see ML as a valuable opportunity for growth and innovation within OR, particularly for solving problems with numerous decision variables and constraints. It is worth noting that the interpretability of ML in OR problems can sometimes raise concerns.
I appreciate how INFORMS creates an inclusive environment, bringing together researchers from various fields to collaborate and address essential issues efficiently and synergistically.
At the INFORMS Annual Meeting 2023, I am organizing a session titled "Exploring the Intersection of Machine Learning and Discrete Optimization: Techniques and Applications." This session aims to connect Machine Learning and Discrete Optimization by offering insights into different techniques and their practical applications. We will discuss machine learning and discrete optimization concepts and how they can be effectively combined. We will explore various techniques for integrating machine learning into discrete optimization problems, such as Lagrangian relaxation, Reinforcement Learning, and Deep Neural Networks. Additionally, we will examine the application of these techniques in real-world problems, including manufacturing scheduling, power systems optimization, and transportation. The session is tailored for data scientists, machine learning engineers, optimization experts, and anyone interested in the intersection of machine learning and discrete optimization.
I am pleased to share several papers I have contributed to, which showcase the synergy between Operations Research (OR) and Machine Learning (ML) in addressing challenges in Manufacturing, Power Systems, and Healthcare:
1. Integrating Machine Learning and Mathematical Optimization for Job-Shop Scheduling [1]
Job-shop scheduling is a crucial and challenging optimization problem for low-volume, high-variety manufacturing, requiring quick solutions. The increasing demand for customized products leads to growing problem sizes, making efficient job-shop scheduling difficult to solve to meet production deadlines and on-time delivery. The direct machine learning application for large-scale job-shop scheduling suffers from generalizability difficulties, making it challenging to predict solutions for a wide range of jobs.
Interplay between OR/ML: The synergistic integration of Deep Neural Networks (DNNs) within the Surrogate Lagrangian Relaxation (SLR) framework, a decomposition and coordination approach, is to predict good-enough solutions for job subproblems thereby overcoming learning difficulties caused by large scales ultimately leading to much reduced computational time and effort as well as to high-quality schedules to avoid late shipments and maintain customer satisfaction. To improve generalization for various jobs, we establish "surrogate" job subproblems, solutions to which are even easier to learn, develop a DNN based on Pointer Network together with a Masking mechanism to predict their solutions and calculate the overall feasible solutions based on these predictions as well as on efficient SLR-enabled coordination. The integration of OR and ML demonstrates the potential for addressing complex problems arising in OR.
Kudos to Anbang Liu (Tsinghua)! The associated paper is conditionally accepted by IEEE Transactions on Automation Science and Engineering. Preprint: https://doi.org/10.36227/techrxiv.20510841.v3. Anbang Liu is also a co-chair of the session "Exploring the Intersection of Machine Learning and Discrete Optimization: Techniques and Applications" at INFORMS Annual Meeting 2023. Don't miss it! :) A big thank you to @Thiago Serra for inviting us to organize the session!
2. Synergistic Integration of Machine Learning and Mathematical Optimization for Unit Commitment [2]
Unit Commitment (UC) is crucial for power system operations, however, with increasing challenges such as growing intermittent renewables and intra-hour net load variability, traditional mathematical optimization can be time-consuming. The commitment of units/generators that is robust to stochastic events is important to avoid unscheduled power outages as well as to increase operational efficiency. Machine learning (ML) is a promising alternative to traditional approaches, but directly learning good solutions for UC is difficult due to its combinatorial nature. We synergistically integrate ML within the decomposition and coordination method of Surrogate Lagrangian Relaxation to learn "good enough" subproblem solutions of deterministic UC. Compared to the original UC, subproblems are much easier to learn.
Interplay between OR/ML: This paper integrates machine learning (ML) within the Surrogate Lagrangian Relaxation to solve the Unit Commitment (UC) problem efficiently. This research also demonstrates the potential of combining machine learning and mathematical optimization in solving complex power system operation optimization problems like Unit Commitment and many other MIP problems.
Kudos to Jianghua Wu (the University of Connecticut, ECE)! The associated paper has been accepted by IEEE Transactions on Power Systems. https://ieeexplore.ieee.org/abstract/document/10026495
Within the above two papers, supported by fast coordination and superlinear reduction of complexity, the ML was indeed the missing piece to unlock the potential toward solving MIP problems within milliseconds. The research is ongoing, and we expect the interplay of OR and ML to continue in other fields beyond manufacturing and power systems.
The above papers focus on solving MIP problems by using ML techniques. How about MIP techniques helping to resolve issues arising in ML?
3. Combining Multi-View Ensemble and Surrogate Lagrangian Relaxation for Real-Time 3D Biomedical Image Segmentation on the Edge [3]
Real-time 3D biomedical image segmentation is essential due to the growing medical imaging data, but deep learning-based methods often require high computation and memory resources. Additionally, privacy and security of patient data are primary concerns in medical applications, making it necessary for 3D biomedical image segmentation to be performed locally (i.e., on the edge) with limited resources. We developed a combination of multi-view ensemble and Surrogate Lagrangian Relaxation (SLR) for real-time 3D biomedical image segmentation on edge. The new method avoids directly dealing with complex 3D biomedical images by leveraging multi-view ensemble techniques, which enable efficient processing of 3D images using multiple 2D views. The Surrogate Lagrangian Relaxation method is integrated to further optimize the segmentation process.
Interplay between OR/ML: This paper synergistically combines a multi-view ensemble technique, an ML approach, with the Surrogate Lagrangian Relaxation, to achieve real-time 3D biomedical image segmentation on the edge, with significant implications for healthcare. This research presents an innovative approach to address the challenges of computational and memory constraints while ensuring patient data privacy and security. The Surrogate Lagrangian Relaxation method not only provides a promising solution for efficient and accurate medical image segmentation in resource-constrained environments but also facilitates effective DNN model compression through neuron and/or weight pruning. Model compression is essential for minimizing the computational resources and memory needed to deploy deep learning models, especially in edge devices with limited processing capabilities. The effectiveness of this approach has been demonstrated in various other applications, including image classification, object detection, and specific tasks such as lane detection [4].
Kudos to Shanglin Zhou (the University of Connecticut, CSE)! The associated paper has been accepted by Neurocomputing. https://www.sciencedirect.com/science/article/abs/pii/S0925231222011286
Conclusion and Broader Perspective: Integrating ML into traditional OR algorithmic frameworks can effectively address many concerns and challenges, paving the way to solve MIP problems with significant societal implications. For example, ML can be used to quickly predict subproblem solutions within decomposition and coordination frameworks, such as Lagrangian Relaxation (LR). With recent developments, LR ensures fast convergence leading to high-quality feasible solutions to a MIP problem, while ML provides a rapid solution strategy for subproblems in the order of milliseconds. This represents an innovative fusion of conventional OR and ML methods. Moreover, ML models based on Lagrangian multipliers (i.e., shadow prices) align with the economics concept of supply-demand shifts in response to market price variations, making ML-based methods of [1] and [2] highly interpretable.
References:
[1] A.-B. Liu, P. B. Luh, K. Sun, M. A. Bragin and B. Yan, "Integrating Machine Learning and Mathematical Optimization for Job Shop Scheduling," conditionally accepted to IEEE Transactions on Automation Science and Engineering.
[2] J. Wu, P. B. Luh, Y. Chen, M. A. Bragin, and B. Yan, "Synergistic Integration of Machine Learning and Mathematical Optimization for Unit Commitment," accepted to IEEE Transactions on Power Systems. DOI: 10.1109/TPWRS.2023.3240106
[3] S. Zhou, X. Xu, M. A. Bragin, and J. Bai, "Combining Multi-view Ensemble and Surrogate Lagrangian Relaxation for Real-time 3D Biomedical Image Segmentation on the Edge," Neurocomputing, Volume 512, November 2022, pp. 466 – 481. DOI: 10.1016/j.neucom.2022.09.039
Additional Reading/Supporting Publications:
[4] B. Li, Z. Wang, S. Huang, M. A. Bragin, J. Li and C. Ding, "Towards Lossless Head Pruning through Automatic Peer Distillation for Language Models," accepted to Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-23) (Acceptance rate: 15%)
[5] Z. Wang‡, B. Li, X. Xiao, T. Zhang, M. A. Bragin‡, B. Yan, C. Ding, and S. Rajasekaran, "Automatic Subnetwork Search Through Dynamic Differentiable Neuron Pruning," accepted to ISQED 2023 (Special Session)
[6] D. Gurevin‡, M. A. Bragin‡, C. Ding‡, S. Zhou, L. Pepin, B. Li, and F. Miao, "Enabling Retrain-Free Deep Neural Network Pruning using Surrogate Lagrangian Relaxation," Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21), pp. 2497-2504. DOI: 10.24963/ijcai.2021/344 (Acceptance rate: 13.9%)
[7] W. Wan, P. Zhang, M. A. Bragin, and P. B. Luh, "Safety-Assured, Real-Time Neural Active Fault Management for Resilient Microgrids Integration," iEnergy, Volume 1, Issue 4, December 2022, pp. 453 - 462. DOI: 10.23919/IEN.2022.0048
[8] D. Zhdanov, S. Bhattacharjee, and M. A. Bragin, "Incorporating FAT and Privacy-Aware AI Modeling Approaches into Business Decision Making Frameworks," Decision Support Systems, Volume 155, April 2022, 113715. DOI: 10.1016/j.dss.2021.113715
[9] M. A. Bragin, P. B. Luh, J. H. Yan, N. Yu, and G. A. Stern, "Convergence of the Surrogate Lagrangian Relaxation Method," Journal of Optimization Theory and Applications, Volume 164, Issue 1, 2015, pp. 173 – 201. DOI: 10.1007/s10957-014-0561-3
------------------------------
Mikhail Bragin
University of California, Riverside
Riverside CA
------------------------------