Awesome-NN-ConstrainedOptimization

A curated list of NN ConstrainedOptimization papers: Using neural networks to solve constrained optimization problems.

Contributions are welcome!

Acknowledgments: This wonderful template is from https://github.com/VainF/Awesome-Anything by Gongfan Fang.

General methods/framework

Title & Authors	Intro	Useful Links
DC3: A learning method for optimization with hard constraints P. Donti, D. Rolnick, J. Z. Kolter > ICLR'21	This method enforces feasibility via a differentiable procedure, which implicitly completes partial solutions to satisfy equality constraints and unrolls gradient-based corrections to satisfy inequality constraints. We demonstrate the effectiveness of DC3 in both synthetic optimization tasks and the real-world setting of AC optimal power flow, where hard constraints encode the physics of the electrical grid. In both cases, DC3 achieves near-optimal objective values while preserving feasibility.	[Github] [PDF]
Ensuring DNN Solution Feasibility for Optimization Problems with Convex Constraints and Its Application to DC Optimal Power Flow Problems Tianyu Zhao, Xiang Pan, Minghua Chen, Steven H. Low > ICLR'23 Oral	This method enforces feasibility via a differentiable procedure, which implicitly completes partial solutions to satisfy equality constraints and unrolls gradient-based corrections to satisfy inequality constraints. We demonstrate the effectiveness of DC3 in both synthetic optimization tasks and the real-world setting of AC optimal power flow, where hard constraints encode the physics of the electrical grid. In both cases, DC3 achieves near-optimal objective values while preserving feasibility.	[Github] [PDF]

Optimal power flow

Title & Authors	Intro	Useful Links
DeepOPF: Deep Neural Network for DC Optimal Power Flow Xiang Pan, Tianyu Zhao, and Minghua Chen > 2019, IEEE International Conference on Smart Grid Communications	DeepOPF leverages a DNN model to depict the high-dimensional load-to-solution mapping and can directly solve the OPF problem upon given load, excelling in fast computation process and desirable scalability.	[Github] [PDF]
Optimal Power Flow Using Graph Neural Networks D Owerko, F Gama, A Ribeiro > ICASSP'20	This method uses imitation learning and graph neural networks to find a local and scalable solution to the OPF problem.	[PDF]
Learning Optimal Power Flow: Worst-Case Guarantees for Neural Networks Andreas Venzke, Guannan Qu > Arxiv	This paper introduces for the first time a framework to obtain provable worst-case guarantees for neural network performance, using learning for optimal power flow (OPF) problems as a guiding example.	[PDF]

Combinatorial optimization problem

Title & Authors	Intro	Useful Links
Revocable Deep Reinforcement Learning with Affinity Regularization for Outlier-Robust Graph Matching Chang Liu, Zetian Jiang, Runzhong Wang, Junchi Yan, Lingxiao Huang, Pinyan Lu > SJTU > ICLR'23	Towards practical and robust graph matching learning, in the absence of labels and in the presence of outliers (in both input graphs), this paper proposes a reinforcement learning method for graph matching namely RGM, especially for its most general QAP formulation	[Github] [PDF]
Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization Nathan Grinsztajn, Daniel Furelos-Blanco, Shikha Surana, Clément Bonnet, Thomas D. Barrett > NIPS'23	This paper introduces Poppy, a simple training procedure for populations. Instead of relying on a predefined or hand-crafted notion of diversity, Poppy induces an unsupervised specialization targeted solely at maximizing the performance of the population. We show that Poppy produces a set of complementary policies, and obtains state-of-the-art RL results on four popular NP-hard problems: traveling salesman, capacitated vehicle routing, 0-1 knapsack, and job-shop scheduling.	[PDF]
A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, Xiaodong Luo > Shenzhen Research Institute of Big Data > ICLR'23	This paper proposes a novel predict-and-search framework for efficiently identifying high-quality feasible solutions. Specifically, they first utilize graph neural networks to predict the marginal probability of each variable, and then search for the best feasible solution within a properly defined ball around the predicted solution	[Github] [PDF]
CktGNN: Circuit Graph Neural Network for Electronic Design Automation Zehao Dong, Weidong Cao, Muhan Zhang, Dacheng Tao, Yixin Chen, Xuan Zhang > WUSTL > ICLR'23	CktGNN is a two-level GNN model with a pre-designed subgraph basis for the analog circuit (DAG) encoding. CktGNN simultaneously optimizes circuit topology and device features, achieving state-of-art performance in analog circuit optimization.	[Github] [PDF]
Two-Stage Predict+Optimize for Mixed Integer Linear Programs with Unknown Parameters in Constraints Xinyi Hu, Jasper C.H. Lee, Jimmy H.M. Lee > CUHK > NIPS'23	Predict+Optimize is a recent framework for end-to-end training supervised learning models for such predictions, incorporating information about the optimization problem in the training process in order to yield better predictions in terms of the quality of the predicted solution under the true parameters. They also give a training algorithm usable for all mixed integer linear programs, vastly generalizing the applicability of the framework	[Github] [PDF]
Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron Courville, Yoshua Bengio, Ling Pan > Mila > NIPS'23	This paper designs Markov decision processes (MDPs) for different combinatorial problems and proposes to train conditional GFlowNets to sample from the solution space. Efficient training techniques are also developed to benefit long-range credit assignment.	[Github] [PDF]

Physics-Inspired Optimization

Title & Authors	Intro	Useful Links
Combinatorial Optimization with Physics-Inspired Graph Neural Networks *Martin J. A. Schuetz, J. Kyle Brubaker, Helmut G. Katzgraber > Amazon > Nature Machine Intelligence '22	This paper uses Physics-inspired GNN to solve quadratic unconstrained binary optimization problems, such as maximum cut, minimum vertex cover, maximum independent set, as well as Ising spin glasses and higher-order generalizations thereof in the form of polynomial unconstrained binary optimization problems.	[Github] [PDF]

Using penalty terms to handle constrained optimization problems

... (TBD)