Information Technology Reference
In-Depth Information
{
2
,
3
,
6
,
8
,
9
,
10
,
11
,
17
,
18
,
21
,
24
,
25
,
26
,
27
,
28
,
29
,
30
,
33
,
34
,
35
,
39
,
40
,
48
,
53
,
54
,
56
,
57
,
58
,
61
,
63
,
64
,
67
,
68
,
69
,
70
,
72
,
74
,
75
,
76
,
77
,
80
,
81
,
82
,
85
,
86
,
92
,
93
,
95
,
96
,
98
}}}}
One unfamiliar with the subject might well ask what this has to do with knapsacks.
The gist is as follows. A
Knapsack Problem
involves taking, or not taking, an element
from a given set, and attempting to optimize some condition that is a function of those
elements taken. There is a large body of literature devoted to such problems, as they
subsume the
Integer Linear Programming Problem
(in short, linear program, but with
variables constrained to be integer valued). It is a pleasant quality of Differential Evo-
lution that it can be adapted to such problems.
4.4.3
Discussion of the Two Methods
The second method we showed is a classical approach in integer linear programming.
One uses a set of variables constrained to be either 0 or 1 (that is,
binary
variables). We
constrain their sum so that we achieve a particular goal, in this case it is that exactly half
be put into one of the two subsets. While not quite a relative position indexing method,
it is similar in that positions of zeros or ones determine which of two complementary
subsets receives elements of the parent set.
The first method, which seemed to work better for Differential Evolution (at least
with parameter settings we utilized) is less common. It is a bit mysterious, in that we
use the ordering of an ensemble of reals to determine placement of individual elements
of a set. This implies a certain
nonlocality
in that a change to one value can have a
big effect on the interpretation of other entries. This is because it is their overall sorted
ordering, and not individual values, that gets used by the objective function. Though
it is not obvious that this would be useful, we saw in this example that we can get a
reasonably good result.
4.5
Minimal Covering of a Set by Subsets
The problem below was once posed in the Usenet news group comp.soft-sys.math.
mathematica. It is an archetypical example of the classical
subset covering problem
.
In this example we are given a set of sets, each containing integers between 1 and 64.
Their union is the set of all integers in that range, and we want to find a set of 12 subsets
that covers that entire range. In general we would want to find a set of subsets of mini-
mal cardinality; this is an instance where we know in advance that that cardinality is 12.
subsets =
subsets =
subsets =
{{
{{
{{
1
,
2
,
4
,
8
,
16
,
32
,
64
1
,
2
,
4
,
8
,
16
,
32
,
64
1
,
2
,
4
,
8
,
16
,
32
,
64
}
}
}
,
,
,
{
{
{
2
,
1
,
3
,
7
,
15
,
31
,
63
2
,
1
,
3
,
7
,
15
,
31
,
63
2
,
1
,
3
,
7
,
15
,
31
,
63
}
}
}
,
,
,
{
{
{
3
,
4
,
2
,
6
,
14
,
30
,
62
3
,
4
,
2
,
6
,
14
,
30
,
62
3
,
4
,
2
,
6
,
14
,
30
,
62
}
}
}
,
,
,
{
{
{
4
,
3
,
1
,
5
,
13
,
29
,
61
4
,
3
,
1
,
5
,
13
,
29
,
61
4
,
3
,
1
,
5
,
13
,
29
,
61
}
}
}
,
,
,
{
{
{
5
,
6
,
8
,
4
,
12
,
28
,
60
5
,
6
,
8
,
4
,
12
,
28
,
60
5
,
6
,
8
,
4
,
12
,
28
,
60
}
}
}
,
,
,
{
{
{
6
,
5
,
7
,
3
,
11
,
27
,
59
6
,
5
,
7
,
3
,
11
,
27
,
59
6
,
5
,
7
,
3
,
11
,
27
,
59
}
}
}
,
,
,
{
{
{
7
,
8
,
6
,
2
,
10
,
26
,
58
7
,
8
,
6
,
2
,
10
,
26
,
58
7
,
8
,
6
,
2
,
10
,
26
,
58
}
}
}
,
,
,
{
{
{
8
,
7
,
5
,
1
,
9
,
25
,
57
8
,
7
,
5
,
1
,
9
,
25
,
57
8
,
7
,
5
,
1
,
9
,
25
,
57
}
}
}
,
,
,
{
{
{
9
,
10
,
12
,
16
,
8
,
24
,
56
9
,
10
,
12
,
16
,
8
,
24
,
56
9
,
10
,
12
,
16
,
8
,
24
,
56
}
}
}
,
,
,
{
10
,
9
,
11
,
15
,
7
,
23
,
55
}
,
{
11
,
12
,
10
,
14
,
6
,
22
,
54
}
,
{
12
,
11
,
9
,
13
,
5
,
21
,
53
}
,
{
{
10
,
9
,
11
,
15
,
7
,
23
,
55
10
,
9
,
11
,
15
,
7
,
23
,
55
}
}
,
,
{
{
11
,
12
,
10
,
14
,
6
,
22
,
54
11
,
12
,
10
,
14
,
6
,
22
,
54
}
}
,
,
{
{
12
,
11
,
9
,
13
,
5
,
21
,
53
12
,
11
,
9
,
13
,
5
,
21
,
53
}
}
,
,
{
13
,
14
,
16
,
12
,
4
,
20
,
52
}
,
{
14
,
13
,
15
,
11
,
3
,
19
,
51
}
,
{
15
,
16
,
14
,
10
,
2
,
18
,
50
}
,
{
{
13
,
14
,
16
,
12
,
4
,
20
,
52
13
,
14
,
16
,
12
,
4
,
20
,
52
}
}
,
,
{
{
14
,
13
,
15
,
11
,
3
,
19
,
51
14
,
13
,
15
,
11
,
3
,
19
,
51
}
}
,
,
{
{
15
,
16
,
14
,
10
,
2
,
18
,
50
15
,
16
,
14
,
10
,
2
,
18
,
50
}
}
,
,
{
16
,
15
,
13
,
9
,
1
,
17
,
49
}
,
{
17
,
18
,
20
,
24
,
32
,
16
,
48
}
,
{
18
,
17
,
19
,
23
,
31
,
15
,
47
}
,
{
{
16
,
15
,
13
,
9
,
1
,
17
,
49
16
,
15
,
13
,
9
,
1
,
17
,
49
}
}
,
,
{
{
17
,
18
,
20
,
24
,
32
,
16
,
48
17
,
18
,
20
,
24
,
32
,
16
,
48
}
}
,
,
{
{
18
,
17
,
19
,
23
,
31
,
15
,
47
18
,
17
,
19
,
23
,
31
,
15
,
47
}
}
,
,
{
19
,
20
,
18
,
22
,
30
,
14
,
46
}
,
{
20
,
19
,
17
,
21
,
29
,
13
,
45
}
,
{
21
,
22
,
24
,
20
,
28
,
12
,
44
}
,
{
{
19
,
20
,
18
,
22
,
30
,
14
,
46
19
,
20
,
18
,
22
,
30
,
14
,
46
}
}
,
,
{
{
20
,
19
,
17
,
21
,
29
,
13
,
45
20
,
19
,
17
,
21
,
29
,
13
,
45
}
}
,
,
{
{
21
,
22
,
24
,
20
,
28
,
12
,
44
21
,
22
,
24
,
20
,
28
,
12
,
44
}
}
,
,
Search WWH ::
Custom Search