Page 72 - Fister jr., Iztok, Andrej Brodnik, Matjaž Krnc and Iztok Fister (eds.). StuCoSReC. Proceedings of the 2019 6th Student Computer Science Research Conference. Koper: University of Primorska Press, 2019
P. 72
the general model described above the processing of the points as possible. Distance between two vertices is defined
influencing can be differently modeled. The most known by the length of the shortest path between the two points,
models are the linear threshold model and the independent where edge lengths may be given or considered unit length.
cascade model, see [3], however for our purposes the so-called The covering distance or covering radius is also given to the
triggering model is the most appropriate. problem, which tells us in what distance the new facility can
cover the demand points. In real life, it may depend on the
2.1 Triggering Model ”size” of the facility, for example, in hospitals, its floor area
affects how many beds can be laid out and thus how many
In the triggering model, for each v ∈ V we independently patients can be accommodated, or on the maximal distance
choose a random Tv triggering set according to some distri- a service can be realized (ambulance, fast food delivery for
bution over subsets of its incoming neighbours. The Tv set example). Formally, we consider a simple graph G = (V, E)
is a subset of the neighbours of vertex v. At the beginning with the usual notation. The concept of coverage can be de-
of the process, the seed set S will be active. An inactive fined as follows. Our goal is either to maximize the covered
point becomes active at time instant t, if any element of the demand by a fixed number of companies or to cover the en-
selected triggering set Tv becomes active at time instance tire network minimizing the number of centers, or building
t − 1. Formally, for v ∈ V \S if exists v ∈ Tv such that costs. We will only discuss the first model, called maximal
v ∈ At−1, then v ∈ At. covering.
It can be seen that in this model, probability and threshold, 3.1 Maximal Covering
used in the threshold model and the independent cascade
model [3], are replaced by an influencer set that represents In this model, we aim to maximize the number of covered
the way information is spread. This also means that this demand points locating a fixed number of facilities at the
model is deterministic from the point where the triggering vertices of the network. The number of facilities to be lo-
sets are chosen. cated is s, and the covering radius R should also be known
for the problem. Formally, we can write the model as fol-
We have designed a mathematical model for this problem lows.
so that it can be solved with a Mixed Integer Programming
(MIP) solver. As a parameter, we need the maximum num- Parameters:
ber of steps of the influencing process, tmax. It is not known
beforehand but can be taken as the diameter of the graph, aij = 1, if point i can cover point j, i.e. d(i, j) ≤ R
which is a good upper bound for the run time. The rest of 0, otherwise
the data is the graph itself and the triggering set for each
vertex Tj, which includes a subset of the neighbours of j and Decision variables:
also j.
Decision variables: Xj = 1, if a company at point j is located,
0, otherwise
Zjt = 1, if point j is active at step t, 1, if point j is covered,
0, otherwise 0, otherwise
Yj =
max Zjtmax (1) Having these parameters and decision variables, the objec-
s.t. (2) tive function and constraints can be written in the following
j (3) way.
Zj0 = s ∀j ∈ V, 0 ≤ t < tmax
j max Yj (4)
s.t. (5)
Zit ≥ Zj,t+1 j (6)
i∈Tj Xj = s
Variables Zjtmax gives us the resulting influenced nodes af- j ∀j
ter tmax steps, thus the objective function is to maximize
their sum. Condition (2) sets the number of initial seeds to aij Xi ≥ Yj
s, while in (3) the influencing is defined. Namely, a vertex j
is influenced if its neighbours in Tj are influenced. By max- i
imizing the influence, the objective guarantees that Zj,t+1
will always take value 1 if the left-hand side of (3) allows it, The objective of the model described in (4) is to maximize
so no lower bounding condition on Zj,t+1 is necessary. coverage, which is the number of covered demand points.
Constraint (5) ensures that exactly s facilities are located.
3. COVERING PROBLEMS Each demand point j has a constraint that ensures that
demand point j is covered only if there is a facility located
Covering problems belong to the field of facility location. within the given distance, see (6). Knowing the coverage
We interpret it on a network and consider vertices as de- distance, we can determine the locations which could cover
mand points. Our goal is to place facilities or service units at the demand point j.
some vertices of the network that can cover as many demand
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 72
Koper, Slovenia, 10 October
influencing can be differently modeled. The most known by the length of the shortest path between the two points,
models are the linear threshold model and the independent where edge lengths may be given or considered unit length.
cascade model, see [3], however for our purposes the so-called The covering distance or covering radius is also given to the
triggering model is the most appropriate. problem, which tells us in what distance the new facility can
cover the demand points. In real life, it may depend on the
2.1 Triggering Model ”size” of the facility, for example, in hospitals, its floor area
affects how many beds can be laid out and thus how many
In the triggering model, for each v ∈ V we independently patients can be accommodated, or on the maximal distance
choose a random Tv triggering set according to some distri- a service can be realized (ambulance, fast food delivery for
bution over subsets of its incoming neighbours. The Tv set example). Formally, we consider a simple graph G = (V, E)
is a subset of the neighbours of vertex v. At the beginning with the usual notation. The concept of coverage can be de-
of the process, the seed set S will be active. An inactive fined as follows. Our goal is either to maximize the covered
point becomes active at time instant t, if any element of the demand by a fixed number of companies or to cover the en-
selected triggering set Tv becomes active at time instance tire network minimizing the number of centers, or building
t − 1. Formally, for v ∈ V \S if exists v ∈ Tv such that costs. We will only discuss the first model, called maximal
v ∈ At−1, then v ∈ At. covering.
It can be seen that in this model, probability and threshold, 3.1 Maximal Covering
used in the threshold model and the independent cascade
model [3], are replaced by an influencer set that represents In this model, we aim to maximize the number of covered
the way information is spread. This also means that this demand points locating a fixed number of facilities at the
model is deterministic from the point where the triggering vertices of the network. The number of facilities to be lo-
sets are chosen. cated is s, and the covering radius R should also be known
for the problem. Formally, we can write the model as fol-
We have designed a mathematical model for this problem lows.
so that it can be solved with a Mixed Integer Programming
(MIP) solver. As a parameter, we need the maximum num- Parameters:
ber of steps of the influencing process, tmax. It is not known
beforehand but can be taken as the diameter of the graph, aij = 1, if point i can cover point j, i.e. d(i, j) ≤ R
which is a good upper bound for the run time. The rest of 0, otherwise
the data is the graph itself and the triggering set for each
vertex Tj, which includes a subset of the neighbours of j and Decision variables:
also j.
Decision variables: Xj = 1, if a company at point j is located,
0, otherwise
Zjt = 1, if point j is active at step t, 1, if point j is covered,
0, otherwise 0, otherwise
Yj =
max Zjtmax (1) Having these parameters and decision variables, the objec-
s.t. (2) tive function and constraints can be written in the following
j (3) way.
Zj0 = s ∀j ∈ V, 0 ≤ t < tmax
j max Yj (4)
s.t. (5)
Zit ≥ Zj,t+1 j (6)
i∈Tj Xj = s
Variables Zjtmax gives us the resulting influenced nodes af- j ∀j
ter tmax steps, thus the objective function is to maximize
their sum. Condition (2) sets the number of initial seeds to aij Xi ≥ Yj
s, while in (3) the influencing is defined. Namely, a vertex j
is influenced if its neighbours in Tj are influenced. By max- i
imizing the influence, the objective guarantees that Zj,t+1
will always take value 1 if the left-hand side of (3) allows it, The objective of the model described in (4) is to maximize
so no lower bounding condition on Zj,t+1 is necessary. coverage, which is the number of covered demand points.
Constraint (5) ensures that exactly s facilities are located.
3. COVERING PROBLEMS Each demand point j has a constraint that ensures that
demand point j is covered only if there is a facility located
Covering problems belong to the field of facility location. within the given distance, see (6). Knowing the coverage
We interpret it on a network and consider vertices as de- distance, we can determine the locations which could cover
mand points. Our goal is to place facilities or service units at the demand point j.
some vertices of the network that can cover as many demand
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 72
Koper, Slovenia, 10 October
