pith. sign in

arxiv: 2411.04237 · v2 · submitted 2024-11-06 · 🧮 math.OC

Chance-Constrained Set Multicover Problem

Shunyu Yao , Neng Fan , Pavlo Krokhmal This is my paper

Pith reviewed 2026-05-23 17:19 UTC · model grok-4.3

classification 🧮 math.OC
keywords chance-constrained optimizationset multicover problemouter approximation algorithmdeterministic reformulationdiscrete probability distributionsample average approximation
0
0 comments X

The pith

The chance-constrained set multicover problem admits exact deterministic reformulations featuring a hierarchy of bounds solved by an outer-approximation algorithm.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper formulates the chance-constrained set multicover problem in which selected sets cover each item a required number of times only with a given probability under uncertain coverage. It converts the stochastic problem into equivalent deterministic optimization models by enumerating the joint outcomes of the discrete probability distributions that govern coverage. These models include a hierarchy of successively tighter bounds that support an outer-approximation algorithm for finding minimum-cost solutions. The work also reduces the number of constraints through vector dominance and gives closed-form reformulations for binomial and log-transformed special cases while analyzing sampling approximations. A reader would care because the approach replaces sampling-based estimates with provably exact solutions when the uncertainty is discrete and enumerable.

Core claim

Using enumerative combinatorics on discrete probability distributions, the chance-constrained set multicover problem is shown to possess exact equivalent deterministic reformulations that incorporate a hierarchy of bounds; these reformulations are solved by a tailored outer-approximation algorithm. Vector dominance relations can eliminate redundant chance constraints, special cases admit log-transformation or binomial closed forms, and sampling methods such as sample average approximation and importance sampling are analyzed for approximation quality under finite discrete spaces.

What carries the argument

The hierarchy of deterministic reformulations obtained by exhaustive enumeration of joint coverage outcomes for the chance constraints, solved via outer approximation.

If this is right

  • Minimum-cost solutions can be obtained to exact optimality whenever the joint outcomes of the coverage distributions can be enumerated.
  • Vector dominance reduces the number of chance constraints that must be enforced in the reformulation.
  • Special cases with binomial distributions or log-transformed probabilities admit simpler closed-form deterministic equivalents.
  • The outer-approximation method is especially effective when the probability matrix is sparse.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same enumeration-plus-hierarchy technique may apply directly to other chance-constrained covering problems whose uncertainty is also discrete.
  • When distributions are continuous or too large to enumerate, the exact reformulation step would need to be replaced by a different bounding scheme.
  • Computational tests on instances with increasing numbers of items and sets would reveal how quickly the bound hierarchy tightens in practice.

Load-bearing premise

The coverage uncertainty for each set-item pair follows a known discrete probability distribution that permits exact enumeration of joint outcomes for the chance constraints.

What would settle it

A small instance whose true stochastic optimum, obtained by exhaustive scenario enumeration, differs from the optimum returned by the outer-approximation algorithm on the deterministic reformulation.

Figures

Figures reproduced from arXiv: 2411.04237 by Neng Fan, Pavlo Krokhmal, Shunyu Yao.

Figure 1
Figure 1. Figure 1: Convergence of bounds for the cover probability [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Feasibility-ratio and optimality-ratio curves of SAA and IS as functions of sample size [PITH_FULL_IMAGE:figures/full_fig_p020_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The average solution time of the SAA and IS methods as a function of [PITH_FULL_IMAGE:figures/full_fig_p021_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The average solution time of four approaches as a function of [PITH_FULL_IMAGE:figures/full_fig_p038_4.png] view at source ↗
read the original abstract

We consider a variant of the set covering problem with uncertain parameters, which we refer to as the chance-constrained set multicover problem (CC-SMCP). In this problem, we assume that there is uncertainty regarding whether a selected set can cover an item, and the objective is to determine a minimum-cost combination of sets that covers each item $i$ at least $k_i$ times with a prescribed probability. To tackle CC-SMCP, we employ techniques of enumerative combinatorics, discrete probability distributions, and combinatorial optimization to derive exact equivalent deterministic reformulations that feature a hierarchy of bounds, and develop the corresponding outer-approximation (OA) algorithm. Additionally, we consider reducing the number of chance constraints via vector dominance relations and reformulate two special cases of CC-SMCP using the ``log-transformation" method and binomial distribution properties. Theoretical results on sampling-based methods, i.e., the sample average approximation (SAA) method and the importance sampling (IS) method, are also studied to approximate the true optimal value of CC-SMCP under a finite discrete probability space. Our numerical experiments demonstrate the effectiveness of the proposed OA method, particularly in scenarios with sparse probability matrices, outperforming sampling-based approaches in most cases and validating the practical applicability of our solution approaches.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper introduces the chance-constrained set multicover problem (CC-SMCP), in which selected sets cover each item i at least k_i times with probability at least 1-ε under discrete coverage uncertainty. It claims to derive exact deterministic reformulations (with a hierarchy of bounds) via enumerative combinatorics and probability, develops a corresponding outer-approximation (OA) algorithm, reduces constraints via vector dominance, treats two special cases with log-transformation and binomial properties, analyzes SAA and importance sampling, and reports that OA outperforms sampling on sparse probability matrices.

Significance. If the claimed exact reformulations hold and the OA algorithm remains tractable, the work would supply a concrete exact-method alternative to sampling for chance-constrained set multicover problems under known discrete distributions, with the vector-dominance reduction and special-case closed forms as additional strengths.

major comments (3)
  1. [§3] §3 (reformulation derivation): the manuscript states that enumerative combinatorics and discrete distributions yield exact deterministic equivalents featuring a bound hierarchy, yet supplies neither the explicit mapping from the chance constraint P(∑_j y_j X_ij ≥ k_i) ≥ 1-ε to the deterministic form nor a proof of equivalence; this equivalence is load-bearing for every subsequent algorithmic claim.
  2. [§4] §4 (OA algorithm): the master-problem size after scenario enumeration is not bounded; because the support of the coverage random variable for item i is the power set of the sets that can cover i, the formulation size is O(2^|J_i|) unless vector dominance or sparsity is shown to produce a polynomial certificate, and no such certificate or worst-case cardinality result is given.
  3. [Numerical experiments] Numerical experiments section: performance claims (OA outperforming SAA/IS “in most cases”) are stated without instance dimensions, matrix densities, number of replications, or statistical tests; the abstract’s assertion of “effectiveness … particularly in scenarios with sparse probability matrices” therefore cannot be evaluated.
minor comments (2)
  1. Notation for the random variables X_ij and the probability matrices is introduced without an explicit table or running example that would allow a reader to trace a small instance through the reformulation.
  2. The abstract and introduction both mention “a hierarchy of bounds” but the text never states whether these bounds are used inside the OA master problem or only for post-processing; the relationship should be clarified.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive comments, which help clarify the presentation of our results on the chance-constrained set multicover problem. We address each major comment below and indicate the revisions we will make.

read point-by-point responses

  1. Referee: [§3] §3 (reformulation derivation): the manuscript states that enumerative combinatorics and discrete distributions yield exact deterministic equivalents featuring a bound hierarchy, yet supplies neither the explicit mapping from the chance constraint P(∑_j y_j X_ij ≥ k_i) ≥ 1-ε to the deterministic form nor a proof of equivalence; this equivalence is load-bearing for every subsequent algorithmic claim.

    Authors: We agree that an explicit step-by-step mapping from the chance constraint to the deterministic equivalent, together with a formal proof of equivalence, is essential. The current §3 derives the reformulation via enumeration of coverage scenarios under the discrete distribution and introduces the bound hierarchy, but the presentation can be strengthened. In the revised manuscript we will insert a dedicated subsection that (i) explicitly enumerates the feasible coverage patterns for each item i, (ii) writes the probability as a sum over those patterns, and (iii) proves equivalence by showing that any feasible solution to the deterministic form satisfies the original chance constraint and vice versa. The hierarchy of bounds will be derived directly from this construction. revision: yes

  2. Referee: [§4] §4 (OA algorithm): the master-problem size after scenario enumeration is not bounded; because the support of the coverage random variable for item i is the power set of the sets that can cover i, the formulation size is O(2^|J_i|) unless vector dominance or sparsity is shown to produce a polynomial certificate, and no such certificate or worst-case cardinality result is given.

    Authors: The referee correctly notes that, without reduction, the number of scenarios per item is exponential in |J_i|. The vector-dominance relations we introduce eliminate dominated coverage patterns, but we do not supply a formal cardinality bound or a polynomial certificate for the reduced formulation. In the revision we will (a) state explicitly that the reduced master-problem size remains exponential in the worst case, (b) quantify the reduction achieved by vector dominance under the sparsity assumptions used in the experiments, and (c) add a short complexity discussion clarifying that tractability relies on sparsity rather than a polynomial guarantee. No polynomial certificate will be claimed. revision: partial

  3. Referee: Numerical experiments section: performance claims (OA outperforming SAA/IS “in most cases”) are stated without instance dimensions, matrix densities, number of replications, or statistical tests; the abstract’s assertion of “effectiveness … particularly in scenarios with sparse probability matrices” therefore cannot be evaluated.

    Authors: We acknowledge that the numerical section is missing the requested details. The revised manuscript will expand the experimental section to report: the dimensions (|I|, |J|, k_i values) of all test instances, the densities of the probability matrices, the number of independent replications for SAA and IS, the computational time limits, and any statistical comparisons (e.g., paired t-tests or Wilcoxon tests) used to support the claim that OA outperforms sampling “in most cases.” Tables will also indicate the sparsity levels at which the performance advantage is observed. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected; derivations rely on standard enumerative combinatorics and probability.

full rationale

The abstract and description state that exact deterministic reformulations are derived via enumerative combinatorics, discrete probability distributions, and combinatorial optimization, with an OA algorithm and bound hierarchy. No quoted equations or steps reduce any prediction or reformulation to a fitted input by construction, a self-citation chain, or a renamed ansatz. The approach is presented as self-contained, with vector dominance and special-case log-transformations as additional techniques, not load-bearing self-references. This matches the default expectation of no circularity when the central claims rest on external mathematical techniques rather than internal redefinitions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The approach rests on the existence of a discrete joint probability distribution over coverage outcomes that allows exact reformulation; no free parameters or invented entities are mentioned.

axioms (1)
  • domain assumption Coverage uncertainty is captured by a known discrete probability distribution over set-item outcomes.
    Required to convert chance constraints into deterministic equivalents via enumeration.

pith-pipeline@v0.9.0 · 5760 in / 1118 out tokens · 42437 ms · 2026-05-23T17:19:19.435720+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

51 extracted references · 51 canonical work pages · 1 internal anchor

  1. [1]

    Operations Research 61(2):438--452

    Ahmed S, Papageorgiou DJ (2013) Probabilistic set covering with correlations. Operations Research 61(2):438--452

    work page 2013

  2. [2]

    Mathematical Programming 170:43--65

    Ahmed S, Xie W (2018) Relaxations and approximations of chance constraints under finite distributions. Mathematical Programming 170:43--65

    work page 2018

  3. [3]

    Mathematical Programming 157:153--189

    Barrera J, Homem-de Mello T, Moreno E, Pagnoncelli BK, Canessa G (2016) Chance-constrained problems and rare events: an importance sampling approach. Mathematical Programming 157:153--189

    work page 2016

  4. [4]

    Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust optimization, volume 28 (Princeton university press)

    work page 2009

  5. [5]

    Operations Research 50(6):956--967

    Beraldi P, Ruszczy \'n ski A (2002) The probabilistic set-covering problem. Operations Research 50(6):956--967

    work page 2002

  6. [6]

    Operations Research 45(2):295--301

    Bramel J, Simchi-Levi D (1997) On the effectiveness of set covering formulations for the vehicle routing problem with time windows. Operations Research 45(2):295--301

    work page 1997

  7. [7]

    The vehicle routing problem, 85--108 (SIAM)

    Bramel J, Simchi-Levi D (2002) Set-covering-based algorithms for the capacitated vrp. The vehicle routing problem, 85--108 (SIAM)

    work page 2002

  8. [8]

    Mathematical Programming 102:25--46

    Calafiore G, Campi MC (2005) Uncertain convex programs: randomized solutions and confidence levels. Mathematical Programming 102:25--46

    work page 2005

  9. [9]

    Transportation Science 42(1):1--21

    Campbell AM, Thomas BW (2008) Probabilistic traveling salesman problem with deadlines. Transportation Science 42(1):1--21

    work page 2008

  10. [10]

    Boolean function analysis meets stochastic optimization: An approximation scheme for stochastic knapsack

    De A (2017) Boolean function analysis meets stochastic optimization: An approximation scheme for stochastic knapsack. arXiv preprint arXiv:1712.00918

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  11. [11]

    Mathematical Programming 172(1-2):105--138

    Dinh T, Fukasawa R, Luedtke J (2018) Exact algorithms for the chance-constrained vehicle routing problem. Mathematical Programming 172(1-2):105--138

    work page 2018

  12. [12]

    Mathematical Programming Computation 4(3):239--273

    Fischetti M, Monaci M (2012) Cutting plane versus compact formulations for uncertain (integer) linear programs. Mathematical Programming Computation 4(3):239--273

    work page 2012

  13. [13]

    Operations research 22(1):180--182

    Glover F, Woolsey E (1974) Converting the 0-1 polynomial programming problem to a 0-1 linear program. Operations research 22(1):180--182

    work page 1974

  14. [14]

    Operations Research 40(2):309--330

    Gr \"o tschel M, Monma CL, Stoer M (1992) Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraints. Operations Research 40(2):309--330

    work page 1992

  15. [15]

    European Journal of Operational Research 10(2):190--195

    Gunawardane G (1982) Dynamic versions of set covering type public facility location problems. European Journal of Operational Research 10(2):190--195

    work page 1982

  16. [16]

    Operations research 48(5):697--708

    Haight RG, Revelle CS, Snyder SA (2000) An integer optimization approach to a probabilistic reserve site selection problem. Operations research 48(5):697--708

    work page 2000

  17. [17]

    European Journal of Operational Research 62(3):323--339

    Hall NG, Hochbaum DS (1992) The multicovering problem. European Journal of Operational Research 62(3):323--339

    work page 1992

  18. [18]

    Mathematical Programming 157:277--296

    Han J, Lee K, Lee C, Choi KS, Park S (2016) Robust optimization approach for a chance-constrained binary knapsack problem. Mathematical Programming 157:277--296

    work page 2016

  19. [19]

    Computational Statistics & Data Analysis 59:41--51

    Hong Y (2013) On computing the distribution function for the poisson binomial distribution. Computational Statistics & Data Analysis 59:41--51

    work page 2013

  20. [20]

    Annals of Operations Research 181:271--286

    Huang R, Kim S, Menezes MB (2010) Facility location for large-scale emergencies. Annals of Operations Research 181:271--286

    work page 2010

  21. [21]

    SIAM Journal on optimization 12(2):479--502

    Kleywegt AJ, Shapiro A, Homem-de Mello T (2002) The sample average approximation method for stochastic discrete optimization. SIAM Journal on optimization 12(2):479--502

    work page 2002

  22. [22]

    Operations Research Letters 36(5):628--632

    Klopfenstein O, Nace D (2008) A robust approach to the chance-constrained knapsack problem. Operations Research Letters 36(5):628--632

    work page 2008

  23. [23]

    EURO Journal on Computational Optimization 10:100030

    K \"u c \"u kyavuz S, Jiang R (2022) Chance-constrained optimization under limited distributional information: A review of reformulations based on sampling and distributional robustness. EURO Journal on Computational Optimization 10:100030

    work page 2022

  24. [24]

    Annals of Operations Research 1--22

    Lejeune MA, Pr \'e kopa A (2018) Relaxations for probabilistically constrained stochastic programming problems: review and extensions. Annals of Operations Research 1--22

    work page 2018

  25. [25]

    Lemus Rodriguez GJ (1999) Portfolio optimization with quantile-based risk measures. Ph.D. thesis, Massachusetts Institute of Technology

    work page 1999

  26. [26]

    Computers & Operations Research 98:56--68

    Lessin AM, Lunday BJ, Hill RR (2018) A bilevel exposure-oriented sensor location problem for border security. Computers & Operations Research 98:56--68

    work page 2018

  27. [27]

    Mathematical Programming 146(1-2):219--244

    Luedtke J (2014) A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support. Mathematical Programming 146(1-2):219--244

    work page 2014

  28. [28]

    SIAM Journal on Optimization 19(2):674--699

    Luedtke J, Ahmed S (2008) A sample approximation approach for optimization with probabilistic constraints. SIAM Journal on Optimization 19(2):674--699

    work page 2008

  29. [29]

    Mitzenmacher M, Upfal E (2005) Probability and Computing: Randomized Algorithms and Probabilistic Analysis (Cambridge University Press), ISBN 9780521835404, ://books.google.com/books?id=0bAYl6d7hvkC

    work page 2005

  30. [30]

    SIAM Journal on Optimization 17(4):969--996

    Nemirovski A, Shapiro A (2007) Convex approximations of chance constrained programs. SIAM Journal on Optimization 17(4):969--996

    work page 2007

  31. [31]

    O zener O \

    \"O zener O \"O , Ergun \"O , Savelsbergh M (2013) Allocating cost of service to customers in inventory routing. Operations Research 61(1):112--125

    work page 2013

  32. [32]

    Management Science 35(11):1393--1412

    Padberg M, Rinaldi G (1989) A branch-and-cut approach to a traveling salesman problem with side constraints. Management Science 35(11):1393--1412

    work page 1989

  33. [33]

    Prudnikov A, Brychkov YA, Integrals OM (1998) Series: Volume 2 special functions

    work page 1998

  34. [34]

    (2009) Rare event simulation using Monte Carlo methods, volume 73 (Wiley Online Library)

    Rubino G, Tuffin B, et al. (2009) Rare event simulation using Monte Carlo methods, volume 73 (Wiley Online Library)

    work page 2009

  35. [35]

    Mathematical programming 121(1):1--31

    Saxena A, Goyal V, Lejeune MA (2010) Mip reformulations of the probabilistic set covering problem. Mathematical programming 121(1):1--31

    work page 2010

  36. [36]

    Mathematical Programming 1--54

    Shen H, Jiang R (2022) Chance-constrained set covering with wasserstein ambiguity. Mathematical Programming 1--54

    work page 2022

  37. [37]

    Transportation Research Part A: General 22(2):97--108

    Smith BM, Wren A (1988) A bus crew scheduling system using a set covering formulation. Transportation Research Part A: General 22(2):97--108

    work page 1988

  38. [38]

    IEEE transactions on wireless communications 12(3):1098--1107

    Soltani NY, Kim SJ, Giannakis GB (2013) Chance-constrained optimization of ofdma cognitive radio uplinks. IEEE transactions on wireless communications 12(3):1098--1107

    work page 2013

  39. [39]

    INFORMS Journal on Computing 26(4):735--747

    Song Y, Luedtke JR, K \"u c \"u kyavuz S (2014) Chance-constrained binary packing problems. INFORMS Journal on Computing 26(4):735--747

    work page 2014

  40. [40]

    Stanley RP (2011) Enumerative Combinatorics: Volume 1 (USA: Cambridge University Press), 2nd edition, ISBN 1107602629

    work page 2011

  41. [41]

    Optimization Letters 13(5):1189--1206

    Sun O, Fan N (2019) The probabilistic and reliable connected power dominating set problems. Optimization Letters 13(5):1189--1206

    work page 2019

  42. [42]

    Tanner MW, Ntaimo L (2010) Iis branch-and-cut for joint chance-constrained programs with random technology matrices. Eur. J. Oper. Res 207(1):290--296

    work page 2010

  43. [43]

    Stochastic Optimization-Seeing the Optimal for the Uncertain 291--320

    Van Ackooij W, Zorgati R, Henrion R, M \"o ller A (2011) Chance constrained programming and its applications to energy management. Stochastic Optimization-Seeing the Optimal for the Uncertain 291--320

    work page 2011

  44. [44]

    European Journal of Operational Research 38(1):27--34

    Vasko FJ, Wolf FE, Stott Jr KL (1989) A set covering approach to metallurgical grade assignment. European Journal of Operational Research 38(1):27--34

    work page 1989

  45. [45]

    Operations research 55(5):966--975

    Wang J (2007) The -reliable median on a network with discrete probabilistic demand weights. Operations research 55(5):966--975

    work page 2007

  46. [46]

    INFORMS Journal on Computing 33(4):1661--1677

    Wang S, Li J, Mehrotra S (2021) Chance-constrained multiple bin packing problem with an application to operating room planning. INFORMS Journal on Computing 33(4):1661--1677

    work page 2021

  47. [47]

    INFORMS Journal on Optimization 4(2):125--147

    Wang S, Li J, Mehrotra S (2022) A solution approach to distributionally robust joint-chance-constrained assignment problems. INFORMS Journal on Optimization 4(2):125--147

    work page 2022

  48. [48]

    SIAM Journal on Optimization 29(1):690--718

    Wu HH, K \"u c \"u kyavuz S (2019) Probabilistic partial set covering with an oracle for chance constraints. SIAM Journal on Optimization 29(1):690--718

    work page 2019

  49. [49]

    Mathematics of Operations Research 41(2):715--731

    Yoda K, Pr \'e kopa A (2016) Convexity and solutions of stochastic multidimensional 0-1 knapsack problems with probabilistic constraints. Mathematics of Operations Research 41(2):715--731

    work page 2016

  50. [50]

    INFORMS Journal on Computing 32(3):547--564

    Zhang Z, Denton BT, Xie X (2020) Branch and price for chance-constrained bin packing. INFORMS Journal on Computing 32(3):547--564

    work page 2020

  51. [51]

    The collected works of Wassily Hoeffding 409--426

    Hoeffding W (1994) Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffding 409--426

    work page 1994