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

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”

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”

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”

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.