Relating Single-Scenario Facets to the Convex Hull of the Extensive Form of a Stochastic Single-Node Flow Polytope

Stochastic mixed-integer programs (SMIPs) are a widely-used modeling paradigm for sequential decision making under uncertainty. One popular solution approach to solving SMIPs is to solve the so-called “extensive form” directly as a large-scale (deterministic) mixed-integer program. In this work, we consider the question of when a facet-defining inequality for the convex hull of a deterministic, single-scenario subproblem is also facet-defining for the convex hull of the extensive form. We study this question in the context of a stochastic variant of the well-known single-node flow polytope, providing necessary and sufficient conditions for single-scenario facet-defining inequalities to be facet-defining for the convex hull of the extensive form. In particular, we provide mild conditions under which every facet-defining inequality for a single scenario is facet-defining for the convex hull of the extensive form. We also provide a number of corollaries illustrating the applicability of these conditions, as well as generalizing results for the deterministic single-node flow polytope.

Article

Download

View PDF