Page 27 - 33-3
P. 27
facility nodes and edges. More precisely, adding a new edge is equivalent to changing
one edge’s capacity from zero to some positive number on the previous solved graph.
The difference between previous maximum flow and the new one will only be
determined by those vertices affected by this insertion. Therefore, whenever we add a
new facility into the construction plan, instead of creating a whole new graph, we add
vertices and edges to the previous solved graph and then continue solving the maximum
flow problem.
Kumar and Gupta (2003) propose an incremental algorithm for the maximum flow
problem of inserting an edge in the graph. The time complexity of the algorithm is
, where is the number of affected vertices and is the number of
�
edges. When an edge is inserted into the graph, there may exist new augmenting path
from source to sink through the new edge. The affected vertices are those that lie on at
least one augmenting path. That is, when we add a new facility into the construction
plan, it is equivalent to insert edges, i.e., , for all , to the graph and
each insertion affects nodes. Therefore, the total time complexity
of adding a new facility to the graph is ��
4.2 Greedy Selection Algorithm with Maximum Flow Estimation
NTU Management Review Vol. 33 No. 3 Dec. 2023
4.2 Greedy Selection Algorithm with Maximum Flow Estimation
O �� � � ,
(GSAMFE)
�
�
�
�
(GSAMFE)
4.2 Greedy Selection Algorithm with Maximum Flow Estimation
and the total time complexity is a construction plan , we have to calculate the
In our algorithm, given
and the total time complexity is
(GSAMFE)
In our algorithm,
� given a construction plan , we have to calculate the
corresponding number of served customers. However, considering the large number of
�� − � .
�
�
�
�
�
In our algorithm, given a construction plan , we have to calculate the
corresponding number of served customers. However, considering the large number of
customers and facilities, it requires long computational time even using the incremental
���
customers and facilities, it requires long computational time even using the incremental
corresponding number of served customers. However, considering the large number of
maximum flow idea may still be too time-consuming. Therefore, we adopt the flow
The implementation with incremental maximum flow indeed reduces the time complexity
The implementation with incremental maximum flow indeed reduces the time
of GSAMF.
customers and facilities, it requires long computational time even using the incremental
maximum flow idea may still be too time-consuming. Therefore, we adopt the flow
estimation algorithm proposed in Kang et al. (2023) to evaluate the objective value and
complexity of GSAMF.
estimation algorithm proposed in Kang et al. (2023) to evaluate the objective value and
maximum flow idea may still be too time-consuming. Therefore, we adopt the flow
extend it to the scenario with time dependency.
4.2 Greedy Selection Algorithm with Maximum Flow Estimation (GSAMFE)
In our algorithm, given a construction plan y, we have to calculate the corresponding
extend it to the scenario with time dependency.
estimation algorithm proposed in Kang et al. (2023) to evaluate the objective value and
>0 for facility at activity session
Let be the set of customers that
number of served customers. However, considering the large number of customers and
��
���
26
extend it to the scenario with time dependency.
facilities, it requires long computational time even using the incremental maximum flow
>0 for facility at activity session
Let be the set of customers that
and �� �� be the set of facilities that ��� ��� >0 for customer at activity session .
idea may still be too time-consuming. Therefore, we adopt the flow estimation algorithm
Let be the set of customers that for customer at activity session .
Given any
��construction plan , we define two variables ( and , where the
and be the set of facilities that ��� >0 ��� >0 for facility at activity session
proposed in Kang et al. (2023) to evaluate the objective value and extend it to the scenario
��
�
��
Given any construction ��� >0 for customer at activity session .
with time dependency. of facilities that two variables ( and , where the
and be the set plan , we define
former
��is called the potential demand of customer , and the latter is called the potential
��
�
Let I be the set of customers that p > 0 for facility j at activity session t and I be the
jt
ijt
jt
Given any construction plan , we define two variables ( and , where the
former is called the potential demand of customer , and the latter is called the potential
supply of facility of scale level . More precisely, we define
set of facilities that p > 0 for customer i at activity session t. Given any construction plan
�
��
ijt
y, we define two variables α (y) and β , where the former is called the potential demand of
supply of facility of scale level . More precisely, we define
former is called the potential demand of customer , and the latter is called the potential
i
jk
customer i, and the latter is called the potential supply of facility j of scale level k. More
( � ,� � � �
supply of facility of scale level . More precisely, we define
�
�� ��
�
precisely, we define
���
���
( � ,� � � �
��� ��
�� ��
�
�
and ( � ,� � � �
���
���
��� ��
� � �� ��
and ��� ��� �� ���
and
and �� � �� , � .
��
�
���
��� ��
�� � �� , � .
�
��
The estimated objective value ( of the construction plan is the minimum of the
���
��� ��
�
�� � �� , � .
�
��
The estimated objective value z'(y) of the construction plan y is the minimum of the
The estimated objective value ( of the construction plan is the minimum of the
potential demand and supply, i.e.,
�
���
��� ��
potential demand and supply, i.e.,
The estimated objective value ( of the construction plan is the minimum of the
potential demand and supply, i.e., �
( �� ( ,� � �.
�
potential demand and supply, i.e., � ��
���
���
���
( �� ( ,� � �.
�
�
��
��� ��� ���
( �� ( ,� � �.
�
19 � ��
��� ��� ���
27
27
27
