论文标题
学习通过神经解码解决网络流问题
Learning to Solve Network Flow Problems via Neural Decoding
论文作者
论文摘要
工程应用中的许多决策问题，例如运输，电力系统和运营研究都需要反复解决大量的线性编程问题，并具有大量不同的输入。例如，在具有高度不确定的可再生资源的能源系统中，可能需要每隔几分钟解决数万个情况。线性网络流问题的标准迭代算法，即使高效，在这些应用中也成为瓶颈。在这项工作中，我们提出了一种新颖的学习方法来加速解决过程。通过利用LP二元性的丰富理论和经济解释，我们将神经网络的输出解释为嘈杂的代码字，其中代码本由优化问题的KKT条件给出。我们提出了一种馈电解码策略，可以找到最佳的主动约束集。该设计是纠正误差，与当前的最新迭代求解器相比，可以提供数量级的速度，同时与端到端学习方法相比，在可行性和最佳性方面提供了更好的解决方案。
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.
