On Mixing Sets Arising in Probabilistic Programming

Simge Kucukyavuz (kucukyavuz.2osu.edu)

Abstract: The mixing set with a knapsack constraint arises in deterministic equivalent of probabilistic programming problems with finite discrete distributions. We first consider the case that the probabilistic program has equal probabilities for each scenario. We study the resulting mixing set with a cardinality constraint and propose facet-defining inequalities that subsume known explicit inequalities for this set. We extend these inequalities to obtain valid inequalities for the mixing set with a knapsack constraint. In addition, we propose a compact extended reformulation (with polynomial number of variables and constraints) that characterizes a linear programming equivalent of a single probabilistic constraint with equal scenario probabilities. We introduce a blending procedure to find valid inequalities for intersection of multiple mixing sets. We propose a polynomial-size extended formulation for the intersection of multiple mixing sets with a knapsack constraint that is stronger than the original mixing formulation. We also give a compact extended linear program for the intersection of multiple mixing sets and a cardinality constraint for a special case. We illustrate the effectiveness of the proposed inequalities in our computational experiments with probabilistic lot-sizing problems.

Keywords: Mixed-integer programming, facets, compact extended formulations, probabilistic constraints, lot-sizing, computation.

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Stochastic Programming

Citation: Industrial and Systems Engineering, Ohio State University, 03/2009.

Download: [PDF]

Entry Submitted: 03/16/2009
Entry Accepted: 03/17/2009
Entry Last Modified: 10/07/2009

Modify/Update this entry