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

3. Set up constraints.
All variables are between 1 and m .
All variables are integer valued.
4. Call NMinimize , using the constraints and scfun as defined above, along
with option settings.
5. Return the minimal value (which we want to be 1, in order that there be full
coverage), and the list of positions denoting which subsets we used in the
cover.

spanningSets[set , nsets , iter , sp , cp ]:=Module[ spanningSets[set , nsets , iter , sp , cp ]:=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 , nsets];

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

rnges = Map[(1

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

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

{ { { nmin , vals nmin , vals nmin , vals } } } = NMinimize[ = NMinimize[ = NMinimize[

{ { { scfun[vars , set , max] , Append[rnges , Element[vars , Integers]] scfun[vars , set , max] , Append[rnges , Element[vars , Integers]] scfun[vars , set , max] , Append[rnges , Element[vars , Integers]] } } } , , ,

vars , MaxIterations vars , MaxIterations vars , MaxIterations → → → iter , iter , iter ,

Method Method Method →{ →{ →{ DifferentialEvolution , SearchPoints DifferentialEvolution , SearchPoints DifferentialEvolution , SearchPoints → → → sp , CrossProbability sp , CrossProbability sp , CrossProbability → → → cp cp cp } } } ]; ]; ];

vals = Union[vars/.vals]; vals = Union[vars/.vals];

{

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

In small tuning runs I found that a fairly high crossover probability setting seemed
to work well.

Timing[ Timing[ Timing[ { { { min , sets min , sets min , sets } } } = spanningSets[subsets , 12 , 700 , 200 ,. 94]] = spanningSets[subsets , 12 , 700 , 200 ,. 94]] = spanningSets[subsets , 12 , 700 , 200 ,. 94]]

{ 365 . 099 , { 1 ., { 1 , 7 , 14 , 21 , 24 , 28 , 34 , 35 , 47 , 52 , 54 , 57 }}}

Length[Union[Flatten[subsets[[sets]]]]]

64

While this is not lightning fast, we do obtain a good result in a few minutes of run
time.
We note that while this was not coded explicitly to use relative position indexing,
it could have been. That is, we could have used vectors of 64 values between 0 and 1,
and taken the positions of the smallest 12 to give 12 members of subsets. The interested
reader may wish to code this variant.

4.5.2 Subset Covering via Knapsack Formulation
Another method is to cast this as a standard knapsack problem. First we transform
each of our set of subsets into a bit vector representation. In this form each subset is
represented by a positional list of zeros and ones. In effect we are translating from a
sparse to a dense representation.