Beyond Chance-Constrained Convex Mixed-Integer Optimization: A Generalized Calafiore-Campi Algorithm and the notion of S-optimization

zbMATH Open1390.90405arXiv1504.00076MaRDI QIDQ4609983FDOQ4609983

Edgardo Roldán-Pensado, Deborah Oliveros, Jesús A. De Loera, Reuben N. La Haye

Publication date: 27 March 2018

Abstract: The scenario approach developed by Calafiore and Campi to attack chance-constrained convex programs utilizes random sampling on the uncertainty parameter to substitute the original problem with a representative continuous convex optimization with $N$ convex constraints which is a relaxation of the original. Calafiore and Campi provided an explicit estimate on the size $N$ of the sampling relaxation to yield high-likelihood feasible solutions of the chance-constrained problem. They measured the probability of the original constraints to be violated by the random optimal solution from the relaxation of size $N$. This paper has two main contributions. First, we present a generalization of the Calafiore-Campi results to both integer and mixed-integer variables. In fact, we demonstrate that their sampling estimates work naturally for variables restricted to some subset $S$ of $mathbb{R}^d$. The key elements are generalizations of Helly's theorem where the convex sets are required to intersect $Ssubsetmathbb{R}^d$. The size of samples in both algorithms will be directly determined by the $S$-Helly numbers. Motivated by the first half of the paper, for any subset $Ssubsetmathbb{R}^d$, we introduce the notion of an $S$-optimization problem, where the variables take on values over $S$. It generalizes continuous, integer, and mixed-integer optimization. We illustrate with examples the expressive power of $S$-optimization to capture sophisticated combinatorial optimization problems with difficult modular constraints. We reinforce the evidence that $S$-optimization is "the right concept" by showing that the well-known randomized sampling algorithm of K. Clarkson for low-dimensional convex optimization problems can be extended to work with variables taking values over $S$.

Full work available at URL: https://arxiv.org/abs/1504.00076

Recommendations

• Sample approximation technique for mixed-integer stochastic programming problems with several chance constraints
• A sampling-and-discarding approach to chance-constrained optimization: feasibility and Optimality
• Sample average approximation method for chance constrained programming: Theory and applications
• Sample approximation technique for mixed-integer stochastic programming problems with expected value constraints
• Randomized solutions to convex programs with multiple chance constraints
• Convex Approximations of Chance Constrained Programs
• Convex relaxations of chance constrained optimization problems
• A Sample Approximation Approach for Optimization with Probabilistic Constraints
• On the expected probability of constraint violation in sampled convex programs
• On the convergence of sampling algorithms for solving dynamic stochastic programming

zbMATH Keywords

combinatorial convexitychance-constrained optimizationHelly-type theoremsconvexity spacesconvex mixed-integer optimizationoptimization with restricted variable valuesrandomized sampling algorithmsS-optimization

Mathematics Subject Classification ID

Stochastic programming (90C15) Mixed integer programming (90C11) Programming in abstract spaces (90C48)

Cites Work

• Uncertain convex programs: randomized solutions and confidence levels
• Title not available (Why is that?)
• A Sample Approximation Approach for Optimization with Probabilistic Constraints
• The Scenario Approach to Robust Control Design
• Las Vegas algorithms for linear and integer programming when the dimension is small
• Algorithms - ESA 2003
• Helly-type theorems and generalized linear programming
• Title not available (Why is that?)
• A combinatorial bound for linear programming and related problems
• Violator spaces: Structure and algorithms
• Lectures on stochastic programming. Modeling and theory.
• Sample average approximation method for chance constrained programming: Theory and applications
• The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs
• Partition numbers for trees and ordered sets
• Designing robust emergency medical service via stochastic programming
• Convexity in cristallographical lattices
• Transversal numbers over subsets of linear spaces
• Bounds for probabilistic integer programming problems
• Axiomatic convexity theory and relationships between the Carathéodory, Helly, and Radon numbers
• An observation on the structure of production sets with indivisibilities
• A Theorem Concerning the Integer Lattice
• Mixed integer linear programming formulations for probabilistic constraints
• Probabilistic Formulation of the Emergency Service Location Problem
• Title not available (Why is that?)
• Flat transversals to flats and convex sets of a fixed dimension
• A probabilistic quality of service constraint for a location model of switches in ATM communications networks
• Centerpoints: A Link between Optimization and Convex Geometry
• A Tverberg-type generalization of the Helly number of a convexity space
• Title not available (Why is that?)
• Integer Programming over a Finite Additive Group
• Helly numbers of algebraic subsets of \(\mathbb{R}^{d}\) and an extension of Doignon's theorem
• Optimality certificates for convex minimization and Helly numbers

Cited In (6)

• Quantitative Tverberg theorems over lattices and other discrete sets
• Sample approximation technique for mixed-integer stochastic programming problems with several chance constraints
• Random sampling with removal
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Centerpoints: A Link between Optimization and Convex Geometry
• Helly numbers of algebraic subsets of \(\mathbb{R}^{d}\) and an extension of Doignon's theorem

This page was built for publication: Beyond Chance-Constrained Convex Mixed-Integer Optimization: A Generalized Calafiore-Campi Algorithm and the notion of $S$-optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4609983)