Advanced
SOME ANALYSES ON A PROPOSED METHOD OF THE OPTIMAL NETWORK SELECTION PROBLEM
SOME ANALYSES ON A PROPOSED METHOD OF THE OPTIMAL NETWORK SELECTION PROBLEM
Journal of Applied Mathematics & Informatics. 2014. Sep, 32(3_4): 539-546
Copyright © 2014, Korean Society of Computational and Applied Mathematics
  • Received : October 18, 2013
  • Accepted : December 17, 2013
  • Published : September 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
JONG SEUL LIM

Abstract
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.
Keywords
1. Introduction
We consider the situation that 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 pij , and that of assigning at least one item to the jth location is cj , 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
PPT Slide
Lager Image
PPT Slide
Lager Image
Then, the optimum location selection problem can be defined as
PPT Slide
Lager Image
where C is the total cost incurred from being assigned, xij , yj = 0, 1, for all i = 1, ..., m , and j = 1, ..., n .
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 I = 1, 2, ..., m , the set of the m given items; J = 1, 2, ..., n , the set of the n given locations;
PPT Slide
Lager Image
Initially, define J (1) = J 1 , where J 1 minimizes the following with respect to all j J ,
PPT Slide
Lager Image
For k = 2, 3, ..., n , and j J , define
PPT Slide
Lager Image
Then find jk J ( k − 1) such that
PPT Slide
Lager Image
and define J ( k ) = J ( k − 1) Ujk , where Ujk 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
PPT Slide
Lager Image
PPT Slide
Lager Image
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 pij is minimized among all the locations that are selected, and that the corresponding
PPT Slide
Lager Image
can be further reduced to offset the additional cost cj .
3. A Feasible Solution And The Variance
A feasible solution to the problem may be represented by a vector s = ( xij , yj , 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
PPT Slide
Lager Image
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 Jk of k elements out of set {1, 2, ..., n }, define
PPT Slide
Lager Image
PPT Slide
Lager Image
In other words, S ( k ) represents all the possible ways of procuring the items from exactly k sources, and S ( Jk ), from k given sources. The numbers of feasible solutions in S , S ( k ), and S ( Jk ) are respectively nm , Nk , and A ( k,m ), which are given by [4] as
PPT Slide
Lager Image
From (3) and (10), for any solution s in S , denote the corresponding total cost by
PPT Slide
Lager Image
The mean is given as
PPT Slide
Lager Image
Then we can find
PPT Slide
Lager Image
The first summation in (14) can be broken down as follows:
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
Then
PPT Slide
Lager Image
For given i, j, and u in (17), the number of solutions s in S ( Jk ) for which xij ( s ) xuj ( s ) ≠ 0 is:
PPT Slide
Lager Image
Therefore
PPT Slide
Lager Image
PPT Slide
Lager Image
For given i u and j v , the number of solutions s in S ( Jk ) is:
PPT Slide
Lager Image
From (21) and (22), we see that
PPT Slide
Lager Image
Now
PPT Slide
Lager Image
PPT Slide
Lager Image
Based on (14), (19) through (25), the first summation can be written as
PPT Slide
Lager Image
Then we can obtain the variance
PPT Slide
Lager Image
as
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 ρ2 in (7) is non-positive, then iterations terminate. Otherwise for k = 3, 4, ..., n , every i I , and j J ( k − 1), define
PPT Slide
Lager Image
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
PPT Slide
Lager Image
Find jk such that
PPT Slide
Lager Image
Then define
PPT Slide
Lager Image
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, yj = 1 for all j J , and for every i I , xij = 1, if pij 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.
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 pij ’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.
BIO
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
References
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