Ensemble Variance Reduction Methods for Stochastic Mixed-Integer Programming and their Application to the Stochastic Facility Location Problem

Jiajun Xu () and Suvrajeet Sen ()
Additional contact information
Jiajun Xu: Ming Hsieh Department of Electrical and Computer Engineering, University of Southern California, Los Angeles, California 90089
Suvrajeet Sen: Daniel J. Epstein Department of Industrial & Systems Engineering, University of Southern California, Los Angeles, California 90089

INFORMS Journal on Computing, 2024, vol. 36, issue 2, 587-599

Abstract: Sample average approximation (SAA), the standard approach to stochastic mixed-integer programming, does not provide guidance for cases with limited computational budgets. In such settings, variance reduction is critical in identifying good decisions. This paper explores two closely related ensemble methods to determine effective decisions with a probabilistic guarantee. (a) The first approach recommends a decision by coordinating aggregation in the space of decisions as well as aggregation of objective values. This combination of aggregation methods generalizes the bagging method and the “compromise decision” of stochastic linear programming. Combining these concepts, we propose a stopping rule that provides an upper bound on the probability of early termination. (b) The second approach applies efficient computational budget allocation for objective function evaluation and contributes to identifying the best solution with a predicted lower bound on the probability of correct selection. It also reduces the variance of the upper bound estimate at optimality. Furthermore, it adaptively selects the evaluation sample size. Both approaches provide approximately optimal solutions even in cases with a huge number of scenarios, especially when scenarios are generated by using oracles/simulators. Finally, we demonstrate the effectiveness of these methods via extensive computational results for “megascale” (extremely large scale) stochastic facility location problems.

Keywords: stochastic mixed-integer programming; sample average approximation; variance reduction; bagging; compromise decisions; facility location problem (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.0324 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:36:y:2024:i:2:p:587-599

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().