Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

4-2022

Abstract

Many practical combinatorial optimization problems under uncertainty can be modeled as stochastic integer programs (SIPs), which are extremely challenging to solve due to the high complexity. To solve two-stage SIPs efficiently, we propose a conditional variational autoencoder (CVAE) based method to learn scenario representation for a class of SIP instances. Specifically, we design a graph convolutional network based encoder to embed each scenario with the deterministic part of its instance (i.e. context) into a low-dimensional latent space, from which a decoder reconstructs the scenario from its latent representation conditioned on the context. Such a design effectively captures the dependencies of the scenarios on their corresponding instances. We apply the trained encoder to two tasks in typical SIP solving, i.e. scenario reduction and objective prediction. Experiments on two graph-based SIPs show that the learned representation significantly boosts the solving performance to attain high-quality solutions in short computational time, and generalizes fairly well to problems of larger sizes or with more scenarios.

Keywords

Auto encoders, Combinatorial optimization problems, Convolutional networks, High complexity, Integer program, Learn+, Learning scenarios, Network-based, Stochastics, Uncertainty

Discipline

Databases and Information Systems | OS and Networks

Publication

Proceedings of the 10th International Conference on Learning Representations, ICLR 2022, Virtual Online, Apr 25-29

Publisher

International Conference on Learning Representations, ICLR

City or Country

Virtual, Online

Copyright Owner and License

Authors

Download

Share

COinS