English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We investigate a class of chance-constrained combinatorial optimizationproblems. Given a pre-specified risk level $\epsilon \in [0,1]$, thechance-constrained program aims to find the minimum cost selection of a vectorof binary decisions $x$ such that a desirable event $\mathcal{B}(x)$ occurswith probability at least $ 1-\epsilon$. In this paper, we assume that we havean oracle that computes $\mathbb P( \mathcal{B}(x))$ exactly. Using thisoracle, we propose a general exact method for solving the chance-constrainedproblem. In addition, we show that if the chance-constrained program is solvedapproximately by a sampling-based approach, then the oracle can be used as atool for checking and fixing the feasibility of the optimal solution given bythis approach. We demonstrate the effectiveness of our proposed methods on avariant of the probabilistic set covering problem (PSC), which admits anefficient probability oracle. We give a compact mixed-integer program thatsolves PSC optimally (without sampling) for a special case. For large-scaleinstances for which the exact methods exhibit slow convergence, we propose asampling-based approach that exploits the special structure of PSC. Inparticular, we introduce a new class of facet-defining inequalities for asubmodular substructure of PSC, and show that a sampling-based algorithmcoupled with the probability oracle solves the large-scale test instanceseffectively.

Chance-Constrained Combinatorial Optimization with a Probability Oracle and Its Application to Probabilistic Partial Set Covering