Case Study: Cell Towers allocation with Probability of Exceedance and VaR functions

Back to main page

Case study background and problem formulations

Instructions for optimization with PSG Run-File, PSG MATLAB Toolbox and PSG MATLAB Subroutines.

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
——————————————————————–

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
Run-File Problem Statement Data Solution
Matlab Toolbox Data
Matlab Subroutines Matlab Code Data

Download other datasets in Run-File Environment.
Instructions for importing problems from Run-File 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 = Value-at-Risk
——————————————————————–

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
Run-File Problem Statement Data Solution
Matlab Toolbox Data
Matlab Subroutines Matlab Code Data

Download other datasets in Run-File Environment.
Instructions for importing problems from Run-File 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
Run-File Problem Statement Data Solution
Matlab Toolbox Data
Matlab Subroutines Matlab Code Data

Download other datasets in Run-File Environment.
Instructions for importing problems from Run-File 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 Value-at-Risk (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), 1363-1373.
• Moshkov M. Ju., Piliszczuk M. and Zielosko B. (2008): Partial Covers, Reducts and Decision Rules. Studies in Computational Intelligence, Springer-Verlag, V.145, 7-49.
• 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), 48-70.