2023/01/31 by Daniel McKenzie, Samy Wu Fung, McKenzie, Daniel +3 · 3 citations
Computer Science · Engineering · #Advanced Neural Network Applications #FOS: Computer and information sciences #Machine Learning (cs.LG) #Optimization and Packing Problems #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2301.13395
openalex publication_date 2023/01/31 · openalex created_date 2023/02/03 · openalex updated_date 2026/07/28
In many applications, a combinatorial problem must be repeatedly solved with similar, but distinct parameters. Yet, the parameters w are not directly observed; only contextual data d that correlates with w is available. It is tempting to use a neural network to predict w given d. However, training such a model requires reconciling the discrete nature of combinatorial optimization with the gradient-based frameworks used to train neural networks. We study the case where the problem in question is an Integer Linear Program (ILP). We propose applying a three-operator splitting technique, also known as Davis-Yin splitting (DYS), to the quadratically regularized continuous relaxation of the ILP. We prove that the resulting scheme is compatible with the recently introduced Jacobian-free backpropagation (JFB). Our experiments on two representative ILPs: the shortest path problem and the knapsack problem, demonstrate that this combination-DYS on the forward pass, JFB on the backward pass-yields a scheme which scales more effectively to high-dimensional problems than existing schemes. All code associated with this paper is available at github.com/mines-opt-ml/fpo-dys.