Probabilistic partial set covering with an oracle for chance constraints

Hao Hsiang Wu, Simge Kucukyavuz*

*Corresponding author for this work

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

We consider a class of chance-constrained combinatorial optimization problems, which we refer to as probabilistic partial set-covering (PPSC) problems. Given a prespecified risk level 2 [0; 1], the PPSC problem aims to find the minimum cost selection of subsets of items such that a target number of items is covered with probability at least 1. We show that PPSC admits an efficient probability oracle that computes the coverage probability exactly, under certain distributions of the random variables representing the coverage relation. Using this oracle, we give a compact mixed-integer program that solves the PPSC problem for a special case. For large-scale instances for which an exact oracle-based method exhibits slow convergence, we propose a samplingbased approach that exploits the special structure of PPSC. The oracle can be used as a tool for checking and fixing the feasibility of the solution given by this approach. In particular, we introduce a new class of facet-defining inequalities for a submodular substructure of PPSC, and show that a sampling-based algorithm coupled with the probability oracle effectively provides high-quality feasible solutions to the large-scale test instances.

Original languageEnglish (US)
Pages (from-to)690-718
Number of pages29
JournalSIAM Journal on Optimization
Volume29
Issue number1
DOIs
StatePublished - Jan 1 2019

Keywords

  • Chance constraints
  • Facets
  • Oracle
  • Probabilistic set covering
  • Stochastic programming
  • Submodularity

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'Probabilistic partial set covering with an oracle for chance constraints'. Together they form a unique fingerprint.

  • Cite this