Tractable algorithms for chance-constrained combinatorial problems

This paper aims at proposing tractable algorithms to find effectively good solutions to large size chance-constrained combinatorial problems. A new robust model is introduced to deal with uncertainty in mixed-integer linear problems. It is shown to be strongly related to chance-constrained programming when considering pure 0-1 problems. Furthermore, its tractability is highlighted. Then, an optimization … Read more

An integer programming approach for linear programs with probabilistic constraints

Linear programs with joint probabilistic constraints (PCLP) are difficult to solve because the feasible region is not convex. We consider a special case of PCLP in which only the right-hand side is random and this random vector has a finite distribution. We give a mixed-integer programming formulation for this special case and study the relaxation … Read more

From CVaR to Uncertainty Set: Implications in Joint Chance Constrained Optimization

In this paper we review the different tractable approximations of individual chance constraint problems using robust optimization on a varieties of uncertainty set, and show their interesting connections with bounds on the condition-value-at-risk CVaR measure popularized by Rockafellar and Uryasev. We also propose a new formulation for approximating joint chance constrained problems that improves upon … Read more

On Safe Tractable Approximations of Chance Constrained Linear Matrix Inequalities

In the paper, we consider the chance constrained version $$ \Prob\{A_0[x]+\sum_{i=1}^d\zeta_i A_i[x]\succeq0\}\geq1-\epsilon, $$ of an affinely perturbed Linear Matrix Inequality constraint; here $A_i[x]$ are symmetric matrices affinely depending on the decision vector $x$, and $\zeta_1,…,\zeta_d$ are independent of each other random perturbations with light tail distributions (e.g., bounded or Gaussian). Constraints of this type, playing … Read more

Selected Topics in Robust Convex Optimization

Robust Optimization is a rapidly developing methodology for handling optimization problems affected by non-stochastic “uncertain-but-bounded” data perturbations. In this paper, we overview several selected topics in this popular area, specifically, (1) recent extensions of the basic concept of {\sl robust counterpart} of an optimization problem with uncertain data, (2) tractability of robust counterparts, (3) links … Read more

A Tractable Approximation of Stochastic Programming via Robust Optimization

Stochastic programming, despite its immense modeling capabilities, is well known to be computationally excruciating. In this paper, we introduce a unified framework of approximating multiperiod stochastic programming from the perspective of robust optimization. Specifically, we propose a framework that integrates multistage modeling with safeguarding constraints. The framework is computationally tractable in the form of second … Read more

Convex Approximations of Chance Constrained Programs

We consider a chance constrained problem, where one seeks to minimize a convex objective over solutions satisfying, with a given (close to one) probability, a system of randomly perturbed convex constraints. Our goal is to build a computationally tractable approximation of this (typically intractable) problem, i.e., an explicitly given convex optimization program with the feasible … Read more

Scenario Approximations of Chance Constraints

We consider an optimization problem of minimization of a linear function subject to chance constraints. In the multidimensional case this problem is, generically, a problem of minimizing under a nonconvex and difficult to compute constraints and as such is computationally intractable. We investigate the potential of conceptually simple scenario approximation of the chance constraints. The … Read more

On complexity of stochastic programming problems

The main focus of this paper is discussion of complexity of stochastic programming problems. We argue that two-stage (linear) stochastic programming problems with recourse can be solved with a reasonable accuracy by using Monte Carlo sampling techniques, while multi-stage stochastic programs, in general, are intractable. We also discuss complexity of chance constrained problems and multi-stage … Read more