Learning scenario representation for solving two-stage stochastic integer programs

• Main Authors: WU, Yaoxin, SONG, Wen, CAO, Zhiguang, ZHANG, Jie
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2022
• Subjects: Auto encoders; Combinatorial optimization problems; Convolutional networks; High complexity; Integer program; Learn+; Learning scenarios; Network-based; Stochastics; Uncertainty; Databases and Information Systems; OS and Networks
• Online Access: https://ink.library.smu.edu.sg/sis_research/8163; https://ink.library.smu.edu.sg/context/sis_research/article/9166/viewcontent/LEARNING_SCENARIO_REPRESENTATION_FOR_SOLVING_TWO_STAGE_STOCHASTIC_INTEGER_PROGRAMS.pdf
• Institution: Singapore Management University

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.