main page
modules
namespaces
classes
files
Gecode home
Generated on Thu Feb 21 2013 23:11:38 for Gecode by
doxygen
1.8.3.1
test
int
bin-packing.cpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Christian Schulte <schulte@gecode.org>
5
*
6
* Copyright:
7
* Christian Schulte, 2010
8
*
9
* Last modified:
10
* $Date: 2010-10-07 08:20:35 +1100 (Thu, 07 Oct 2010) $ by $Author: schulte $
11
* $Revision: 11468 $
12
*
13
* This file is part of Gecode, the generic constraint
14
* development environment:
15
* http://www.gecode.org
16
*
17
* Permission is hereby granted, free of charge, to any person obtaining
18
* a copy of this software and associated documentation files (the
19
* "Software"), to deal in the Software without restriction, including
20
* without limitation the rights to use, copy, modify, merge, publish,
21
* distribute, sublicense, and/or sell copies of the Software, and to
22
* permit persons to whom the Software is furnished to do so, subject to
23
* the following conditions:
24
*
25
* The above copyright notice and this permission notice shall be
26
* included in all copies or substantial portions of the Software.
27
*
28
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35
*
36
*/
37
38
#include "
test/int.hh
"
39
40
#include <
gecode/minimodel.hh
>
41
#include <climits>
42
43
namespace
Test {
namespace
Int {
44
46
namespace
BinPacking
{
47
53
54
class
LoadBinAssignment
:
public
Assignment
{
55
protected
:
57
int
n_bins
;
59
int
n_items
;
61
Gecode::IntSet
d_load
;
63
Gecode::IntSet
d_bin
;
65
int
load
;
67
Gecode::IntSetValues
*
dsv
;
68
public
:
70
LoadBinAssignment
(
int
m
,
const
Gecode::IntSet
& d_m,
71
int
n
,
const
Gecode::IntSet
& d_n,
72
int
l)
73
:
Assignment
(m+n,d_m),
74
n_bins
(m),
n_items
(n),
d_load
(d_m),
d_bin
(d_n),
load
(l),
75
dsv
(new Gecode::IntSetValues[static_cast<unsigned int>(m+n)]) {
76
for
(
int
i
=
n_bins
;
i
--; )
77
dsv
[
i
].init(
d_load
);
78
for
(
int
i
=
n_items
;
i
--; )
79
dsv
[
n_bins
+
i
].init(
d_bin
);
80
}
82
virtual
bool
operator()
(
void
)
const
{
83
return
dsv
[0]();
84
}
86
virtual
void
operator++
(
void
) {
87
// Try to generate next bin assignment
88
{
89
int
i
=
n_items
-1;
90
while
(i >= 0) {
91
++
dsv
[
n_bins
+
i
];
92
if
(
dsv
[
n_bins
+i]())
93
return
;
94
dsv
[
n_bins
+(i--)].init(
d_bin
);
95
}
96
}
97
// Try to generate next load assignment
98
{
99
retry:
100
int
i
=
n_bins
-1;
101
while
(
true
) {
102
++
dsv
[
i
];
103
if
(
dsv
[i]() || (i == 0)) {
104
if
(
dsv
[i]() && (
load
>= 0)) {
105
int
l = 0;
106
for
(
int
k=0;k<
n_bins
; k++)
107
l +=
dsv
[k].val();
108
if
(
load
!= l)
109
goto
retry;
110
}
111
return
;
112
}
113
dsv
[i--].
init
(
d_load
);
114
}
115
}
116
}
118
virtual
int
operator[]
(
int
i
)
const
{
119
assert((i>=0) && (i<
n_bins
+
n_items
));
120
return
dsv
[
i
].
val
();
121
}
123
virtual
~LoadBinAssignment
(
void
) {
124
delete
[]
dsv
;
125
}
126
};
127
129
class
BPT
:
public
Test
{
130
protected
:
132
int
m
;
134
Gecode::IntArgs
s
;
136
bool
valid
;
138
int
t
;
140
mutable
int
il
[4];
142
static
int
total
(
const
Gecode::IntArgs
&
s
) {
143
int
t
= 0;
144
for
(
int
i
=s.
size
();
i
--; )
145
t += s[
i
];
146
return
t
;
147
}
148
public
:
150
BPT
(
int
m0,
const
Gecode::IntArgs
& s0,
bool
v
=
true
)
151
:
Test
(
"BinPacking::"
+
str
(m0)+
"::"
+
str
(s0)+
"::"
+(
v
?
"+"
:
"-"
),
152
m0+s0.
size
(), 0, 100),
153
m
(m0),
s
(s0),
valid
(
v
),
t
(
total
(
s
)) {
154
testsearch
=
false
;
155
}
157
virtual
Assignment
*
assignment
(
void
)
const
{
158
// Compute plausible bin sizes
159
int
a
=
t
/
m
;
160
return
new
LoadBinAssignment
(
m
,
Gecode::IntSet
(a-1,a+2),
161
s
.
size
(),
Gecode::IntSet
(0,
m
-1),
162
valid
?
t
: -1);
163
}
165
virtual
bool
solution
(
const
Assignment
& x)
const
{
166
// Loads are from 0 to m-1, after that are items
167
// Check whether loads sum up to total size
168
int
l=0;
169
for
(
int
j=
m
; j--; )
170
l += x[j];
171
if
(l !=
t
)
172
return
false
;
173
// Compute whether items add up
174
for
(
int
j=
m
; j--; )
175
il
[j] = 0;
176
for
(
int
i
=
s
.
size
();
i
--; )
177
il
[x[
m
+
i
]] +=
s
[
i
];
178
for
(
int
j=
m
; j--; )
179
if
(
il
[j] != x[j])
180
return
false
;
181
return
true
;
182
}
184
virtual
void
post
(
Gecode::Space
& home,
Gecode::IntVarArray
& x) {
185
using namespace
Gecode;
186
IntVarArgs
l(
m
);
187
IntVarArgs
b
(
s
.
size
());
188
for
(
int
j=
m
; j--; )
189
l[j]=x[j];
190
for
(
int
i
=
s
.
size
();
i
--; )
191
b
[
i
]=x[
m
+
i
];
192
binpacking
(home, l,
b
,
s
);
193
}
194
};
195
197
class
Create
{
198
public
:
200
Create
(
void
) {
201
using namespace
Gecode;
202
203
IntArgs
s1(3, 2,1,1);
204
IntArgs
s2(4, 1,2,3,4);
205
IntArgs
s3(4, 4,3,2,1);
206
IntArgs
s4(4, 1,2,4,8);
207
IntArgs
s5(4, 1,1,1,1);
208
IntArgs
s6(4, 1,1,2,2);
209
IntArgs
s7(4, 1,3,3,4);
210
IntArgs
s8(6, 1,2,4,8,16,32);
211
212
for
(
int
m
=1;
m
<4;
m
++) {
213
(void)
new
BPT
(
m
, s1);
214
(void)
new
BPT
(
m
, s2);
215
(void)
new
BPT
(
m
, s3);
216
(void)
new
BPT
(
m
, s4);
217
(void)
new
BPT
(
m
, s5);
218
(void)
new
BPT
(
m
, s6);
219
(void)
new
BPT
(
m
, s7);
220
(void)
new
BPT
(
m
, s8);
221
(void)
new
BPT
(
m
, s1,
false
);
222
}
223
224
}
225
};
226
227
Create
c
;
228
230
231
}
232
233
}}
234
235
236
// STATISTICS: test-int
237