Learning Linear Programs from Optimal Decisions
This work addresses the problem of automating linear program specification for practitioners in optimization and machine learning, though it appears incremental as it builds on existing inverse optimization literature.
The authors tackled the problem of learning linear programs from observed optimal decisions, a challenging bi-level inverse optimization task, and developed a flexible gradient-based framework that jointly learns all parameters and handles issues like empty feasible regions and non-unique solutions. Their method successfully learned synthetic linear programs and multi-commodity flow instances where previous approaches failed, with a fast PyTorch implementation provided.
We propose a flexible gradient-based framework for learning linear programs from optimal decisions. Linear programs are often specified by hand, using prior knowledge of relevant costs and constraints. In some applications, linear programs must instead be learned from observations of optimal decisions. Learning from optimal decisions is a particularly challenging bi-level problem, and much of the related inverse optimization literature is dedicated to special cases. We tackle the general problem, learning all parameters jointly while allowing flexible parametrizations of costs, constraints, and loss functions. We also address challenges specific to learning linear programs, such as empty feasible regions and non-unique optimal decisions. Experiments show that our method successfully learns synthetic linear programs and minimum-cost multi-commodity flow instances for which previous methods are not directly applicable. We also provide a fast batch-mode PyTorch implementation of the homogeneous interior point algorithm, which supports gradients by implicit differentiation or backpropagation.