A learning-based algorithm to quickly compute good primal solutions for Stochastic Integer Programs

By Yoshua Bengio, Emma Frejinger, Andrea Lodi, Rahul Patel, Sriram Sankaranarayanan. 2019

31 citations recorded by the source corpus.

We propose a novel approach using supervised learning to obtain near-optimal primal solutions for two-stage stochastic integer programming (2SIP) problems with constraints in the first and second stages. The goal of the algorithm is to predict a "representative scenario" (RS) for the problem such that, deterministically solving the 2SIP with the random realization equal to the RS, gives a near-optimal solution to the original 2SIP. Predicting an RS, instead of directly predicting a solution ensures first-stage feasibility of the solution. If the problem is known to have complete recourse, second-stage feasibility is also guaranteed. For computational testing, we learn to find an RS for a two-stage stochastic facility location problem with integer variables and linear constraints in both stages and consistently provide near-optimal solutions. Our computing times are very competitive with those of general-purpose integer programming solvers to achieve a similar solution quality.

Subfields: Computer Networks and Communications, Management Science and Operations Research, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

1. Simon Lacoste-Julien
2. Andrea Lodi
3. Yoshua Bengio
4. Emma Frejinger
5. François Soumis

In Management Science and Operations Research

1. Yoshua Bengio
2. Sébastien Lachapelle
3. Simon Lacoste-Julien
4. Andrea Lodi
5. Eric Larsen
6. Emma Frejinger

In Mathematical Optimization

1. Sébastien Lachapelle
2. Simon Lacoste-Julien
3. Andrea Lodi
4. Yoshua Bengio

Citations in the corpus

• Predicting Tactical Solutions to Operational Planning Problems under Imperfect Information (2018, background): “In this area of research, we note for instance Abbasi et al. (2020), Bengio et al. (2019), Nair et al. (2018).”