Hirsch M.J., Pardalos P.M., Murphey R. Dynamics of Information Systems: Theory and Applications

Подождите немного. Документ загружается.

356 E.L. Pasiliao Jr.

Fig. 19.1 Local search

PROCEDURE LocalSearch(S)

1 S

Best

← S

2 NS ← Neighborhood(S

Best

)

3 WHILE NS =∅ →

4 S ← SelectSolution(NS)

5 NS ←NS \{S}

6 IF Obj(S) < Obj(S

Best

) →

7 S

Best

← S

8 NS ← Neighborhood(S

Best

)

9 END

10 END

11 RETURN(S

Best

)

END LocalSearch

We will now explore intrapermutation and interpermutation k-exchange neigh-

borhoods. From the permutation formulation of the multidimensional assignment

problem, we are able to perform unique types of k-exchanges that would be dif-

ﬁcult to implement on any other combinatorial optimization problem. The permu-

tation formulation unique in how it can be easily reduced to a lower dimensional

assignment problem by simply ﬁxing some of the permutation vectors. One of these

is the intrapermutation n-exchange, which would normally have a complexity of

O(n!). Every possible permutation of a vector with n elements would have to be

calculated. However, because of the permutation formulation, we are able to ex-

plore the n-exchange neighborhood with a complexity of only O(n

). We are also

able to perform interpermutation exchanges in which entire permutation vectors are

exchanged in one move. We explore and present experimental results for the dif-

ferent types of k-exchanges. Variable depth interchange, path relinking, and vari-

able neighborhoods, which are extensions of the k-exchange neighborhoods, are

discussed in Sect. 19.3.

19.2.1 Intrapermutation Exchanges

Here, we discuss the ﬁrst case of intrapermutation exchanges where only the el-

ements that are already in the current solution are candidates for exchange. Al-

though n

≤n

∀m = 1, 2,...,M −1, the neighborhoods deﬁned here only allow

exchanges between elements that are currently in the solution. The maximum num-

ber of assignments in an MAP is equivalent to the size of the smallest dimension, n

There are n

−n

elements in each dimension that are not in the solution and, there-

fore, do not affect the objective function.

Let φ be a permutation vector of n

elements. If we deﬁne ψ as another permu-

tation of the same elements from φ, then the set of all differences between these two

distinct permutation vectors is given as

(φ, ψ) =



i : φ(i) =ψ(i), ∀ i =1, 2,...,n



(19.4)

19 Local Neighborhoods for the Multidimensional Assignment Problem 357

Deﬁne the distance between φ and ψ as

(φ, ψ) =



(φ, ψ)



(19.5)

We can now deﬁne a k-exchange neighborhood for any one of the M permutation

vectors, φ

,ofn

elements that constitute a feasible solution to the MAP. This

neighborhood includes all n

-permutations, N

k,n

(φ

), such that the distance be-

tween φ

and any ψ

∈N

k,n

(φ

) is no greater than the value of k,

k,n

(φ

) =



: d

(φ

,ψ

) ≤k; 0 ≤k ≤n



(19.6)

Continuing this approach to a set of permutations, we naturally deﬁne the

k-exchange neighborhood for Φ ={φ

,φ

,...,φ

M−1

} as

k,n

(Φ) =



Ψ : d

(φ

,ψ

) ≤k; φ

∈Φ, ψ

∈Ψ



(19.7)

where Ψ is a set of M permutation vectors corresponding to the original set Φ.Note

that the size of the k-exchange neighborhood for an M-dimensional assignment

problem with M −1 permutation vectors is given by



k,n

(Φ)



M−1



m=0



k,n

(φ

)



(19.8)

Although we normally ﬁx the ﬁrst permutation φ

in the MAP formulation, the

product above is applied for m ≥ 0. Performing exchanges on φ

produces addi-

tional feasible solutions since the exchanges are limited to k<n

. The neighbor-

hood size for the MAP using this deﬁnition of a neighborhood grows exponentially

with the number of dimensions.

If we deﬁne the set of all differences between two sets of permutation vectors Φ

and Ψ as



(Φ, Ψ ) =



m : d

(φ

,ψ

)>0, ∀m =1, 2,...,M; φ

∈Φ, ψ

∈Ψ



(19.9)

then the distance between Φ and Ψ is given by

(Φ, Ψ ) =





(Φ, Ψ )



(19.10)

We can now deﬁne another k-exchange neighborhood for a set of permutation vec-

tors as

k,n

(Φ) =



Ψ : d

(φ

,ψ

) ≤k, D

(Φ, Ψ ) ≤1; φ

∈Φ, ψ

∈Ψ



(19.11)

This neighborhood is much smaller than N

k,r

(Φ) because it limits the number of

k-exchanges to one permutation vector at a time. The previous neighborhood def-

inition allows k-exchanges in multiple permutation vectors. Note that the size of

358 E.L. Pasiliao Jr.

the neighborhood for an M-dimensional assignment problem in which only a single

k-exchange is allowed at a time is given by



k,n

(Φ)



M−1



m=0



k,n

(φ

)



(19.12)

The neighborhood size for the MAP using the second deﬁnition of a neighborhood

only grows linearly with the number of dimensions.

The following relationships hold between the two k-exchange neighborhood def-

initions:

k,n

(Φ) ⊆N

k,n

(Φ) −→



k,n

(Φ)



≤



k,n

(Φ)



All single vector exchange neighborhoods are also included in the multiple vector

k-exchange neighborhoods.

19.2.1.1 2-Exchange

Although a large k-exchange neighborhood may produce better solutions, it also

incurs added complexity. The extra computation time may or may not be justiﬁed

depending on the time necessary to obtain a new initial feasible solution. If it takes a

considerable amount of time to produce a good initial solution, then spending more

time searching a larger neighborhood would be the preferred approach. However, if

a new initial solution may be found in a relatively short amount of time, it would

be better to limit the neighborhood to a small size. Because of the computational

difﬁculty in implementing exchanges for k>2 elements, we focus this section on

2-exchange neighborhoods.

The 2-exchange neighborhood for a permutation vector φ

is deﬁned as

2,n

(Φ) =



Ψ : d

(φ

,ψ

) ≤2; φ

∈Φ, ψ

∈Ψ



(19.13)

Note that the size of the 2-exchange neighborhood for a single permutation vector

is given by



2,n

(φ

)







(19.14)

which is simply the number of ways to choose unordered pairs from a set of n

elements. The size of a 2-exchange neighborhood for an M-dimensional assignment

problem with M −1 permutation vectors is given by



2,n

(Φ)







(19.15)

for a neighborhood that allows a 2-exchange in more than one permutation vector

and



2,n

(Φ)



=M ×





(19.16)

19 Local Neighborhoods for the Multidimensional Assignment Problem 359

PROCEDURE 2-Exchange(S, C)

1 S

Best

⇐ S

2 FOR m =0 :M −1 →

4 FOR i

=1 :n

−1 →

5 FOR i

+1 :n

→

6 old ⇐ c

),φ

),...,φ

M−1

)

),φ

),...,φ

M−1

)

7 φ

) ⇔ φ

)

8 new ⇐ c

),φ

),...,φ

M−1

)

),φ

),...,φ

M−1

)

9 IF new < old →

10 S

Best

⇐{φ

,φ

,...,φ

M−1

}

11 RETURN(S

Best

)

12 φ

) ⇔ φ

)

13 END

14 END

15 END

16 RETURN(S

Best

)

END LocalSearch

Fig. 19.2 Intrapermutation 2-exchange local search

for a neighborhood that is limited to a single 2-exchange at a time.

Figure 19.2 presents the implementation of the intrapermutation 2-exchange

neighborhood. The heuristic permutes two elements at a time for each dimension

until all possible exchanges have been explored. If an improvement is found, this

solution is then stored as the current solution and a new neighborhood is deﬁned

and searched. When no better solution can be found, the search is terminated and

the local minimum is returned.

19.2.1.2 n-Exchange

Extending the intrapermutation k-exchange neighborhood to its limit, we present

the following neighborhood deﬁnition:

(φ

) =



: d

(φ

,ψ

) ≤n

; 0 ≤n

≤n

∀m>1



(19.17)

Note that the size of the n

-exchange neighborhood for a single permutation vector

is given by



(φ

)



! (19.18)

which is simply the number of ways to order n

elements.

The ﬁrst n

-exchange neighborhood for a set of permutation vectors, Φ,isgiven

(Φ) =



Ψ : d

(φ

,ψ

) ≤n

; φ

∈Φ, ψ

∈Ψ



(19.19)

where Ψ is a set of M permutations vectors corresponding to the original set Φ.The

size of this n

-exchange neighborhood for an M-dimensional assignment problem

360 E.L. Pasiliao Jr.

with M −1 permutation vectors is given by



(Φ)



M−1



m=1



(φ

)



=[n

M−1

(19.20)

The product above is applied for m>1 since we may ﬁx the ﬁrst permutation φ

without decreasing the neighborhood size. This is different from the k-exchange,

where k<n

.Ifk =n

, all the feasible solutions may be found without manipulat-

ing the φ

The second neighborhood deﬁnition for a set of permutation vectors is given by

(Φ) =



Ψ : d

(φ

,ψ

) ≤n

(Φ, Ψ ) ≤1; φ

∈Φ, ψ

∈Ψ



(19.21)

This n

-exchange neighborhood has a size of



(Φ)



M−1



m=0



(φ

)



=M ×[n

!] (19.22)

The summation here is applied for m ≥ 0, which is different from the previous

deﬁnition of an n-exchange neighborhood. The difference is that we are only able

to manipulate one permutation at a time. In the previous deﬁnition, we were allowed

to manipulate multiple permutations simultaneously. Because of this difference, we

may not ﬁx the ﬁrst permutation φ

without reducing the neighborhood size.

Figure 19.3 describes the local search procedure to improve the current solu-

tion by searching within its predeﬁned neighborhood. The heuristic performs an

-exchange by ﬁxing M −1 permutation vectors and solving for the single deci-

sion vector with a two-dimensional assignment problem solver. A 2AP is solved for

PROCEDURE n-Exchange(S, C)

1 S

Best

⇐ S

2 FOR m =0 :M −1 →

3 S ⇐ S \ φ

4 FOR i

=1 :n

→

5 FOR i

=1 :n

→

6 A

⇐ c

),...,φ

m−1

), i

,φ

m+1

),...,φ

M−1

)

7 END

8 END

9 φ

← Solve2AP(A)

10 S ⇐ S ∪ φ

11 IF Cost(S) < Cost(S

Best

) →

12 S

Best

⇐ S

13 RETURN(S

Best

)

14 END

15 RETURN(S

Best

)

END LocalSearch

Fig. 19.3 Intrapermutation n-exchange local search

19 Local Neighborhoods for the Multidimensional Assignment Problem 361

Φ ={φ

,φ

}

Permute φ

∗

← min





i,φ

(j),φ

(j)

·x





(j) ⇐ i for x

∗

=1 ∀i, j

Permute φ

∗

← min





(j),i,φ

(j),φ

(j)

·x





(j) ⇐ i for x

∗

=1 ∀i, j

Permute φ

Fig. 19.4 Intrapermutation n-exchange example, C ∈

3×4×4×5

each dimension of the MAP until either a better solution is found or all the dimen-

sions are explored. If an improvement is found, this solution is then stored as the

current solution and a new neighborhood is deﬁned and searched. When no better

solution is available, the search is terminated and the local minimum is returned.

An example of how the n-exchange neighborhood for C ∈

3×4×4×5

is given in

Fig. 19.4. The coefﬁcients of the 2AP are found by ﬁxing M −1 =3 permutation

vectors or dimensions at a time. Therefore, a 2AP solver must be implemented for

each dimension.

19.2.2 Interpermutation Exchanges

This section discusses exchanges that are performed between the permutation vec-

tors of the MAP permutation formulation. By deﬁning a limited number of ex-

changes that may be made between the elements of a permutation vector, we can

deﬁne a local search neighborhood.

So far we have only investigated k-exchanges within a given permutation vec-

tor φ

. We now explore the possibility of ﬁnding better solutions by interchanging

the indices themselves. This section discusses the ﬁrst case of interpermutation ex-

changes; all the dimensions in the MAP have exactly the same size. Again we use

the permutation formulation of the MAP with M permutation vectors.

362 E.L. Pasiliao Jr.

If we deﬁne the set of all differences between two sets of permutation vectors Φ

and Ψ as



(Φ, Ψ ) =



m : d

(φ

,ψ

)>0, ∀m =1, 2,...,M; φ

∈Φ, ψ

∈Ψ



(19.23)

where d

(φ

,ψ

) is the distance between permutation vectors φ

and ψ

, then

the distance between Φ and Ψ is given by

(Φ, Ψ ) =





(Φ, Ψ )



(19.24)

We can now deﬁne an interpermutation k-exchange neighborhood for Φ as the set of

all permutation vector sets such that the distance between Φ and any Ψ ∈N

k,M

(Φ)

is no greater than the value of k,

k,M

(Φ) =



Ψ : d

(Φ, Ψ

) ≤k; 0 <k<M



(19.25)

Note that the size of the 2-exchange neighborhood is given by



2,M

(Φ)







(19.26)

which is simply the number of ways to choose unordered pairs from a set of M

permutation vectors.

The pseudo-code for performing an interpermutation standard 2-exchange is

showninFig.19.5. The procedure explores every possible 2-exchange between per-

mutations until a better solution is found. Lines 6–9 perform the exchanges between

two permutation vectors, while lines 10–13 check if the exchange produced a bet-

ter solution. If no improvement is found, then we ﬁnd another pair of vectors to

exchange.

The standard interpermutation 2-exchange is implemented in a straightforward

manner when all of the dimensions in the MAP have the same size. However, it is

often the case when the dimension sizes are not homogeneous. For this situation, we

need a method for deciding which elements of the larger permutation vectors will

be included into and removed from the current solution.

Performing 2-exchanges between two dimensions of the same size is straightfor-

ward since every element in the ﬁrst dimension is feasible in the second dimension

considered. The difﬁculty arises when the dimensions have different sizes. When

for some dimension m, then exchanging one permutation for another may

produce infeasible results. As an example, suppose that we have a four-dimensional

assignment problem with cost array C ∈

3×4×4×5

. A current feasible solution may

be given as the following:

⎡

⎢

⎣

⎤

⎥

⎦

⎡

⎢

⎣

⎤

⎥

⎦

⎡

⎢

⎣

⎤

⎥

⎦

⎡

⎢

⎣

⎤

⎥

⎦

f =c

1121

2443

3215

19 Local Neighborhoods for the Multidimensional Assignment Problem 363

PROCEDURE 2-Exchange(S, C)

1 S

Best

⇐ S

2 FOR m

=0 :M −2 →

3 S ⇐ S \ φ

4 FOR m

+1 :M −1 →

5 S ⇐ S \ φ

6 FOR i =1 :n

→

7 ψ

(i) ⇐ φ

(i)

8 ψ

(i) ⇐ φ

(i)

9 END

10 IF Cost(S ∪ψ

∪ψ

)<Cost(S

Best

) →

11 S

Best

⇐ S ∪ψ

∪ψ

12 RETURN(S

Best

)

13 END

14 S ⇐ S ∪ φ

15 END

16 S ⇐ S ∪ φ

17 END

18 RETURN(S

Best

)

END LocalSearch

Fig. 19.5 Interpermutation standard 2-exchange local search

If we perform an exchange between permutation vectors φ

and φ

, where n

then we have a standard interpermutation 2-exchange with a resulting change in the

objective function.

⎡

⎢

⎣

⎤

⎥

⎦

⎡

⎢

⎣

⎤

⎥

⎦

⎡

⎢

⎣

⎤

⎥

⎦

⎡

⎢

⎣

⎤

⎥

⎦

f =c

1211

2443

3125

The cost coefﬁcients c

1121

and c

3215

have been removed from the solution set and

replaced with c

1211

and c

3125

The interpermutation 2-exchange is smaller than its intrapermutation counter-

part for most MAP instances with the exception occurring when the sizes are much

smaller than the number of dimensions. However, because of the added complexity

in implementing the intrapermutation 2-exchange, the interpermutation 2-exchange

is a more efﬁcient neighborhood to search since only two cost elements are analyzed

every time an exchange is made. The number of reassignments is also smaller for

364 E.L. Pasiliao Jr.

the intrapermutation version. For the interpermutation 2-exchange, all n

feasible

cost elements are analyzed for each exchange.

19.3 Extensions

The main types of local neighborhood search applied to multidimensional assign-

ment problems are k-exchanges. Extensions of these neighborhoods include variable

neighborhood, variable depth interchange, and path relinking. We outline the MAP

implementation procedures for all three extensions in this section.

19.3.1 Variable Depth Interchange

Balas and Saltzman [3] used a variable depth interchange neighborhood in their

branch-and-bound algorithm for the three-index assignment problem. It is based on

the heuristic applied by Lin and Kernighan [12] on the traveling salesman problem

and described by Ahuja, Ergun, Orlin, and Punnen [1] in their survey of neighbor-

hood search algorithms. Figure 19.6 presents a pseudo-code of variable depth inter-

change for multidimensional assignment problems. The heuristic can escape local

minima by allowing moves to nonimproving solutions until a threshold is reached.

There is, however, no guarantee of escaping any local minima for this problem.

19.3.2 Path Relinking

Path relinking is a strategy proposed by Laguna and Marti [11] to connect multiple

high-quality solutions in an effort to ﬁnd an even better solution. Aiex, Pardalos,

Resende, and Toraldo [2] implemented a Greedy Randomized Adaptive Search Pro-

cedure (GRASP) with path relinking to the three-dimensional assignment problem.

Their path relinking approach uses two types of moves in which either one or two

pairs of indices are interchanged between two cost coefﬁcients from different fea-

sible solution sets. Because the moves are performed within a single permutation

vector of the MAP permutation formulation, we will refer to their approach as an

intrapermutation path relinking. We also propose a type of interpermutation path

relinking where permutations between two good solutions are exchanged. This ap-

proach is not as exhaustive as the intrapermutation approach, but it is also signif-

icantly less complex while still managing to combine qualities from one or more

high-quality solutions.

19 Local Neighborhoods for the Multidimensional Assignment Problem 365

PROCEDURE VariableDepthInterchange(S)

1 S

Best

← S

2 G ← 0

3 i

∗

←RandomSelect{1, 2,...,n

}

4 WHILE G>0 →

5 FORALL m =0, 1,...,M −1 →

6 g

= min

∗

),...,φ

m−1

∗

), φ

(j), φ

m+1

∗

),...,φ

M−1

∗

)

}

7 c

∗

),...,φ

m−1

∗

), φ

∗

), φ

m+1

∗

),...,φ

M−1

∗

)

←g

∗

=min

8 G ←G −g

∗

),...,φ

m−1

∗

), φ

∗

), φ

m+1

∗

),...,φ

M−1

∗

)

9 S ← S \{c

∗

),φ

∗

),...,...,φ

M−1

∗

)

}

10 S ← S ∪{c

∗

),...,φ

m−1

∗

), φ

∗

), φ

m+1

∗

),...,φ

M−1

∗

)

}

11 S ← S \{c

∗

),φ

∗

),...,...,φ

M−1

∗

)

}

12 S ← S ∪{c

∗

),...,φ

m−1

∗

), φ

∗

), φ

m+1

∗

),...,φ

M−1

∗

)

}

13 i

∗

←j

∗

14 IF Obj(S) < Obj(S

Best

) → S

Best

← S

15 END

16 RETURN(S

Best

)

END VariableDepthInterchange

Fig. 19.6 Variable depth interchange

19.3.2.1 Intrapermutation Relinking

The intrapermutation path-relinking approach described by Aiex, Pardalos, Re-

sende, and Toraldo [2] for the three-dimensional assignment problem is generalized

for the multidimensional assignment problem in Fig. 19.7. This heuristic systemat-

ically transforms an initial solution Φ

into a guiding solution Φ

by performing

exchanges within the permutation vectors of the initial solution. Each solution is a

set of M permutation vectors. The transformation happens one vector at a time start-

ing from m =0. Lines 6 through 13 are performed as long as the m-th vector of the

initial solution is different from the corresponding vector of the guiding solution.

Index u is the location of an element in Φ

that is different from Φ

. Index v is the

location of the element that needs to moved to index location u.

The objective function value of Φ

is evaluated after every exchange. We keep the

solution that provides the lowest objective value z. A constraint to the new solution

is that it not be the same as the guiding solution. This forces a new solution to be kept

even if the guiding solution has a better value. Finally, a local search is performed

on the best of the new solutions.