Relative Position Indexing Approach - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 100

spanningSets2[set , iter , sp , seed , cp : . 5]:=Module[ spanningSets2[set , iter , sp , seed , cp : . 5]:=Module[

{

{ vars , rnges , max = Length[set] , nmin , vals },

{ vars , rnges , max = Length[set] , nmin , vals vars , rnges , max = Length[set] , nmin , vals } } , ,

vars = Array[xx , max];

vars = Array[xx , max]; vars = Array[xx , max];

rnges = Map[(0

rnges = Map[(0 ≤ # ≤ 1)& , vars];

rnges = Map[(0 ≤ ≤ # # ≤ ≤ 1)& , vars]; 1)& , vars];

{ { {

nmin , vals

nmin , vals

nmin , vals

} } } =

= =

NMinimize[ { { { Apply[Plus , vars] , Join[rnges ,

Apply[Plus , vars] , Join[rnges , Apply[Plus , vars] , Join[rnges ,

{ { {

Element[vars , Integers]

Element[vars , Integers]

Element[vars , Integers]

} } } , , ,

NMinimize[ NMinimize[

Thread[vars . set

Thread[vars . set

Thread[vars . set

≥ ≥ ≥ Tab le[1 ,

Tab le[1 , Tab le[1 ,

{ { { max } } } ]]] } } } , vars , MaxIterations , vars , MaxIterations , vars , MaxIterations → → → iter ,

iter , iter ,

max max ]]] ]]]

Method Method Method →{ →{ →{ DifferentialEvolution , CrossProbability DifferentialEvolution , CrossProbability DifferentialEvolution , CrossProbability → → → cp , cp , cp ,

SearchPoints SearchPoints SearchPoints → → → sp , RandomSeed sp , RandomSeed sp , RandomSeed → → → seed seed seed } } ]; } ]; ];

vals = vars/.vals; vals = vars/.vals;

{ { { nmin , vals nmin , vals nmin , vals } } } ] ] ]

Timing[ Timing[ Timing[ { { { min , sets min , sets min , sets } } } = spanningSets2[mat , 2000 , 100 , 0 ,. 9]] = spanningSets2[mat , 2000 , 100 , 0 ,. 9]] = spanningSets2[mat , 2000 , 100 , 0 ,. 9]]

{ 1930 . 4Second , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 ,

0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 0 ,
0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1

{ 12 ., {

}}}

We have again obtained a result that uses 12 subsets. We check that it covers the entire
range.

To tal[Map[Min[# , 1]& , sets . mat]]

64

We see that this method was much slower. Experience indicates that it needs a lot of
iterations and careful setting of the CrossProbability option. So at present NMinimize
has difficulties with this formulation. All the same it is encouraging to realize that one
may readily set this up as a standard knapsack problem, and still hope to solve it using
Differential Evolution. Moreover, as the alert reader may have observed, we actually
had an added benefit from using this method: nowhere did we need to assume that
minimal coverings require 12 subsets.

4.6 An Assignment Problem

Our next example is a benchmark from the literature of discrete optimization. We are
given two square matrices. We want a permutation that, when applied to the rows and
columns of the second matrix, multiplied element-wise with corresponding elements of
the first, and all elements summed, gives a minimum value. The matrices we use have
25 rows. This particular example is known as the NUG25 problem. It is an example of
a Quadratic Assignment Problem (QAP). The optimal result is known and was verified
by a large parallel computation. We mention that the methods of handling this problem
can, with minor modification, be applied to related problems that require the selecting
of a permutation (for example, the traveling salesman problem).