Genetic Local Search for the Servers Load Balancing Problem

Abstract

In this work we consider the servers load balancing problem (SLBP) formulated as a mixed integer linear programming problem. As known, this problem is NP-hard in strong sense. We analyze the approximability of the problem and prove that SLBP is Log-APX-hard under PTAS-reducibility and cannot be NPO-complete unless P=NP. To solve the problem we develop an approximate method using the idea of genetic local search. Computational results are discussed.

Keywords

• servers load balancing
• mixed integer linear programming
• approximability
• genetic local search

Introduction

Copyright ⃝c by the paper's authors. Copying permitted for private and academic purposes.

It was proven in [ 1 ] that servers load balancing problem is NP-hard in strong sense. An approximation algorithm with a posteriori performance guarantee for solving this problem based on the problem representation as mixed integer linear programming problem was also proposed in this paper. Integer variables were substituted with continuous ones and the optimal solution of the corresponding linear programming problem was used to obtain an approximate solution and its error estimations. More precisely, a linear programming allows to x a part of disks on servers and thus to reduce the dimension of the problem and to solve the obtained subproblem exactly with the branchand-bound method (using CPLEX solver). This approach allows us to nd quickly an optimal solution on the instances with zero overload and gives rather good results in case of big overload of servers. For small overload a linear programming approach gives almost no positive integer components; thus, the dimension of the problem is not reduced, and hence the algorithm does not work.

Another approach based on the local search principles was proposed in [ 2 ]. Together with the essential neighborhoods of small size (switch disk to another server or swap disk with another disk) authors considered a new original neighborhood of exponential size. One disk was chosen on each server. After that, selected disks were redistributed between the servers. Each server got one disk, while the total overload of servers was minimized. The solution of the assignment problem gives the best redistribution of disks. Authors studied different ways of choosing disks for redistribution and efficiency of the local search with such neighborhood.

In the second chapter we formulate the servers load balancing problem as a mixed integer linear programming problem. We prove some results on approximation guarantee in the third chapter. We propose a new approximate method which is based on the idea of genetic local search in the fourth chapter . Computational results are discussed in the fth chapter. 2

Mathematical model

We use the following notation: S is the set of servers, D is the set of disks; T is the planning period; R is the set of load parameters (CPU, RAM, : : :); cdrt is the load of the disk d at the moment t by the parameter r; csr is the threshold load of the server s by the parameter r; x0ds is the initial distribution of disks among servers; bsdr(bsedr) is w the additional costs to move the disk d to (from) the server s for the parameter r, and Bswr(Bser) is the maximum allowed additional costs for the parameter r to move disks to (from) the server s.

Variables of the problem are: xds = 1 if the disk d is moved to the server s, xds = 0 otherwise; ystr is the overload at the server s at the moment t by the parameter r.

In these terms we can write the servers load balancing problem (SLBP) as a mixed integer linear programming problem [ 1, 2 ]: subject to min ∑ ∑

∑ ystr s2S t2T r2R ystr ∑ cdrtxds s 2 S; t 2 T;

r 2 R; s 2 S; ystr

The objective function de nes the total overload of servers during the planning period. The rst set of inequalities de nes the overload for each server at each moment of time for each parameter. The second set of equalities ensures that each disk will be put exactly at one server. The third and fourth sets of inequalities bound the additional cost for each server and each parameter when ejecting and inserting disks.

Formulating SLBP as an integer linear programming gives us a possibility to solve it using commercial software such as IBM ILOG CPLEX, GUROBI, AMPL, etc. Unfortunately, because of huge integrality gap, transition to continuous variable xds does not give us a possibility to nd an exact solution even for instances of average size. For example, for jSj = 20; jDj = 200; jT j = 150; jRj = 2; calculations can take more than one day without any guarantee to nd an exact solution. It can be partly explained by the fact that the problem is NP-hard in strong sense even for jT j = jRj = 1 and for zero additional costs [ 1, 2 ]. 3

Approximation complexity

In this chapter we describe the place of SLBP in approximation hierarchy [ 3 ]. The rst level of approximation hierarchy has the following structure:

P O

F P T AS

P T AS

AP X

Log

AP X P oly

AP X

Exp

AP X

N P O: Each class consists of optimization problems from the class NPO and describes certain quality of approximation, i.e. the rst level is used to describe properties of the problems for which the corresponding decision version belongs to the class NP. The class PO consists of the problems for which there exists an exact polynomial algorithm. The class FPTAS consists of the problems for which there exists fully polynomial approximate scheme and the class PTAS is formed by the problems for which there exists polynomial approximate scheme. Classes APX, Log-APX, Poly-APX and Exp-APX consist of the problems for which there exists polynomial r-approximate algorithm, where r is a constant, logarithmic, polynomial, and exponential estimates for the accuracy of error, respectively. In the last three cases values of the above-mentioned functions depend on the length of input data (instance of the problem) [ 3, 4 ]. As known, inclusions of these classes are proper unless P=NP [3{5].

we introduce notation for an arbitrary optimization problem A with minimization criterion: L(A) is the set of inputs (refer to an arbitrary input t 2 L(A) as a problem t); OP TA(t) is the optimal value of t 2 L(A). DA(t) is the set of feasible solutions of t 2 L(A); FA(t; s) is the value of the objective function of t 2 L(A) on the solution s 2 DA(t). The error of the solution s 2 DA(t) of t 2 L(A) is de ned as

FA(t; s) RA(t; s) = maxf OP TA(t) ;

OP TA(t) FA(t; s) g 1: Clearly, if A is the optimization problem with minimization criterion then RA(t; s) =

FA(t; s) OP TA(t) :

Here, we deal with rational numbers only. We remind the de nition of PTASreducibility [ 6 ]. Let A and B be problems from the class NPO. We say that the problem A PTAS-reduces to the problem B if and only if there exist three functions φ, and such that { φ(t; ") 2 L(B) for any t 2 L(A), and any " from the interval (0; 1); φ is polynomially computable with respect to the length jtj of the input t; { (t; s; ") 2 DA(t) for any t 2 L(A), any " 2 (0; 1), and any s 2 DB(φ(t; ")); is polynomially computable with respect to jtj and the length jsj of the solution s; { : (0; 1) ! (0; 1); if RB(φ(t; "); s) 1=" then RA(t; (t; s; ")) 1= ("); t 2 L(A), " 2 (0; 1), s 2 DB(φ(t; "))).

The following statement holds: Theorem 1. The problem SLBP is Log-APX-hard under PTAS-reducibility. Proof. We consider the minimum set cover problem [ 7 ] that can be described as follows. Given a set M and its subsets M1; :::; Mn such that ∪in=1 Mi = M , a set N~ N = f1; :::; ng is the cover of M if and only if ∪i2N~ Mi = M . The weight of each set Mi equals 1. The weight of the cover N is the sum of weights of all Mi; i 2 N . The objective is to nd the cover with minimal weight. As known, the minimum set cover problem is Log-APX-complete under PTAS-reducibility [ 8 ].

We reduce the minimum set cover problem (MSCP) to SLBP. To de ne the function φ we consider the following input of SLBP. Let S = S1 [S2 [S3, where jS1j = jS2j = jN j (for ease of description, let S1 = N ) and jS3j = jM j, D = D1 [ D2, where jD1j = jN j and jD2j = jM j (for ease of description, let D2 = M ). The planning period T consists of a single moment, i.e. jT j = 1. The set R consists of jM j load parameters. Each disk from D1 locates in a server from S1 (one disk in each server). By analogy, each disk from D2 are in a server from S3. The load of each disk d 2 D1 by each load parameter r equals 1. We associate each disk d 2 D2 with a certain load parameter r. Then, the load of disk d 2 D2 by the association load parameter r equals 1. For leftover load parameters the load is 0. The threshold load of any server s 2 S1 by any load parameter equals 1. The threshold load of any server from S2 by the rst load parameter equals 1 for some small positive . For another load parameters the threshold load equals 1. The threshold load of the servers S3 by each load parameter is 0. Let the additional costs to move a disk from a server be 0. We associate each disk d 2 D1 with two certain servers from S1 and S2, for example, the rst disk is associated with the rst server from S1 and the rst server from S2, the second disk is associated with the second server from S1 and the second server from S2, i.e. the additional costs to move a disk d 2 D1 to the associated server s 2 S2 equal 0 and to another server equal 1. The additional costs to move the disk d 2 Ms to the server s 2 S1 are equal to 0 and to another server are equal to 1. All maximum allowed additional costs are equal to 0. Scheme of the reduction is shown in gure 1.

To solve the constructed input we need to move disks from D2 to servers from S1. Then, we have to move disks from D1 that are in servers whose number of disks is more than 1. We move it to the servers from S2 (one disk to its distinct server). Thus, the optimal objective value is equal to jN j , where N is an optimal cover.

Let (x; y) be the feasible solution of the considered input. To de ne construct a feasible solution (x; y; "). First, using (x; y), construct the following solution (x~; y~). In x if the disk d 2 Ms from some s 2 N is located in a server from S3 then we move d to the server s. We consider consequently all disks d~ 2 D1, which is located in a server from S1. If there is another disk in this server then we move d~ to the appropriate server from S2. Derived distribution is x~. Thus, the objective function value does not grow up, i.e. y~ y. Moreover, all disks in S2 associate with some cover N~ . Finally, we have: as the identity function.

⊔⊓ ~ ~ RMSC (t; (x; y; ")) = jN j = jN j jN j jN j

= y = RSLB(φ(t; "); x; y)

y~ jN j 1 "

: jN j Thus, we could take the function

In previous theorem we obtained a lower bound on the location of SLBP in the approximation hierarchy. In addition, we derive an upper bound. Let us consider the maximum weighted satis ability problem (MWSP) described in [ 3 ]. In this problem there is the boolean formula φ in variables x1, x2, : : :, xn with nonnegative weights w1, w2, : : :, wn. Solution is the truth assignment to the variables that satis es φ. The measure is maxf1; ∑n

i=1 wi (xi)g, where Boolean values "true" and "false" are identi ed with 1 and 0, respectively. As known, MWSP is NPO-complete under APreducibility1 [ 3 ]. If SLBP is NPO-complete under AP-reducibility, then MWSP APreduces to SLBP. Then we can obtain a feasible solution of MWSP in polynomial time using, for example, the initial distribution of SLBP. Thus, we can solve NP-complete satis ability problem in polynomial time. Therefore, SLBP cannot be NPO-complete under AP-reducibility unless P=NP.

High complexity of the problem gives rise to development of new approximation algorithms. One of the priorities in the area is development of genetic local search methods that are known to perform well while solving many NP-hard discrete optimization problems [ 9, 10 ]. 4

Genetic local search

To solve SLBP we developed a hybrid algorithm based on the genetic algorithm and local search [ 9, 10 ]. First, we determine all parameters of this hybrid algorithm (genetic local search or GLS). Let Imax be the iteration number of the algorithm. P is the size of population (problem's solutions). Cmax is the maximal number of possible crosses of parents. The population is the set of feasible solutions of SLBP. The parent is the population's element. Then, the genetic local search scheme can be described as follows: { Step 0: Create the initial population consisting of P feasible solutions. Let i := 0; { Step 1: Take an arbitrary manner two parents from the population and cross them as follows: each disk places randomly with probability 0.5 to the rst parent server 1 AP-reducibility is a special case of PTAS-reducibility.

LS(move) LS(LK) LS(rand) GLS(move) GLS(LK) csr time value time value time value time value time value 850 59 0 65 0 <1 0 <1 0 <1 0 840 61 0 65 0 <1 0 <1 0 <1 0 830 61 0 64 0 1 0 1 0 1 0 820 61 0 65 0 1 0 1 0 1 0 810 74 0 76 0 2 0 2 0 2 0 800 88 0 90 0 20 0 20 0 20 0 750 237 8667 833 9199 284 8687 336 8362 1845 8427 700 285 121062 854 120121 143 120685 199 119840 1349 120073 650 174 382847 820 382807 73 382802 422 382673 774 382670 600 62 682399 522 682399 <1 682399 <1 682399 <1 682399 or to the second parent's server. If the resulting solution (descendant) is infeasible, because restrictions on the ejection and insertion disks were failed, then repeat crossing process. If the feasible solution is not found after Cmax crosses, then i := i + 1 and if i < Imax, then repeat step 1, else STOP; { Step 2: Apply the local search described below to the resulting solution from the previous step. Put i := i + 1. If i is not more than given iteration number Imax, then go to step 1. Otherwise STOP.

Apply the local search algorithm with randomized neighbourhood (neighbourhood rand described below) P times to the initial distribution x0 to derive the initial population. Let x~ be some feasible distribution of the problem. We use f to denote the objective function of SLBP. We describe the local search (LS) as follows: { Step 0: x := x~ and f := f (x~); { Step 1: Find the best neighbour x in the neighbourhood of x ; { Step 2: If f (x) < f , then x := x, f := f (x), and go to step 1. Else STOP.

In the local search algorithm we consider three neighbourhood types: move, KL (Kernighan-Lin) [ 9 ] and rand. Neighbour of a feasible solution x in a neighbourhood move is arbitrary feasible solution which is received from x by switching a disk to another server or swapping a disk with another disk between two servers. Let D~ be a set of disks. Neighbour of a feasible solution x in a neighbourhood move(D~ ) is arbitrary feasible solution which is received from x as follows. We take a disk (or two disks) which does not belong to the set D~ and move the disk(s) as in the neighbourhood move. We use Lmax to denote the number transformations the solution which was moved in the neighbourhood move(D~ ). Neighbour of some feasible solution x in a neighbourhood KL is arbitrary feasible solution which is received from x as the result of implementation of the following algorithm:

{ Step 0: Given x~ := x, x := x, f~ := f (x), and D := ∅; { Step 1: Repeat the following procedure Lmax times. Find the best neighbour x′ of x in move(D). If solution x′ differs from x only transferring some disk d to another server, then D := D [ d. Else, for de niteness, let two disks d and d′ were swaped, than D := D [ d [ d′ . Given x := x′ . If f (x ) < f~, then x~ := x and f~ := f (x ).

In move disks are viewed alternately and to any disk the best server or swapping disk are selected. In contrary, in the neighbourhood rand we select the disk randomly with uniform distribution. After that, we nd the best server or swapping disk. LS algorithm with the neighbourhood rand stops after IRmax steps.

If we use move (KL or rand) neighbourhood, then call the local search algorithm and genetic local search as LS(move) (LS(KL) or LS(rand)) and GLS(move) (GLS(KL) or GLS(rand)), respectively. 5

Computational results

Presented algorithms LS and GLS were implemented in C++ and tested on PC Intel Core i7-3612QM with 4 GB RAM. We used known instances with random initial data from [ 1, 2 ] to explore our algorithms. At these instances there is following dimension: jSj = 20, jDj = 200, jT j = 150, jRj = 2. The values x0ds that of the initial distribution of disks on servers were generated randomly with uniform distribution. For each disk one server was chosen randomly. The load value and additional costs for each disk an average load value cd, d 2 D, was initially assigned. It was chosen uniformly on the interval [50; 100]. Then the following values were assigned: cdrt = cd=10 + drt, bswdr = cd=10 + sdr, bsedr = cd=10 + sdr; s 2 S; d 2 D; r 2 R. Here the values drt 2 [ 20; 20] and sdr; sdr 2 [ 3; 3] were also chosen as independent uniform random values from the speci ed intervals.

We divide computational experiments in two groups. In the rst group (see tables 1 { 4) instances differ from each over only the choice of threshold loads and maximum

LS(move) LS(LK) LS(rand) GLS(move) csr time value time value time value time value 850 57 0 52 0 1 0 1 0 840 63 0 52 0 1 0 1 0 830 62 0 53 0 3 0 3 0 820 63 0 54 0 2 0 2 0 810 76 0 62 0 3 0 3 0 800 92 0 75 0 3 0 3 0 750 169 10419 176 10485 29 11100 38 10522 700 211 124552 217 124703 24 123983 24 123983 650 156 383016 210 383073 21 383228 19 383068 600 62 682399 511 682399 <1 682399 <1 682399 allowed additional costs. In the tables 1 and 2 maximum allowed additional costs are equal to 150. In contrary, in the tables 3 and 4 it is equal to 50. Moreover, threshold loads are the same for all servers. Their value is speci ed in the rst column of tables 1 { 4 and characterizes the number of instance. According to the computational experiment, instances with threshold loads equal to 700 were the most difficult for known algorithms and new methods. Therefore, the second group (see table 5) instances consist of 10 instances with maximum allowed additional costs equal to 150 and threshold loads equal to 700, i.e. we can say that these instances are the most difficult instances of servers load balancing problem for real dimension.

In the computational experiments we used the following empirical parameters of algorithms. We took Imax = 200, P = 6, IRmax = 20000, Cmax = Lmax = 30. We can increase IRmax to 100000 { 200000 and decrease Imax to 50 { 100 to reduce the computation time with small loss.

Algorithms LS(move), LS(KL), LS(rand), GLS(move), and GLS(KL) are compared with servers load balancing problem linear relaxation (LP ), algorithm ILP from [ 1 ] based on the transformation the solution of linear relaxation and local search with neighborhood of exponential size (algorithm M LS) described in [ 2 ].

Columns value and time correspond to objective function value and computational time of the best found solution, respectively. Experimental studies show the high efficiency of the developed genetic local search methods in comparison with known algorithms. Local search algorithm with randomized neighbourhood often obtains a good solution in short time. Therefore, we used this method to obtain a good initial population. Algorithms LS(rand) and GLS(move) were more efficient than method ILP and comparable with method M LS. Moreover, the relative deviation from the linear relaxation does not exceed 0,12 (12 percent). Finally, algorithm GLS(move) does not signi cantly exceed in accuracy and signi cantly exceed in computational time GLS(KL) (see table 2). Algorithms LS(rand), LS(move), and LS(KL) are same in accuracy, but LS(rand) signi cantly exceed LS(move) and LS(KL) in computational time (see tables 2 and 4). In this work the servers load balancing problem is considered. For solution of this problem new approximate approach based on the genetic local search is proposed. Experimental studies show high efficiency of the developed approximate methods. Approximability of the problem is analyzed. It is proven that the problem is Log-APX-hard under PTAS-reducibility and cannot be NPO-complete under AP-reducibility unless P=NP.

For the further research it is interesting to consider neighborhood of exponential size (see [ 2 ]) and another neighbourhoods, new crossing procedures, for example, procedure of optimal crossing [ 11 ], path relinking algorithm [ 9 ] and another heuristic methods. As the exact location of the problem in the approximation hierarchy did not established, it is planned to specify the upper and lower approximation bound.

Acknowledgments. This research was supported by the Ministry of Education and Science of the Republic of Kazakhstan (grant 0115PK00546).

References

1. Kochetov , Yu.A. , Kochetova , N.A. : Problem of Load Balancing Servers . Vestnik Novosib. Gos. Univ. Ser. Inform. Tekhnol . 11 ( 4 ), 71 { 76 ( 2013 )

2. Davydov , I. , Kochetov , Yu. , Kononova , P. : Local Search with an Exponential Neighborhoodfor the Servers Load Balancing Problem . Journal of Applied and Industrial Mathematics . 9 ( 1 ), 27 - 35 ( 2015 )

3. Ausiello , G. , Crescenzi , P. , Gambosi , G. , Kann , V. , Marchetti-Spaccamela , A. , Protasi , M. : Complexity and approximation: combinatorial optimization problems and their aproximability properties . Berlin: Springer-Verlag, ( 1999 )

4. Bazgan , C. , Escoffer , B. , Paschos , V. : Completeness in standard and differential approximation classes: Poly-(D)APX- and (D) PTAS-completeness. Theoret. Comput. Sci . 339 , 272 - 292 ( 2005 )

5. Crescenzi , P. , Kann , V. , Silvestri , R. , Trevisan , L. : Structure in approximation classes . SIAM J. COMPUT . 28 ( 5 ), 1759 - 1782 ( 1999 )

6. Crescenzi , P. , Trevisan , L. : On approximation scheme preserving reducibility and its application . Proc. 14th Annual Conference on Foundation of Software Technology and Teoretical Computer Science. Lecture Notes in Computer Science 880 , Springer-Verlag, Belrin , 330 - 341 ( 1994 )

7. Garey , M. , Johnson , D.: Computers and Intractability: A Guide to the Theory of NPCompleteness . San Francisco, Freeman, ( 1979 ); Mir, Moscow, ( 1982 )

8. Escoffier , B. , Paschos , V. Th .: Completeness in approximation classes beyond APX . Theoret. Comput. Sci . 359 , 369 - 377 ( 2006 )

9. Kochetov , Yu.A. , Plyasunov , A.V. : Genetic local search the graph partitioning problem under cardinality constraints . Computational Mathematics and Mathematical Physics . 52 ( 1 ), 157 - 167 ( 2012 )

10. Kochetov , Yu., Panin , A. , Plyasunov , A. : Comparison of metaheuristics for the bilevel facility location and mill pricing problem . Journal of Applied and Industrial Mathematics . 9 ( 3 ), 392 - 401 ( 2015 )

11. Eremeev , A.V. , Kovalenko , Ju.V.: Optimal recombination in genetic algorithms for combinatorial optimization problems { part I . Yougoslav Journal of Operations Research . 24 ( 1 ), 1 - 20 ( 2014 )