SOME ANALYSES ON A PROPOSED METHOD OF THE OPTIMAL NETWORK SELECTION PROBLEM

Journal of Applied Mathematics & Informatics.
2014.
Sep,
32(3_4):
539-546

- Received : October 18, 2013
- Accepted : December 17, 2013
- Published : September 28, 2014

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

This paper introduces the approximation and a proposed method to deal the optimum location network selection problem such that the total cost is minimized. For the proposed method, we derived a feasible solution and the variance. To compare the performances of the approximation and the proposed method, computer simulation is also implemented. The result showed the solutions being optimum with 74% for the proposed method and 57% for the approximation. When the solutions is not optimum, maxi-mum and average deviations are below 4% and 2% respectively. The results indicate a slightly better performance of the proposed method in a certain case.
AMS Mathematics Subject Classification : 68M20.
m
given items are to be assigned to
n
given locations, such that every item must be assigned to one and only one location, but more than one item may be assigned to the same location.
The cost of assigning the ith item to the jth location is
p_{ij}
, and that of assigning at least one item to the jth location is
c_{j}
,
i
= 1, 2, ...,
m
, and
j
= 1, 2, ...,
n
.
To get the optimum solutions of this type of the problem, traditionally the approximation
[1]
which is reasonably efficient has been being applied.
In the first assigns all the items to the same locations, selects the one which minimizes the total cost and then proceeds recursively, selecting one additional location at a time. For example, suppose that
k
<
n
locations is tested to see whether further reduction is possible of the value of the objective function (1), when it is also selected and the m items are assigned accordingly.
If these are such locations, then the procedure selects the one for which the reduction is the largest. Iteration terminates when no further reduction is possible. At each stage of iteration, it considers all possible ways of adding the unselected location to those already selected, and of deleting the latter ones, and then course of action which reduces the most the value of the objective function. Define
Then, the optimum location selection problem can be defined as
where
C
is the total cost incurred from being assigned,
x_{ij}
,
y_{j}
= 0, 1, for all
i
= 1, ...,
m
, and
j
= 1, ...,
n
.
I
= 1, 2, ...,
m
, the set of the
m
given items;
J
= 1, 2, ...,
n
, the set of the
n
given locations;
Initially, define
J
(1) =
J
_{1}
, where
J
_{1}
minimizes the following with respect to all
j
∈
J
,
For
k
= 2, 3, ...,
n
, and
j
∈
J
, define
Then find
j_{k}
∉
J
(
k
− 1) such that
and define
J
(
k
) =
J
(
k
− 1)
Uj_{k}
, where
U_{jk}
denotes the union of sets. The iteration procedure terminates either as soon as
k
= 1, 2, ...,
n
is found for which
ρ_{k}
≥ 0, or
ρ_{k}
> 0, for all
k
= 1, 2, ...,
n
. In the first case, the optimum solution is
In the second case, the optimum solution may be obtained from (9) by setting
k
=
n
+ 1. From (6), (7), and (9), we see that at the end of each iteration, every item
i
is assigned to the location for which
p_{ij}
is minimized among all the locations that are selected, and that the corresponding
can be further reduced to offset the additional cost
c_{j}
.
s
= (
x_{ij}
,
y_{j}
,
i
= 1, ...,
m
, and
j
= 1, ...,
n
). However, those for which (2) does not hold need not be considered. Thus we may define the set of all feasible solutions as
which satisfy (1) and (2). The problem is similar to those of optimum location selections (
[1]
,
[2]
,
[5]
). For any
k
= 1, ...,
n
, and any subset
J_{k}
of
k
elements out of set {1, 2, ...,
n
}, define
In other words,
S
(
k
) represents all the possible ways of procuring the items from exactly
k
sources, and
S
(
J_{k}
), from
k
given sources. The numbers of feasible solutions in
S
,
S
(
k
), and
S
(
J_{k}
) are respectively
n^{m}
,
N_{k}
, and
A
(
k,m
), which are given by
[4]
as
From (3) and (10), for any solution
s
in
S
, denote the corresponding total cost by
The mean is given as
Then we can find
The first summation in (14) can be broken down as follows:
Then
For given
i, j,
and
u
in (17), the number of solutions
s
in
S
(
J_{k}
) for which
x_{ij}
(
s
)
x_{uj}
(
s
) ≠ 0 is:
Therefore
For given
i
≠
u
and
j
≠
v
, the number of solutions s in
S
(
J_{k}
) is:
From (21) and (22), we see that
Now
Based on (14), (19) through (25), the first summation can be written as
Then we can obtain the variance
as
ρ_{2}
in (7) is non-positive, then iterations terminate. Otherwise for
k
= 3, 4, ...,
n
, every
i
∈
I
, and
j
∈
J
(
k
− 1), define
In other words, if location
j
is to be deleted, those items which are assigned to it at the (
k
− 1)
th
iteration must be reassigned to the next possible location which will be retained. Let
Find
j_{k}
such that
Then define
The iteration procedure terminate either as soon as a
k
= 3, 4,..., is found for which
ρ_{k}
≤ 0, or
ρ_{k}
> 0 for
J
(
k
) =
J
. In the first case, the optimum solution is the same as (9). In the second case,
y_{j}
= 1 for all
j
∈
J
, and for every
i
∈
I
,
x_{ij}
= 1, if
p_{ij}
is minimized with respect to all the locations in
J
.
Using the above derivations for the proposed method, the optimum solution of the related problem can be found by direct enumeration. One of the optimum solution is the minimum cost obtained.
Due to the complexity of the problem, iterations by computer simulation are implemented. These iterations produce the minimum costs from the approximation in the section 2 and those from the proposed method in the section 4. With the minimum costs obtained, we can compare and judge performance of the methods.
p_{ij}
’s were drawn from a uniform distributions in the (0,150) interval and a lower bound fixed at 20 and and an upper bound ranging from 30 to 100. Both the proposed method and the approximation are applied, and the optimum solutions were found by direct search. To 50 of those problems, the proposed method is also applied where the initial solutions are based on all locations. The results of the experiments are optimum 74% from the proposed method, while 57% from the approximation. Also the proposed method was tested on 50 problems using two different types of initial solutions. Single location and all possible locations. The results indicate a slightly better performance of the proposed method when the initial solutions are based on consideration of all locations. However, the tests were limited in scope and no general rules can be from those results.
Jong Seul Lim received the BS degree from Seoul National University and the Ph.D degree in communications and operations engineering from Polytechnic University, New York, in 1988. He worked with AT&T Bell Laboratories and developed the computer network and cellular communication systems. After then, he joined SK Telecom Corp. Since 1993, he has worked with Sunmoon University, Korea as a professor.
Information Communication Engineering Department, Sunmoon University, Asan, Chung-nam, Korea.
e-mail: jslsky7@hotmail.com

1. Introduction

We consider the situation that
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

2. The Approximation

In order to see the difference between the approximation and the proposed method, we describe the former given in
[1]
with minor modifications. Let
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

3. A Feasible Solution And The Variance

A feasible solution to the problem may be represented by a vector
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

4. The Proposed Method

With the derivations in the previous sections and using the feasible solution and the variance, the iterations are implemented. At the first and second iterations, the procedure is the same as the approximation derived in the section 2. If
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

5. Conclusions

We showed the derivation of a feasible solution and the variance of the cost function. Also we tested the performance of the proposed method derived in this paper by the simulation for 100 problems with a different random number generator. The
BIO

Cornuejols
,
Gerard
,
Fisher
,
Marshall L.
(1997)
Location of Bank Accounts of Optimize Float: An Analytic Study of Exact and Approximate Algorithms
Manage Science
23
(8)
789 -
810

Cramer
,
Harold
1999
Mathematical Methods of Statistics
Princeton University Press
Princeton, NJ

Ryu D.
,
Kim H.
(2006)
Convergence of Linear Processes with The Negatively Dependent random Variables
J. Appl. Math. & Informatics
20
(1-2)
603 -
610

Feller
,
William
1991
An Introduction to Probability Theory and Its Applications, Vol. I
Third Edition
John Wiley and Sons, Inc.
New York, NY

Johannes J.
,
Schenk R.
(2012)
Adaptive Estimation of Linear Functionals in Functional Linear Models
Mathematical Methods of Statistics
21
(3)
189 -
214
** DOI : 10.3103/S1066530712030027**

Kuehn
,
Alfred A.
,
Hamburger
,
Michael J.
(1993)
A Heuristic Program for Locating Ware-house
Management Science
9
(4)
643 -
666

Citing 'SOME ANALYSES ON A PROPOSED METHOD OF THE OPTIMAL NETWORK SELECTION PROBLEM
'

@article{ E1MCA9_2014_v32n3_4_539}
,title={SOME ANALYSES ON A PROPOSED METHOD OF THE OPTIMAL NETWORK SELECTION PROBLEM}
,volume={3_4}
, url={http://dx.doi.org/10.14317/jami.2014.539}, DOI={10.14317/jami.2014.539}
, number= {3_4}
, journal={Journal of Applied Mathematics & Informatics}
, publisher={Korean Society of Computational and Applied Mathematics}
, author={LIM, JONG SEUL}
, year={2014}
, month={Sep}