Learning to Solve Network Flow Problems via Neural Decoding

Abstract

Many decision-making problems in engineering applications such as transportation, power system and operations research require repeatedly solving large-scale linear programming problems with a large number of different inputs. For example, in energy systems with high levels of uncertain renewable resources, tens of thousands of scenarios may need to be solved every few minutes. Standard iterative algorithms for linear network flow problems, even though highly efficient, becomes a bottleneck in these applications. In this work, we propose a novel learning approach to accelerate the solving process. By leveraging the rich theory and economic interpretations of LP duality, we interpret the output of the neural network as a noisy codeword, where the codebook is given by the optimization problem's KKT conditions. We propose a feedforward decoding strategy that finds the optimal set of active constraints. This design is error correcting and can offer orders of magnitude speedup compared to current state-of-the-art iterative solvers, while providing much better solutions in terms of feasibility and optimality compared to end-to-end learning approaches.

arXiv commentIn submission

References in corpus (10)

• End to End Learning for Self-Driving Cars
• Learning Combinatorial Optimization Algorithms over Graphs
• Spatial Deep Learning for Wireless Scheduling
• Exact Combinatorial Optimization with Graph Convolutional Neural Networks
• OptNet: Differentiable Optimization as a Layer in Neural Networks
• Differentiable Convex Optimization Layers
• Task-based End-to-end Model Learning in Stochastic Optimization
• DeepOPF: A Deep Neural Network Approach for Security-Constrained DC Optimal Power Flow
• Hierarchical Decision Making In Electricity Grid Management
• Probabilistic Forecasting and Simulation of Electricity Markets via Online Dictionary Learning

Cited by in corpus (9)

• Flow Network based Generative Models for Non-Iterative Diverse Candidate Generation
• Learning Active Constraints to Efficiently Solve Linear Bilevel Problems: Application to the Generator Strategic Bidding Problem
• Neural Networks for Encoding Dynamic Security-Constrained Optimal Power Flow
• Learning to Solve AC Optimal Power Flow by Differentiating through Holomorphic Embeddings
• A Convex Neural Network Solver for DCOPF with Generalization Guarantees
• DeepOPF-V: Solving AC-OPF Problems Efficiently
• Graph Neural Networks for Learning Real-Time Prices in Electricity Market
• SAVER: Safe Learning-Based Controller for Real-Time Voltage Regulation
• A short note on solving box inequality and linear equality constrained optimization problem