Page 24 - 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. 24
ure 1: Graph of Italy with cities on the islands (left), graph of Germany (right)
2. THE P -MEDIAN PROBLEM Our aim is to minimize the sum of the distances between
the demand points and the closest facility, but we do not
The aim of solving a p-median problem is to locate exactly p have any direct constraint for that. That is because the
medians by minimizing the sum of the distances between the model minimizes the sum of dijyij, and so in this way the
demand points and the located facilities and also completing model automatically chooses the best solution, which is the
a few constraints mentioned below. In order to solve the minimal distance between a demand point and the assigned
problem we used the following model which is based on a facility.
non-oriented weighted n-vertex graph. We worked with the
graph as a set of vertices (V ) connected by weighted edges 3. METHODS
(E ⊆ {V, V }).
Our choice to get the computational results was AMPL,
min dij yij (1) which is A Mathematical Programming Language. First we
s.t. (2) implemented the model to solve the p-median problem. In
i,j∈V (3) order to obtain the optimal solution of this Mixed Integer
(4) Programming (MIP) problem we used a commercial solver
yij = 1 ∀i ∈ V called CPLEX.
j∈V Our goal was to inspect how the solution reacts to changes,
especially deleting edges. At first, we always ran the algo-
zi = p; rithm with no changes to inspect the original solution, than
we modified it with different amounts. We increased the
i∈V number of deleted edges always by 10%. After deleting 40%
of the edges we decided to stop, because we noticed that the
yij ≤ zj ∀i, j ∈ V ; graph fell apart. We also checked how the solution operates
when we want to locate 1, 2 or 3 medians with the different
To represent the distances between the vertices we used a number of deleted edges. In every variation of the number of
parameter dij, which is a squared matrix. The j-th column deleted edges and the number of located medians we made
of the i-th row represents the length of the shortest path 20 test runs.
between the i-th and j-th vertex.
In order to delete edges, first we made a mapping, so we
We also used two set of variables: yij and zi. The binary could work with the edges like an ordered set. Then we ran-
variable yij is to sign that the i-th demand point is sup- domly choose the right number of edges to delete from the
plied by the j-th facility and zi is a binary variable to sign graph. To implement this random choose, we used some of
if we locate a facility on vertex i. The aim of the model is the built-in functions of AMPL. Deleting the desired amount
to minimize the sum of the distances between the demand of edges was done uniformly. In a cycle we have generated a
points and the facilities. The optimal solution must com- random integer value k from 1 to the number of still exist-
plete three constraints: (2) gives the condition, that exactly ing edges and removed the kth edge, until we removed the
one facility has to be assigned to one vertex; the number of required number of edges.
located facilities must be p which is required by constraint
(3); and finally, that a demand point can only be assigned
to a facility, that is located, see (4).
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 24
Koper, Slovenia, 10 October
2. THE P -MEDIAN PROBLEM Our aim is to minimize the sum of the distances between
the demand points and the closest facility, but we do not
The aim of solving a p-median problem is to locate exactly p have any direct constraint for that. That is because the
medians by minimizing the sum of the distances between the model minimizes the sum of dijyij, and so in this way the
demand points and the located facilities and also completing model automatically chooses the best solution, which is the
a few constraints mentioned below. In order to solve the minimal distance between a demand point and the assigned
problem we used the following model which is based on a facility.
non-oriented weighted n-vertex graph. We worked with the
graph as a set of vertices (V ) connected by weighted edges 3. METHODS
(E ⊆ {V, V }).
Our choice to get the computational results was AMPL,
min dij yij (1) which is A Mathematical Programming Language. First we
s.t. (2) implemented the model to solve the p-median problem. In
i,j∈V (3) order to obtain the optimal solution of this Mixed Integer
(4) Programming (MIP) problem we used a commercial solver
yij = 1 ∀i ∈ V called CPLEX.
j∈V Our goal was to inspect how the solution reacts to changes,
especially deleting edges. At first, we always ran the algo-
zi = p; rithm with no changes to inspect the original solution, than
we modified it with different amounts. We increased the
i∈V number of deleted edges always by 10%. After deleting 40%
of the edges we decided to stop, because we noticed that the
yij ≤ zj ∀i, j ∈ V ; graph fell apart. We also checked how the solution operates
when we want to locate 1, 2 or 3 medians with the different
To represent the distances between the vertices we used a number of deleted edges. In every variation of the number of
parameter dij, which is a squared matrix. The j-th column deleted edges and the number of located medians we made
of the i-th row represents the length of the shortest path 20 test runs.
between the i-th and j-th vertex.
In order to delete edges, first we made a mapping, so we
We also used two set of variables: yij and zi. The binary could work with the edges like an ordered set. Then we ran-
variable yij is to sign that the i-th demand point is sup- domly choose the right number of edges to delete from the
plied by the j-th facility and zi is a binary variable to sign graph. To implement this random choose, we used some of
if we locate a facility on vertex i. The aim of the model is the built-in functions of AMPL. Deleting the desired amount
to minimize the sum of the distances between the demand of edges was done uniformly. In a cycle we have generated a
points and the facilities. The optimal solution must com- random integer value k from 1 to the number of still exist-
plete three constraints: (2) gives the condition, that exactly ing edges and removed the kth edge, until we removed the
one facility has to be assigned to one vertex; the number of required number of edges.
located facilities must be p which is required by constraint
(3); and finally, that a demand point can only be assigned
to a facility, that is located, see (4).
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 24
Koper, Slovenia, 10 October
