Information Technology Reference
In-Depth Information
that this approach is far from scientific. About the best one can say is that, while it is not
obviously fantastic, it is also not obviously bad. Note that this sort of situation happens
often in engineering, and that is why one can make nice incremental improvements to a
technology such as optimization.
4.4.2 Set Partitioning via Knapsack Approach
Another approach to this problem is as follows. We take the full set and pick 100 corre-
sponding random integer values that are either 0 or 1. An element in the set is put into
one or the other subset according to the value of the bit corresponding to that element.
For this to give an even split we also must impose a constraint that the size of each
subset is half the total size. To get an idea of what these constraints are, we show again
on our small example of size six.
vars = Array[
x
,
6];
vars = Array[
x
,
6];
ranges = Map[(0
<
=#
<
=1)&
,
vars];
vars = Array[
x
,
6];
ranges = Map[(0
<
=#
<
=1)&
,
vars];
Join[ranges
,
ranges = Map[(0
<
=#
<
=1)&
,
vars];
Join[ranges
,
Join[ranges
,
{
{
{
Element[vars
,
Integers]
,
Apply[Plus
,
vars]==3
Element[vars
,
Integers]
,
Apply[Plus
,
vars]==3
Element[vars
,
Integers]
,
Apply[Plus
,
vars]==3
}
}
}
]
]
]
{
0
≤
x
[1]
≤
1
,
0
≤
x
[2]
≤
1
,
0
≤
x
[3]
≤
1
,
0
≤
x
[4]
≤
1
,
0
≤
x
[5]
≤
1
,
0
≤
x
[6]
≤
1
,
(
x
[1]
|
x
[2]
|
x
[3]
|
x
[4]
|
x
[5]
|
x
[6])
∈
Integers
,
x
[1]+
x
[2]+
x
[3]+
x
[4]+
x
[5]+
x
[6]==3
}
We are now ready to define our new objective function.
spfun2
Outline of spfun2
1. Input: a vector of integers, of even length
n
. All entries are 0 or 1.
2. Convertevery0to-1.
3. Form a list of square roots of the integers in
.
4. Multiply, componentwise, with the list of ones and negative ones.
5. Return the absolute value of the sum from step (4).
{
1
,...,
n
}
spfun2[vec :
spfun2[vec :
spfun2[vec :
{
{
{
Integer
Integer
Integer
}
]:=Abs[(2
}
}
]:=Abs[(2
]:=Abs[(2
∗
∗
∗
vec
vec
vec
−
−
−
1)
.
Sqrt[
N
[Range[Length[vec]]]]]
1)
.
Sqrt[
N
[Range[Length[vec]]]]]
1)
.
Sqrt[
N
[Range[Length[vec]]]]]
Again we use our small example. What would our objective function be if the vector
has ones in the first two and last places, and zeros in the middle three? First we find the
exact value.
exactval = Abs[To tal[Sqrt[smallset[[
exactval = Abs[To tal[Sqrt[smallset[[
exactval = Abs[To tal[Sqrt[smallset[[
{
{
{
1
,
6
,
3
1
,
6
,
3
1
,
6
,
3
}
}
}
]]]]
]]]]
]]]]
−
−
−
To tal[Sqrt[smallset[[
To tal[Sqrt[smallset[[
To tal[Sqrt[smallset[[
{
{
{
5
,
4
,
2
5
,
4
,
2
5
,
4
,
2
}
}
}
]]]]]
]]]]]
]]]]]
1 +
√
2
−
√
3 +
√
5
−
√
6
N
[exactval]
N
[exactval]
N
[exactval]
0
.
468741
We see that, as expected, this agrees with our objective function.
Search WWH ::
Custom Search