On solving two-stage distributionally robust disjunctive programs with a general ambiguity set

Manish Bansal*, Sanjay Mehrotra

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

We introduce two-stage distributionally robust disjunctive programs (TSDR-DPs) with disjunctive constraints in both stages and a general ambiguity set for the probability distributions. The TSDR-DPs subsume various classes of two-stage distributionally robust programs where the second stage problems are non-convex programs (such as mixed binary programs, semi-continuous program, nonconvex quadratic programs, separable non-linear programs, etc.). TSDR-DP is an optimization model in which the degree of risk aversion can be chosen by decision makers. It generalizes two-stage stochastic disjunctive program (risk-neutral) and two-stage robust disjunctive program (most-conservative). To our knowledge, the foregoing special cases of TSDR-DPs have not been studied until now. In this paper, we develop decomposition algorithms, which utilize Balas’ linear programming equivalent for deterministic disjunctive programs or his sequential convexification approach within L-shaped method, to solve TSDR-DPs. We present sufficient conditions under which our algorithms are finitely convergent. These algorithms generalize the distributionally robust integer L-shaped algorithm of Bansal et al. (SIAM J. on Optimization 28: 2360-2388, 2018) for TSDR mixed binary programs, a subclass of TSDR-DPs. Furthermore, we formulate a semi-continuous program (SCP) as a disjunctive program and use our results for TSDR-DPs to solve general two-stage distributionally robust SCPs (TSDR-SCPs) and TSDR-SCP having semi-continuous inflow set in the second stage.

Original languageEnglish (US)
Pages (from-to)296-307
Number of pages12
JournalEuropean Journal of Operational Research
Volume279
Issue number2
DOIs
StatePublished - Dec 1 2019

Fingerprint

Linear programming
Probability distributions
Decomposition
Ambiguity
Binary
Convexification
Generalise
Quadratic Program
Risk Aversion
Decomposition Algorithm
Optimization Model
Probability Distribution
Integer
Optimization
Sufficient Conditions

Keywords

  • Decomposition algorithms
  • Distributionally robust disjunctive programs
  • Reverse convex program
  • Semi-continuous program
  • Stochastic programming

ASJC Scopus subject areas

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this

@article{dc13f3f431d54ed2aca518333163f7ed,
title = "On solving two-stage distributionally robust disjunctive programs with a general ambiguity set",
abstract = "We introduce two-stage distributionally robust disjunctive programs (TSDR-DPs) with disjunctive constraints in both stages and a general ambiguity set for the probability distributions. The TSDR-DPs subsume various classes of two-stage distributionally robust programs where the second stage problems are non-convex programs (such as mixed binary programs, semi-continuous program, nonconvex quadratic programs, separable non-linear programs, etc.). TSDR-DP is an optimization model in which the degree of risk aversion can be chosen by decision makers. It generalizes two-stage stochastic disjunctive program (risk-neutral) and two-stage robust disjunctive program (most-conservative). To our knowledge, the foregoing special cases of TSDR-DPs have not been studied until now. In this paper, we develop decomposition algorithms, which utilize Balas’ linear programming equivalent for deterministic disjunctive programs or his sequential convexification approach within L-shaped method, to solve TSDR-DPs. We present sufficient conditions under which our algorithms are finitely convergent. These algorithms generalize the distributionally robust integer L-shaped algorithm of Bansal et al. (SIAM J. on Optimization 28: 2360-2388, 2018) for TSDR mixed binary programs, a subclass of TSDR-DPs. Furthermore, we formulate a semi-continuous program (SCP) as a disjunctive program and use our results for TSDR-DPs to solve general two-stage distributionally robust SCPs (TSDR-SCPs) and TSDR-SCP having semi-continuous inflow set in the second stage.",
keywords = "Decomposition algorithms, Distributionally robust disjunctive programs, Reverse convex program, Semi-continuous program, Stochastic programming",
author = "Manish Bansal and Sanjay Mehrotra",
year = "2019",
month = "12",
day = "1",
doi = "10.1016/j.ejor.2019.05.033",
language = "English (US)",
volume = "279",
pages = "296--307",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "2",

}

On solving two-stage distributionally robust disjunctive programs with a general ambiguity set. / Bansal, Manish; Mehrotra, Sanjay.

In: European Journal of Operational Research, Vol. 279, No. 2, 01.12.2019, p. 296-307.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On solving two-stage distributionally robust disjunctive programs with a general ambiguity set

AU - Bansal, Manish

AU - Mehrotra, Sanjay

PY - 2019/12/1

Y1 - 2019/12/1

N2 - We introduce two-stage distributionally robust disjunctive programs (TSDR-DPs) with disjunctive constraints in both stages and a general ambiguity set for the probability distributions. The TSDR-DPs subsume various classes of two-stage distributionally robust programs where the second stage problems are non-convex programs (such as mixed binary programs, semi-continuous program, nonconvex quadratic programs, separable non-linear programs, etc.). TSDR-DP is an optimization model in which the degree of risk aversion can be chosen by decision makers. It generalizes two-stage stochastic disjunctive program (risk-neutral) and two-stage robust disjunctive program (most-conservative). To our knowledge, the foregoing special cases of TSDR-DPs have not been studied until now. In this paper, we develop decomposition algorithms, which utilize Balas’ linear programming equivalent for deterministic disjunctive programs or his sequential convexification approach within L-shaped method, to solve TSDR-DPs. We present sufficient conditions under which our algorithms are finitely convergent. These algorithms generalize the distributionally robust integer L-shaped algorithm of Bansal et al. (SIAM J. on Optimization 28: 2360-2388, 2018) for TSDR mixed binary programs, a subclass of TSDR-DPs. Furthermore, we formulate a semi-continuous program (SCP) as a disjunctive program and use our results for TSDR-DPs to solve general two-stage distributionally robust SCPs (TSDR-SCPs) and TSDR-SCP having semi-continuous inflow set in the second stage.

AB - We introduce two-stage distributionally robust disjunctive programs (TSDR-DPs) with disjunctive constraints in both stages and a general ambiguity set for the probability distributions. The TSDR-DPs subsume various classes of two-stage distributionally robust programs where the second stage problems are non-convex programs (such as mixed binary programs, semi-continuous program, nonconvex quadratic programs, separable non-linear programs, etc.). TSDR-DP is an optimization model in which the degree of risk aversion can be chosen by decision makers. It generalizes two-stage stochastic disjunctive program (risk-neutral) and two-stage robust disjunctive program (most-conservative). To our knowledge, the foregoing special cases of TSDR-DPs have not been studied until now. In this paper, we develop decomposition algorithms, which utilize Balas’ linear programming equivalent for deterministic disjunctive programs or his sequential convexification approach within L-shaped method, to solve TSDR-DPs. We present sufficient conditions under which our algorithms are finitely convergent. These algorithms generalize the distributionally robust integer L-shaped algorithm of Bansal et al. (SIAM J. on Optimization 28: 2360-2388, 2018) for TSDR mixed binary programs, a subclass of TSDR-DPs. Furthermore, we formulate a semi-continuous program (SCP) as a disjunctive program and use our results for TSDR-DPs to solve general two-stage distributionally robust SCPs (TSDR-SCPs) and TSDR-SCP having semi-continuous inflow set in the second stage.

KW - Decomposition algorithms

KW - Distributionally robust disjunctive programs

KW - Reverse convex program

KW - Semi-continuous program

KW - Stochastic programming

UR - http://www.scopus.com/inward/record.url?scp=85067256965&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85067256965&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2019.05.033

DO - 10.1016/j.ejor.2019.05.033

M3 - Article

AN - SCOPUS:85067256965

VL - 279

SP - 296

EP - 307

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

ER -