Information Technology Reference
In-Depth Information
{
5
,
11
,
20
,
15
,
22
,
2
,
25
,
8
,
9
,
1
,
18
,
16
,
3
,
6
,
19
,
24
,
21
,
14
,
7
,
10
,
17
,
12
,
4
,
23
,
13
}
p
=
p
=
p
=
{
{
5
,
11
,
20
,
15
,
22
,
2
,
25
,
8
,
9
,
1
,
18
,
16
,
3
,
6
,
19
,
24
,
21
,
14
,
7
,
10
,
17
,
12
,
4
,
23
,
13
5
,
11
,
20
,
15
,
22
,
2
,
25
,
8
,
9
,
1
,
18
,
16
,
3
,
6
,
19
,
24
,
21
,
14
,
7
,
10
,
17
,
12
,
4
,
23
,
13
}
}
;
;
;
We compute the objective function value we obtain from this permutation. As a sort
of baseline, we show the result one obtains from applying no permutation. We then
compute results of applying several random permutations. This gives some idea of how
to gauge the results below.
best = Apply[Plus
,
Flatten[mat1
∗
permuteMatrix[mat2
,
p
]]]
best = Apply[Plus
,
Flatten[mat1
best = Apply[Plus
,
Flatten[mat1
∗
∗
permuteMatrix[mat2
,
p
]]]
permuteMatrix[mat2
,
p
]]]
3744
baseline = Apply[Plus
,
Flatten[mat1
∗
mat2]]
baseline = Apply[Plus
,
Flatten[mat1
baseline = Apply[Plus
,
Flatten[mat1
∗
∗
mat2]]
mat2]]
4838
randomvals = Tab le[
randomvals = Tab le[
perm = Ordering[RandomReal[
{
0
,
1
}
,
{
}
perm = Ordering[RandomReal[
perm = Ordering[RandomReal[
{
{
0
,
1
0
,
1
}
}
,
,
{
{
25
25
25
}
}
]];
]];
]];
Apply[Plus
,
Flatten[mat1
∗
permuteMatrix[mat2
,
perm]]]
,
{
}
Apply[Plus
,
Flatten[mat1
Apply[Plus
,
Flatten[mat1
∗
∗
permuteMatrix[mat2
,
perm]]]
,
permuteMatrix[mat2
,
perm]]]
,
{
{
10
10
10
}
}
]
]
]
{
4858
,
5012
,
5380
,
5088
,
4782
,
4994
,
5032
,
5044
,
5088
,
5094
}
A substantially longer run over random permutations gives an indication of how hard it
is to get good results via a naive random search.
SeedRandom[1111];
SeedRandom[1111];
Timing[randomvals = Tab le[
Timing[randomvals = Tab le[
Timing[randomvals = Tab le[
perm = Ordering[RandomReal[
{
0
,
1
}
,
{
}
perm = Ordering[RandomReal[
perm = Ordering[RandomReal[
{
{
0
,
1
0
,
1
}
}
,
,
{
{
25
25
25
}
}
]];
]];
]];
∗
permuteMatrix[mat2
,
perm]]]
,
To tal[Flatten[mat1
To tal[Flatten[mat1
To tal[Flatten[mat1
∗
∗
permuteMatrix[mat2
,
perm]]]
,
permuteMatrix[mat2
,
perm]]]
,
{
1000000
}
]; ]
{
{
1000000
1000000
}
}
]; ]
]; ]
{
449
.
06
,
Null
}
Min[randomvals]
4284
4.6.1
Relative Position Indexing for Permutations
We must decide how to make a set of values into a permutation. Our first approach is
nearly identical to the ensemble order method we used on the set partition problem.
Specifically, we will let the
Ordering
function of a set of real values determine a
permutation.
QAP
Outline of QAP
1. Input: square matrices
M
1
and
M
2
each of dimension
n
, along with parameter
settings to pass to
NMinimize
.
2. Form a vector of variables of length
n
. Give them initial ranges from 0 to 1.
Search WWH ::
Custom Search