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

MaRDI QIDQ4609983zbMATH OpenFDO

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

Publication date 27 March 2018

Full work available at URL https://arxiv.org/abs/1504.00076, http://www.heldermann.de/JCA/JCA25/JCA251/jca25012.htm#jca251

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)

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$.

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

Cites work

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

Cited in

(6)

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

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)