USCO-Solver: Solving Undetermined Stochastic Combinatorial Optimization Problems
arXiv:2107.07508
Abstract
Real-world decision-making systems are often subject to uncertainties that have to be resolved through observational data. Therefore, we are frequently confronted with combinatorial optimization problems of which the objective function is unknown and thus has to be debunked using empirical evidence. In contrast to the common practice that relies on a learning-and-optimization strategy, we consider the regression between combinatorial spaces, aiming to infer high-quality optimization solutions from samples of input-solution pairs -- without the need to learn the objective function. Our main deliverable is a universal solver that is able to handle abstract undetermined stochastic combinatorial optimization problems. For learning foundations, we present learning-error analysis under the PAC-Bayesian framework using a new margin-based analysis. In empirical studies, we demonstrate our design using proof-of-concept experiments, and compare it with other methods that are potentially applicable. Overall, we obtain highly encouraging experimental results for several classic combinatorial problems on both synthetic and real-world datasets.
arXiv commentNeurIPS 2021
References in corpus (13)
- Semi-Supervised Classification with Graph Convolutional Networks
- The Dynamics of Viral Marketing
- Learning Combinatorial Optimization Algorithms over Graphs
- Kronecker Graphs: An Approach to Modeling Networks
- Deep Reinforcement Learning: An Overview
- 3D Steerable CNNs: Learning Rotationally Equivariant Features in Volumetric Data
- Reinforcement Learning for Solving the Vehicle Routing Problem
- Structured Prediction Cascades
- Deep Set Prediction Networks
- On Learning Sets of Symmetric Elements
- FSPool: Learning Set Representations with Featurewise Sort Pooling
- Learning Influence Functions from Incomplete Observations
- From Data to Knowledge to Action: A Global Enabler for the 21st Century