Probabilistic Covering Problems and Their Applications in Vaccination Allocation and Sensor Deployment
This presentation talks about probabilistic (chance-constrained) covering problems (PCP). Covering problems are computational problems that ask whether a certain combinatorial structure 'covers' another, or how large the structure has to be to do that. The PCPs are the covering problems with uncertain data and the probability of coverage is required to be at least a minimum value. We discuss two classes of probabilistic covering problems in this talk.
The first class problems consist of only continuous variables. We first give a MIP formulation using sample average approximation approach and show that solving this MIP is strongly NP-hard. Then we introduce and analyze a coefficient-strengthening scheme, adapt and analyze an existing cutting plane technique, and present a branching technique. We apply the proposed approaches to a portfolio optimization problem and a vaccination allocation problem. The vaccination allocation problem is to distribute a scarce vaccine among households in a community to prevent an epidemic from breaking out by restricting the post-vaccination reproductive number to be strictly less than one. Through computational experiments, we empirically verify that these techniques are significantly effective in improving solution times over the CPLEX MIP solver.
The second class of PCPs are probabilistic set k-cover problems (PSKP), in which decision variables are restricted to be binary variables and coefficients to be Bernoulli random numbers. We introduce the ambiguous k-cover set, which is a “distributionally-robust” model for PSKP, and build deterministic reformulations and approximations. We apply the models to a probabilistic sensor deployment problem, in which we deploy a set of sensors to n possible locations such that each target is monitored by at least three sensors with a prescribed probability. Computational experiments are conducted to examine the quality of the deterministic reformulations in terms of cost effectiveness and solution robustness. Finally, we demonstrate the modeling capability of the proposed models by applying them to maximal location problems and probabilistic shortest path problems.
Feng Qiu is a PhD candidate in the H. Milton Stewart School of Industrial & Systems Engineering at the Georgia Institute of Technology, majoring in optimization. His research interests are in optimization and its applications, specifically stochastic and integer programming. Feng Qiu worked as an operations research analyst in Shanghai Firsttech, an ILOG solution center, before he joined Georgia Tech.