71 dsv(new
Gecode::IntSetValues[static_cast<unsigned int>(m+
n)]) {
99 if (
dsv[i]() || (i == 0)) {
102 for (
int k=0;k<
n_bins; k++)
140 for (
int i=
s.size(); i--; )
147 :
Test(
"BinPacking::"+
str(m0)+
"::"+
str(s0)+
"::"+(v ?
"+" :
"-"),
148 m0+s0.size(), 0, 100),
171 if ((x[
m+j] < 0) || (x[
m+j] >=
m))
176 for (
int i=
s.size(); i--; )
190 for (
int i=
s.size(); i--; )
208 mutable int il[4][8];
213 :
Test(
"MultiBinPacking::"+
str(d0)+
"::"+
str(m0)+
"::"+
214 str(s0)+
"::"+
str(c0), s0.size() / d0, 0, m0-1),
215 d(d0),
m(m0),
s(s0),
c(c0) {
226 for (
int i=x.
size(); i--; )
227 il[k][x[i]] +=
s[i*
d+k];
238 for (
int j=
m*
d; j--; )
285 for (
int i=
clique.size()-1; i--; )
288 for (
int i=
clique.size(); i--; )
298 if (
static_cast<unsigned int>(
clique.size()) != mc.
size()) {
302 for (
int i=
clique.size(); i--; )
325 const bool expected_failed[4])
const {
329 for (
unsigned int i = 0; i < 4; i += 1) {
336 if (failed != expected_failed[i])
344 :
Base(
"Int::BinPacking::PropagationLevels") {}
348 bool const advanced_failed[] = {
false,
true,
true,
true};
349 bool const full_failed[] = {
false,
false,
false,
true};
353 IntArgs({32,30,24,21,19,11,10,9,8,5,3}),
364 :
Test(
"BinPacking::DFFLargeWeights::"+
str(n)+
"::"+
str(w),
365 n,0,1), capacity(
c), weight(w) {}
367 long long loads[2] = {0,0};
368 for (
int i=0; i<x.
size(); i++)
369 loads[x[i]] += weight;
370 return (loads[0] <= capacity) && (loads[1] <= capacity);
375 for (
int i=0; i<x.
size(); i++)
400 for (
int m=1; m<4; m++) {
401 (void)
new BPT(m, s0);
402 (void)
new BPT(m, s1);
403 (void)
new BPT(m, s2);
404 (void)
new BPT(m, s3);
405 (void)
new BPT(m, s4);
406 (void)
new BPT(m, s5);
407 (void)
new BPT(m, s6);
408 (void)
new BPT(m, s7);
409 (void)
new BPT(m, s8);
410 (void)
new BPT(m, s9);
411 (void)
new BPT(m, s1,
false);
416 IntArgs s1({1,2, 2,1, 1,2, 2,1});
418 (void)
new MBPT(2, 4, s1, c1);
419 (void)
new MBPT(2, 6, s1, c1);
423 (void)
new MBPT(2, 6, s2, c21);
424 (void)
new MBPT(2, 6, s2, c22);
425 IntArgs s3({1,2,3, 3,2,1, 2,1,3, 1,3,2});
429 (void)
new MBPT(3, 4, s3, c31);
430 (void)
new MBPT(3, 4, s3, c32);
431 (void)
new MBPT(3, 4, s3, c33);
432 (void)
new MBPT(3, 5, s3, c31);
433 (void)
new MBPT(3, 5, s3, c32);
434 (void)
new MBPT(3, 5, s3, c33);
440 IntArgs c3({1,3,7,10,15,22,27,97});
441 IntArgs c41({1,2,3,4,5,6,7,14});
442 IntArgs c42({1,2,3,4,5,6,7,15});
443 IntArgs c43({1,2,3,4,5,6,7,16});
444 IntArgs c44({1,2,3,4,5,6,7,30});
445 IntArgs c45({1,2,3,4,5,6,7,31});
446 IntArgs c46({1,2,3,4,5,6,7,32});
447 IntArgs c47({1,2,3,4,5,6,7,62});
448 IntArgs c48({1,2,3,4,5,6,7,63});
449 IntArgs c49({1,2,3,4,5,6,7,64});
int size(void) const
Return size of array (number of elements).
Passing integer arguments.
Value iterator for integer sets.
bool in(int n) const
Return whether n is included in the set.
unsigned int size(void) const
Return size (cardinality) of set.
Passing integer variables.
int size(void) const
Return size of array (number of elements).
Gecode::Support::RandomGenerator _rand
Random number generator.
Base(std::string s)
Create and register a standard test with name s.
static std::string str(bool b)
Map bool to string.
Base class for assignments
int n
Number of variables.
Assignment(int n0, const Gecode::IntSet &d0)
Initialize assignments for n0 variables and values d0.
int size(void) const
Return number of variables.
Test with different bin loads and items
static int total(const Gecode::IntArgs &s)
Compute total size.
virtual Assignment * assignment(void) const
Create assignment.
virtual bool solution(const Assignment &x) const
Test whether x is solution
BPT(int m0, const Gecode::IntArgs &s0, bool v=true)
Create and register test for m bins and item sizes s.
Gecode::IntArgs s
Item sizes.
int il[8]
Array of sufficient size for computing item loads.
bool valid
Whether to generate only valid loads.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
virtual Gecode::Space * copy(void)
Copying member function.
Test for testing the max-clique finding for multi bin-packing.
int n_items
Number of items.
CliqueMBPT(const Gecode::IntArgs &c)
Test for number of items n expected clique c.
Gecode::IntArgs clique
Expected clique.
virtual bool run(void)
Run the actual test.
Help class to create and register tests.
Create(void)
Perform creation and registration.
Large weights must preserve every feasible bin assignment.
virtual bool solution(const Assignment &x) const
Check for solution.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint.
DFFLargeWeights(int n, int c, int w)
Generate load and bin assignments.
virtual ~LoadBinAssignment(void)
Destructor.
Gecode::IntSet d_bin
Domain for bin variables.
Gecode::IntSetValues * dsv
Iterator for each variable.
LoadBinAssignment(int m, const Gecode::IntSet &d_m, int n, const Gecode::IntSet &d_n, int l)
Initialize assignments for load and bin variables.
int load
Load to generate (unless -1).
int n_bins
Number of bins.
virtual bool has_more(void) const
Test whether all assignments have been iterated.
Gecode::IntSet d_load
Domain for load variables.
int n_items
Number of items.
virtual int operator[](int i) const
Return value for variable i.
virtual void next(Gecode::Support::RandomGenerator &)
Move to next assignment.
Test with different bin loads and items
MBPT(int d0, int m0, const Gecode::IntArgs &s0, const Gecode::IntArgs &c0)
Create and register test for d0 dimensions, m0 bins, item sizes s0, and capacities c0.
virtual bool solution(const Assignment &x) const
Test whether x is solution
Gecode::IntArgs c
Bin capacities.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Gecode::IntArgs s
Item sizes.
int il[4][8]
Array of sufficient size for computing item loads.
virtual Gecode::Space * copy(void)
Copying member function.
Test the bin-packing propagation levels.
bool check_case(int n_bins, int capacity, const Gecode::IntArgs &sizes, const bool expected_failed[4]) const
Check one propagation-level test case.
PropagationLevels(void)
Constructor.
virtual bool run(void)
Run the actual test.
bool testsearch
Whether to perform search test.
static std::string str(bool b)
Map bool to string.
bool testfix
Whether to perform fixpoint test.
const int capacity[n_warehouses]
Capacity of a single warehouse.
LinearCongruentialGenerator< 2147483647, 48271, 44488, 3399 > RandomGenerator
Default values for linear congruential generator.
void binpacking(Home home, const IntVarArgs &l, const IntVarArgs &b, const IntArgs &s, IntPropLevel ipl=IPL_DEF)
Post propagator for bin packing.
IntPropLevel
Propagation levels for integer propagators.
@ IPL_BASIC
Use basic propagation algorithm.
@ IPL_FULL
Use full propagation.
@ IPL_ADVANCED
Use advanced propagation algorithm.
@ IPL_DEF
Simple propagation levels.
SpaceStatus status(StatusStatistics &stat)
Query space status.
@ SS_FAILED
Space is failed
const int max
Largest allowed integer value.
Gecode toplevel namespace
Tests for bin-packing constraint
Testing finite domain integers.