# USCO-Solver: Solving Undetermined Stochastic Combinatorial Optimization Problems

arXiv: https://arxiv.org/abs/2107.07508 · HTML: https://mlsanity.com/paper/2107.07508/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 79 references that are in the map.
- First posted on arXiv 15 Jul 2021.

## Builds on (most cited first, 25 of 25)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [PointCNN: Convolution On X-Transformed Points](https://mlsanity.com/paper/1801.07791/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [3D Steerable CNNs: Learning Rotationally Equivariant Features in Volumetric Data](https://mlsanity.com/paper/1807.02547/) (2018)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Deep Reinforcement Learning: An Overview](https://mlsanity.com/paper/1701.07274/) (2017)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Deep Closest Point: Learning Representations for Point Cloud Registration](https://mlsanity.com/paper/1905.03304/) (2019)
- [DeepDriving: Learning Affordance for Direct Perception in Autonomous Driving](https://mlsanity.com/paper/1505.00256/) (2015)
- [Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization](https://mlsanity.com/paper/1809.05504/) (2018)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [From Predictive to Prescriptive Analytics](https://mlsanity.com/paper/1402.5481/) (2014)
- [On Learning Sets of Symmetric Elements](https://mlsanity.com/paper/2002.08599/) (2020)
- [Deep Set Prediction Networks](https://mlsanity.com/paper/1906.06565/) (2019)
- [Conditional Affordance Learning for Driving in Urban Environments](https://mlsanity.com/paper/1806.06498/) (2018)
- [FSPool: Learning Set Representations with Featurewise Sort Pooling](https://mlsanity.com/paper/1906.02795/) (2019)
- [The Limitations of Optimization from Samples](https://mlsanity.com/paper/1512.06238/) (2015)
- [A learning-based algorithm to quickly compute good primal solutions for Stochastic Integer Programs](https://mlsanity.com/paper/1912.08112/) (2019)
- [Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover](https://mlsanity.com/paper/1303.0726/) (2013)
- [Learning Influence Functions from Incomplete Observations](https://mlsanity.com/paper/1611.02305/) (2016)
- [Large Margin Learning in Set to Set Similarity Comparison for Person Re-identification](https://mlsanity.com/paper/1708.05512/) (2017)
- [StratLearner: Learning a Strategy for Misinformation Prevention in Social Networks](https://mlsanity.com/paper/2009.14337/) (2020)
- [From Data to Knowledge to Action: A Global Enabler for the 21st Century](https://mlsanity.com/paper/2008.00045/) (2020)

## Built on by (most cited first, 5 of 5)

- [A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization](https://mlsanity.com/paper/2211.03074/) (2022)
- [Benchmarking PtO and PnO Methods in the Predictive Combinatorial Optimization Regime](https://mlsanity.com/paper/2311.07633/) (2023)
- [Social-Inverse: Inverse Decision-making of Social Contagion Management with Task Migrations](https://mlsanity.com/paper/2209.10493/) (2022)
- [Query-decision Regression between Shortest Path and Minimum Steiner Tree](https://mlsanity.com/paper/2402.02211/) (2024)
- [N(CO)2: Neural Combinatorial Optimization with Chance Constraints to Solve Stochastic Orienteering](https://mlsanity.com/paper/2606.18514/) (2026)

## Abstract (arXiv)

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.