Information Technology Reference
In-Depth Information
We start with the
Set Partitioning Problem
. We will illustrate this with an old example
from computational folklore: we are to partition the integers from 1 to 100 into two sets
of 50, such that the sums of the square roots in each set are as close to equal as possible.
There are various ways to set this up as a problem for
NMinimize
. We will show
two of them. First we will utilize a simple way of choosing 50 elements from a set of
100. We will use 100 real values, all between 0 and 1. (Note that we are using continuous
variables even though the problem itself involves a discrete set.) We take their
relative
positions
as defining a permutation of the integers from 1 to 100. A variant of this
approach to decoding permutations is described in [4, 3].
In more detail: their sorted ordering (obtained, in our code, from the
Mathematica
Ordering
function) determines which is to be regarded as first, which as second, and
so on. As this might be confusing, we illustrate the idea on a smaller set of six values.
We begin with our range of integers from 1 to 6.
smallset = Range[6]
smallset = Range[6]
{
}
Now suppose we also have a set of six real values between 0 and 1.
1
,
2
,
3
,
4
,
5
,
6
vals = RandomReal[1
,
{
}
vals = RandomReal[1
,
vals = RandomReal[1
,
{
{
6
6
6
}
}
]
]
]
{
0
.
131973
,
0
.
80331
,
0
.
28323
,
0
.
694475
,
0
.
677346
,
0
.
255748
}
We use this second set of values to split
smallset
into two subsets of three, simply
by taking as one such subset the elements with positions corresponding to those of the
three smallest member of
vals
. The complementary subset would therefore be the
elements with positions corresponding to those of the three largest members of
vals
.
One can readily see (and code below will confirm) that the three smallest elements of
vals
, in order of increasing size, are the first, sixth, and third elements.
Ordering[vals]
{
1
,
6
,
3
,
5
,
4
,
2
}
We split this into the positions of the three smallest, and those of the three largest, as
below.
{
{
{
smallindices
,
largeindices
smallindices
,
largeindices
smallindices
,
largeindices
}
}
}
=
{
{
{
Take[#
,
3]
,
Drop[#
,
3]
Take[#
,
3]
,
Drop[#
,
3]
Take[#
,
3]
,
Drop[#
,
3]
}
}
}
&[Ordering[vals]]
=
=
&[Ordering[vals]]
&[Ordering[vals]]
{{
1
,
6
,
3
}
,
{
5
,
4
,
2
}}
We now split smallset according to these two sets of indices. Because it is simply the
values one through six, the subsets are identical to their positions.
{
{
{
s1
,
s2
s1
,
s2
s1
,
s2
}
}
}
= Map[smallset[[#]]&
,
= Map[smallset[[#]]&
,
= Map[smallset[[#]]&
,
{
{
{
smallindices
,
largeindices
smallindices
,
largeindices
smallindices
,
largeindices
}
}
}
]
]
]
{{
1
,
6
,
3
}
,
{
5
,
4
,
2
}}
Search WWH ::
Custom Search