Threshold Boolean form for joint probabilistic constraints with random technology matrix

Alexander Kogan, Miguel A. Lejeune

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

Abstract

We develop a new modeling and solution method for stochastic programming problems that include a joint probabilistic constraint in which the multirow random technology matrix is discretely distributed. We binarize the probability distribution of the random variables in such a way that we can extract a threshold partially defined Boolean function (pdBf) representing the probabilistic constraint. We then construct a tight threshold Boolean minorant for the pdBf. Any separating structure of the tight threshold Boolean minorant defines sufficient conditions for the satisfaction of the probabilistic constraint and takes the form of a system of linear constraints. We use the separating structure to derive three new deterministic formulations for the studied stochastic problem, and we derive a set of strengthening valid inequalities. A crucial feature of the new integer formulations is that the number of integer variables does not depend on the number of scenarios used to represent uncertainty. The computational study, based on instances of the stochastic capital rationing problem, shows that the mixed-integer linear programming formulations are orders of magnitude faster to solve than the mixed-integer nonlinear programming formulation. The method integrating the valid inequalities in a branch-and-bound algorithm has the best performance.

Original languageEnglish (US)
Pages (from-to)391-427
Number of pages37
JournalMathematical Programming
Volume147
Issue number1-2
DOIs
StatePublished - Oct 2013

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Keywords

  • Boolean function
  • Joint probabilistic constraint
  • Minorant
  • Random technology matrix
  • Stochastic programming
  • Threshold function

Fingerprint

Dive into the research topics of 'Threshold Boolean form for joint probabilistic constraints with random technology matrix'. Together they form a unique fingerprint.

Cite this