Case Study: Cell Towers allocation with Probability of Exceedance and VaR functions
Case study background and problem formulations
Sources of Data  

PROBLEM 1: Control a fraction of uncovered houses using Probability function in constraint
Minimize linear (number of allocated Cell Towers)
subject to
Pr_pen <= Const1 (constraint on the fraction of uncovered houses)
——————————————————————–
Pr_pen = Probability of Exceedance
——————————————————————–
Minimize linear (number of allocated Cell Towers)
subject to
Pr_pen <= Const1 (constraint on the fraction of uncovered houses)
——————————————————————–
Pr_pen = Probability of Exceedance
——————————————————————–
Problem “problem_CELL_Towers_Pr”
# of Variables  # of Scenarios  Objective Value  Gap  Solving Time, PC 3.4GHz (sec)  
Dataset1  98  41  6.0  0.0  0.27  

Environments  
RunFile  Problem Statement  Data  Solution  
Matlab Toolbox  Data  
Matlab Subroutines  Matlab Code  Data 
Download other datasets in RunFile Environment.
Instructions for importing problems from RunFile to PSG MATLAB.
Problem Datasets  # of Variables  # of Scenarios  Objective Value  Gap  Solving Time (sec), PC 3.4GHz  

Dataset2  ProblemStatement  Data  Solution  98  41  13  0  0.24 
Dataset3  ProblemStatement  Data  Solution  89776  45152  4869  0  43.01 
Dataset4  ProblemStatement  Data  Solution  89776  45152  11320  786  7200.15 
PROBLEM 2: Control a fraction of uncovered houses based on VaR function in constraint
Minimize linear (number of allocated Cell Towers)
subject to
Var_risk <= Const2 (constraint on the fraction of uncovered houses)
——————————————————————–
Var_risk = ValueatRisk
——————————————————————–
Problem “problem_CELL_Towers_Var”
# of Variables  # of Scenarios  Objective Value  Gap  Solving Time, PC 3.4GHz (sec)  
Dataset1  98  41  6  0.0  0.24  

Environments  
RunFile  Problem Statement  Data  Solution  
Matlab Toolbox  Data  
Matlab Subroutines  Matlab Code  Data 
Download other datasets in RunFile Environment.
Instructions for importing problems from RunFile to PSG MATLAB.
Problem Datasets  # of Variables  # of Scenarios  Objective Value  Gap  Solving Time (sec), PC 3.4GHz  

Dataset2  ProblemStatement  Data  Solution  98  41  13  0  0.25 
Dataset3  ProblemStatement  Data  Solution  89776  45152  4869  0  38.95 
Dataset4  ProblemStatement  Data  Solution  89776  45152  11323  788  10007.44 
PROBLEM 3: Minimize a fraction of uncovered houses using Probability function in objective
Minimize Pr_pen (fraction of uncovered houses)
subject to
linear <= Const3 (constraint on the number of Cell Towers to be allocated)
——————————————————————–
Pr_pen = Probability of Exceedance
——————————————————————–
Problem “problem_min_PR_CELL_Towers”
# of Variables  # of Scenarios  Objective Value  Gap  Solving Time, PC 3.4GHz (sec)  
Dataset1  98  41  0.2439  0  0.25  

Environments  
RunFile  Problem Statement  Data  Solution  
Matlab Toolbox  Data  
Matlab Subroutines  Matlab Code  Data 
Download other datasets in RunFile Environment.
Instructions for importing problems from RunFile to PSG MATLAB.
Problem Datasets  # of Variables  # of Scenarios  Objective Value  Gap  Solving Time (sec), PC 3.4GHz  

Dataset2  ProblemStatement  Data  Solution  98  41  0.26829  0  0.26 
Dataset3  ProblemStatement  Data  Solution  89776  45152  0.2999867  0  93.34 
Dataset4  ProblemStatement  Data  Solution  89776  45152  0.2964  0.0386  24582.72 
CASE STUDY SUMMARY
This Case study demonstrates a scenario based optimization framework for solving Partial Set Covering problem and Maximal Covering Location problem. We use Probability of Exceedance (POE) and ValueatRisk (VaR) functions to bound and minimize some fraction of uncovered nodes. Although the suggested approach is quite general, it is demonstrated, in this case study, with the problem of “Allocation of Cell Towers to Service Houses”.
We solved a small problem (10×10) for covering 41 houses by 1 and 2 Cell Towers. Also, we generated and solved a big (300×300) problem with randomly distributed 45,152 houses.
We found that covering houses by 2 Cell Towers is a much more challenging combinatorial problem (time of solving increases dramatically) compared with covering by 1 Cell Tower.
This Case study demonstrates a scenario based optimization framework for solving Partial Set Covering problem and Maximal Covering Location problem. We use Probability of Exceedance (POE) and ValueatRisk (VaR) functions to bound and minimize some fraction of uncovered nodes. Although the suggested approach is quite general, it is demonstrated, in this case study, with the problem of “Allocation of Cell Towers to Service Houses”.
We solved a small problem (10×10) for covering 41 houses by 1 and 2 Cell Towers. Also, we generated and solved a big (300×300) problem with randomly distributed 45,152 houses.
We found that covering houses by 2 Cell Towers is a much more challenging combinatorial problem (time of solving increases dramatically) compared with covering by 1 Cell Tower.
References
• Toregas C., Swain R., ReVelle C. and Bergman L. (1971): The location of emergency service facilities. Operations Research, 19(6), 13631373.
• Moshkov M. Ju., Piliszczuk M. and Zielosko B. (2008): Partial Covers, Reducts and Decision Rules. Studies in Computational Intelligence, SpringerVerlag, V.145, 749.
• Church, R., ReVelle, C. S. (1974): The Maximal Covering Location Problem. Papers in Regional Science 32 (1), 101–118.
• Daskin, M. S. (1983): A Maximum Expected Covering Location Model: Formulation, Properties and Heuristic Solution. Transportation Science 17 (1), 4870.
• Toregas C., Swain R., ReVelle C. and Bergman L. (1971): The location of emergency service facilities. Operations Research, 19(6), 13631373.
• Moshkov M. Ju., Piliszczuk M. and Zielosko B. (2008): Partial Covers, Reducts and Decision Rules. Studies in Computational Intelligence, SpringerVerlag, V.145, 749.
• Church, R., ReVelle, C. S. (1974): The Maximal Covering Location Problem. Papers in Regional Science 32 (1), 101–118.
• Daskin, M. S. (1983): A Maximum Expected Covering Location Model: Formulation, Properties and Heuristic Solution. Transportation Science 17 (1), 4870.