Probabilistic partial set covering with an oracle for chance constraints
From MaRDI portal
Publication:4629339
DOI10.1137/17M1141576zbMATH Open1414.90250DBLPjournals/siamjo/WuK19arXiv1708.02505OpenAlexW2919175449WikidataQ90802306 ScholiaQ90802306MaRDI QIDQ4629339FDOQ4629339
Authors: Hao-Hsiang Wu, Simge Küçükyavuz 
Publication date: 22 March 2019
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Abstract: We investigate a class of chance-constrained combinatorial optimization problems. Given a pre-specified risk level , the chance-constrained program aims to find the minimum cost selection of a vector of binary decisions such that a desirable event occurs with probability at least . In this paper, we assume that we have an oracle that computes exactly. Using this oracle, we propose a general exact method for solving the chance-constrained problem. In addition, we show that if the chance-constrained program is solved approximately by a sampling-based approach, then the oracle can be used as a tool for checking and fixing the feasibility of the optimal solution given by this approach. We demonstrate the effectiveness of our proposed methods on a variant of the probabilistic set covering problem (PSC), which admits an efficient probability oracle. We give a compact mixed-integer program that solves PSC optimally (without sampling) for a special case. For large-scale instances for which the exact methods exhibit slow convergence, we propose a sampling-based approach that exploits the special structure of PSC. In particular, we introduce a new class of facet-defining inequalities for a submodular substructure of PSC, and show that a sampling-based algorithm coupled with the probability oracle solves the large-scale test instances effectively.
Full work available at URL: https://arxiv.org/abs/1708.02505
Recommendations
Cites Work
- Random graphs and complex networks. Volume 1
- On the Distribution of the Number of Successes in Independent Trials
- The Structure and Function of Complex Networks
- Title not available (Why is that?)
- On the Number of Successes in Independent Trials
- Computing k-out-of-n System Reliability
- Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
- Reducibility among combinatorial problems
- Title not available (Why is that?)
- A Sample Approximation Approach for Optimization with Probabilistic Constraints
- Mixed-integer bilinear programming problems
- Title not available (Why is that?)
- On mixing sets arising in chance-constrained programming
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
- A user's guide to measure theoretic probability
- Constrained bundle methods for upper inexact oracles with application to joint chance constrained energy problems
- Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra
- On the mixing set with a knapsack constraint
- Decomposition algorithms for two-stage chance-constrained programs
- Chance-Constrained Binary Packing Problems
- The Probabilistic Set-Covering Problem
- A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support
- Contributions to the theory of stochastic programming
- Dual method for the solution of a one-stage stochastic programming problem with random RHS obeying a discrete probability distribution
- The integer \(L\)-shaped method for stochastic integer programs with complete recourse
- MIP reformulations of the probabilistic set covering problem
- An integer programming approach for linear programs with probabilistic constraints
- Pattern-based modeling and solution of probabilistically constrained optimization problems
- Probabilistic set covering with correlations
- An exact approach for solving integer problems under probabilistic constraints with random technology matrix
- Scenario approximations of chance constraints
- Cutting plane versus compact formulations for uncertain (integer) linear programs
- A probabilistic analysis of the maximal covering location problem
- Human sexual contact network as a bipartite graph
- Inexact stabilized Benders' decomposition approaches with application to chance-constrained problems with finite support
- Title not available (Why is that?)
- A polyhedral study on chance constrained program with random right-hand side
- A polyhedral study of the static probabilistic lot-sizing problem
- A two-stage stochastic programming approach for influence maximization in social networks
- On intersection of two mixing sets with applications to joint chance-constrained programs
Cited In (13)
- State-Variable Modeling for a Class of Two-Stage Stochastic Optimization Problems
- A discussion of probability functions and constraints from a variational perspective
- Efficient presolving methods for the influence maximization problem
- MIP reformulations of the probabilistic set covering problem
- Robust min-max regret covering problems
- Online non-monotone diminishing return submodular maximization in the bandit setting
- A polyhedral approach to bisubmodular function minimization
- An exact method for constrained maximization of the conditional value-at-risk of a class of stochastic submodular functions
- Probabilistic set covering with correlations
- An exact cutting plane method for \(k\)-submodular function maximization
- Chance-constrained set covering with Wasserstein ambiguity
- Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints
- Chance-constrained optimization under limited distributional information: a review of reformulations based on sampling and distributional robustness
This page was built for publication: Probabilistic partial set covering with an oracle for chance constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629339)
