Optimal Demand Fulfillment: An Industry Approach

Published in

Towards Data Science

8 min readFeb 6, 2023

In the field of telecommunications, data science has numerous applications ranging from site planning to budget and managerial accounting decisions, customer lifecycle management, and marketing. In this post, we will discuss one such use case, network site planning. We will begin with two scenarios so that you can understand them.

Scenario 1: Recently, telecom decision-makers discovered massive overheads as a result of unplanned site planning. The network sites, of course, have a variety of costs associated with them, including fixed construction costs, variable costs, and other variable overheads. Managers at the company have identified various types of variances that are causing inefficiencies. Now the managers want to replan everything and turn off unnecessary site locations while ensuring that the remaining site locations completely cover all demand/regions. This is one such use case. The goal here is to reduce the total number of cell sites while still covering all regions.

Scenario 2: Another use case is when a manager wants to limit the number of site locations that can be used to cover the maximum number of regions may be due to a lack of financials or a budget constraint in a particular quarter or year. So, in this case, we’d like to maximize our coverage regions while selecting no more than p cellsites (upper cap). In this scenario, it is possible that we are not able to cover all regions.

General Overview

Let’s take a look at how we can use optimization techniques to easily solve these two use cases. Demand does not always refer to the number of subscribers or regions, but it can be viewed holistically, taking into account a number of factors that are beyond the scope of this article.

Scenario 1

Let us begin with the first use case, which is about allocating as few selected sites as possible in order to meet all demand. We will only use a simple example to demonstrate the concepts; however, in the real world, you may have different types of datasets with 1000s of cell sites, and each cell site’s neighborhood or coverage can be checked with some distance threshold.

Let us begin with an example. We have four cell sites, and the area is divided into four regions. A large area is normally divided into different grids on a map. We won’t go into that much detail. For example, Cell Site #1 can cover Regions 1 and 2, while Cell Site #2 can cover Region 3. Cell Site #2 can cover Regions 1, 2, and 3. Cell Site 3 can cover regions 3 and 4. Cell Site 4 can cover regions 2 and 4. The diagram below illustrates this.

Graph 1: Regions connectivity with network towers (Figure by Author)

In this case, we want to find the fewest number of cell sites that can meet all of the requirements. For example, we may not need cell site #4 because demand is already met by cell sites #1, #2, and #3. Therefore, we may want to eliminate cell site #4. This is what we want to accomplish: find the optimal combination of our cell sites to meet all demand while eliminating unnecessary cell sites.

Equation

Let us represent Location/CellSite with J and Demand nodes/Region with I. Let us also define aij which will be equal to 1 if demand node i is getting covered by location node j. aij can be defined using some distance threshold.

Table 1: Sample Problem Formulation and variable notations for Scenario 1 (Figure by Author)

Each cell site location is represented by a binary variable xj indicating whether it is selected or not. xj=1 if the cell site is selected else it will be equals to 0.

The objective function is to optimize by minimizing the sum of selected cell site.

Equation 1: Objective Function — Minimizing sum of selected cell sites for Scenario 1 (Figure by Author)

The constraints are to ensure that the region is covered by at least one selected cell site. Therefore, we want every demand node i (regions in our case) to be served by at least one location j (cell site in our case).

Equation 2: Constraints— each region to be covered by atleast 1 cell site/location for Scenario 1 (Figure by Author)

So, for each Region i, we look at all cell sites, and see whether this cell site covers region i or not. Each region should be at least covered by one cell site. Note that in this particular model, region can be served by more than one cell site.

By solving this optimization problem, telecom companies can determine the optimal cell site locations while minimizing the number of cell sites required to cover the entire country/city/region.

Code

from pyomo.environ import *

model = ConcreteModel()

# Define parameters regions and cell sites
model.I = Set(initialize=[1,2,3,4]) # regions/demands
model.J = Set(initialize=[1,2,3,4]) # cell sites
model.a = Param(model.I, model.J, initialize={(1,1):1, (1,2):1, (1,3):0, (1,4):0, (2,1):1,(2,2):1,(2,3):1, (2,4):0, (3,1):0,(3,2):0,(3,3):1,(3,4):1,(4,1):0,(4,2):1,(4,3):0, (4,4):1})

# Define variables
model.x = Var(model.J, within=Binary)

# Define objective function
def objective(model):
    return sum(model.x[j] for j in model.J)

model.obj = Objective(rule=objective, sense=minimize)

# Define constraints (sumproduct), for each Region i, we look at all cell sites, and see whether this cell site covers region i or not. sum must be greator than equal to 1
def demand_rule(model, i):
    return sum(model.a[i,j]*model.x[j] for j in model.J) >= 1

model.demand_constraint = Constraint(model.I, rule=demand_rule)

# Solve the model
solver = SolverFactory('glpk')
results = solver.solve(model)

# Print the solution
print("Optimal solution:")
for j in model.J:
    if model.x[j].value == 1:
        print(f"Location {j} is open")
print(f"Number of open locations: {model.obj()}")

Figure 1: Result of Scenario 1 (Figure by Author)

As we can see, we can cover all demand points/regions with only two cell sites, and you can validate the results yourself using the graph above.

Scenario 2

Now we come to our second use case, which is about putting an upper cap on site locations that can be used to meet maximum demand. Given the limited number of cell sites available, we would like to maximize coverage. For example, a company may decide to set a upper cap of maximum two cell sites and turn off other cell sites to save finances. The question now is how many region we can cover with only two cell sites. Of course, different combinations are possible; for example, if we only use cell sites 1 and 2 and turn off cell sites 3 and 4, we would effectively lose coverage in region 3. Perhaps there is some combination of two cell sites that can cover the entire region, which we will solve using our optimization equations. It could be possible that there exist more than 1 feasible solution.

Equation

Table 2: Sample Problem Formulation and variable notations for Scenario 2(Figure by Author)

In this case, we would like to essentially maximize our coverage, we define the notion of coverage with y variable. yi in this case represents whether our region is going to be selected or not. If it is selected then yi will be 1 else it will be 0. We essentially want to maximize this sum that is saying that we want every region to be covered. This can be represented by the following equation.

Equation 3: Objective Function — Maximizing coverage/regions for Scenario 1 (Figure by Author)

However, we have constraints so it may not be possible to cover all the regions. Let us start with our first constraint that is number of cell sites covering the region must be greater than equals to yi. So if for example a particular region is selected yi=1 then we essentially want number of cell sites covering that region to be greator than equals to yi.

Equation 4: Constraints — each selected region(yi) needs to be covered by atleast 1 cell site/location for Scenario 2(Figure by Author)

The equation is the same as in the first part, except we replace 1 with yi. So, for each region I we look at whether it is covered by cell site and add it all up to make sure it is greater than equals to yi.

Aside from that, the most important constraint is the company’s decision to limit us to a maximum of two cell sites. We essentially want the total number of cellsites to be less than equals to p. (2 in our case).

Equation 5: Constraints — Upper cap of p cellsites for Scenario 2(Figure by Author)

Let us now combine all the equations and write it again all together.

Equation 6: Complete equation combining everything from above for scenario 2(Figure by Author)

Code

from pyomo.environ import *

model = ConcreteModel()
# Define parameters regions and cell sites
model.I = Set(initialize=[1,2,3,4]) # regions/demands
model.J = Set(initialize=[1,2,3,4]) # cell sites
model.a = Param(model.I, model.J, initialize={(1,1):1, (1,2):1, (1,3):0, (1,4):0, (2,1):1,(2,2):1,(2,3):1, (2,4):0, (3,1):0,(3,2):0,(3,3):1,(3,4):1,(4,1):0,(4,2):1,(4,3):0, (4,4):1})


model.p = Param(initialize=1)
model.x = Var(model.J, within=Binary)
model.y = Var(model.I, within=Binary)

def objective(model):
    return sum(model.y[i] for i in model.I)

model.obj = Objective(rule=objective, sense=maximize)

##constraint
def coverage_rule(model, i):
    return sum(model.a[i,j]*model.x[j] for j in model.J) >= model.y[i]

model.coverage_constraint = Constraint(model.I, rule=coverage_rule)

def cellsitelocation_rule(model):
    return sum(model.x[j] for j in model.J) <= model.p

model.cellsite_constraint = Constraint(rule=cellsitelocation_rule)

opt = SolverFactory("glpk")
results = opt.solve(model)

print("Optimal solution:")
for j in model.J:
    if model.x[j].value == 1:
        print(f"Cellsite {j} is on")

print("Optimal solution:")
for i in model.I:
    if model.y[i].value == 1:
        print(f"Region {i} is covered")
print(f"Number of regions covered: {model.obj()}")

Figure 2: Result of Scenario 2 (Figure by Author)

We can still cover all the demand/regions with limited number of cellsites. You can now experiment with p=1 to see which regions may be missed. It is important to note that while using an upper cap, you may miss out on some regions while still maximizing coverage.

Conclusion

These are the very simple problems that we explored in this post. However, this can be really powerful tool when it comes to problem like this. We can have a more advanced type of equation with a weighted part as well, and it is now up to you to think about it further. There are many other variants for these types of problems, such as minimizing shipping costs from location to demand point. There are numerous interesting problems of this type.