bin-packing.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2010
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include "test/int.hh"
#include <gecode/minimodel.hh>
#include <climits>
namespace Test { namespace Int {
namespace BinPacking {
class LoadBinAssignment : public Assignment {
protected:
int n_bins;
int n_items;
Gecode::IntSet d_load;
Gecode::IntSet d_bin;
int load;
Gecode::IntSetValues* dsv;
public:
LoadBinAssignment(int m, const Gecode::IntSet& d_m,
int n, const Gecode::IntSet& d_n,
int l)
: Assignment(m+n,d_m),
n_bins(m), n_items(n), d_load(d_m), d_bin(d_n), load(l),
dsv(new Gecode::IntSetValues[static_cast<unsigned int>(m+n)]) {
for (int i=n_bins; i--; )
dsv[i].init(d_load);
for (int i=n_items; i--; )
dsv[n_bins+i].init(d_bin);
}
virtual bool operator()(void) const {
return dsv[0]();
}
virtual void operator++(void) {
// Try to generate next bin assignment
{
int i = n_items-1;
while (i >= 0) {
++dsv[n_bins+i];
if (dsv[n_bins+i]())
return;
dsv[n_bins+(i--)].init(d_bin);
}
}
// Try to generate next load assignment
{
retry:
int i = n_bins-1;
while (true) {
++dsv[i];
if (dsv[i]() || (i == 0)) {
if (dsv[i]() && (load >= 0)) {
int l = 0;
for (int k=0;k<n_bins; k++)
l += dsv[k].val();
if (load != l)
goto retry;
}
return;
}
dsv[i--].init(d_load);
}
}
}
virtual int operator[](int i) const {
assert((i>=0) && (i<n_bins+n_items));
return dsv[i].val();
}
virtual ~LoadBinAssignment(void) {
delete [] dsv;
}
};
class BPT : public Test {
protected:
int m;
Gecode::IntArgs s;
bool valid;
int t;
mutable int il[8];
static int total(const Gecode::IntArgs& s) {
int t = 0;
for (int i=s.size(); i--; )
t += s[i];
return t;
}
public:
BPT(int m0, const Gecode::IntArgs& s0, bool v=true)
: Test("BinPacking::"+str(m0)+"::"+str(s0)+"::"+(v ? "+" : "-"),
m0+s0.size(), 0, 100),
m(m0), s(s0), valid(v), t(total(s)) {
testsearch = false;
}
virtual Assignment* assignment(void) const {
// Compute plausible bin sizes
int a = t / m;
return new LoadBinAssignment(m,Gecode::IntSet(a-1,a+2),
s.size(),Gecode::IntSet(0,m-1),
valid ? t : -1);
}
virtual bool solution(const Assignment& x) const {
// Loads are from 0 to m-1, after that are items
// Check whether loads sum up to total size
int l=0;
for (int j=m; j--; )
l += x[j];
if (l != t)
return false;
// Check whether items are at possible bins
for (int j=m; j--; )
if ((x[m+j] < 0) || (x[m+j] >= m))
return false;
// Compute whether items add up
for (int j=m; j--; )
il[j] = 0;
for (int i=s.size(); i--; )
il[x[m+i]] += s[i];
for (int j=m; j--; )
if (il[j] != x[j])
return false;
return true;
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
using namespace Gecode;
IntVarArgs l(m);
IntVarArgs b(s.size());
for (int j=m; j--; )
l[j]=x[j];
for (int i=s.size(); i--; )
b[i]=x[m+i];
binpacking(home, l, b, s);
}
};
class MBPT : public Test {
protected:
int d;
int m;
Gecode::IntArgs s;
Gecode::IntArgs c;
mutable int il[4][8];
public:
MBPT(int d0, int m0,
const Gecode::IntArgs& s0, const Gecode::IntArgs& c0)
: Test("MultiBinPacking::"+str(d0)+"::"+str(m0)+"::"+
str(s0)+"::"+str(c0), s0.size() / d0, 0, m0-1),
d(d0), m(m0), s(s0), c(c0) {
testsearch = false;
testfix = false;
}
virtual bool solution(const Assignment& x) const {
// x are the bin variables
for (int k=d; k--; )
for (int j=m; j--; )
il[k][j] = 0;
for (int k=d; k--; )
for (int i=x.size(); i--; )
il[k][x[i]] += s[i*d+k];
for (int k=d; k--; )
for (int j=m; j--; )
if (il[k][j] > c[k])
return false;
return true;
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
using namespace Gecode;
IntVarArgs l(d*m);
for (int j=m*d; j--; )
l[j]=IntVar(home, 0, Gecode::Int::Limits::max);
binpacking(home, d, l, x, s, c);
}
};
class CliqueMBPT : public Base {
protected:
int n_items;
Gecode::IntArgs clique;
class TestSpace : public Gecode::Space {
public:
// Constructor
TestSpace(void) {}
// Copy function
virtual Gecode::Space* copy(void) {
return NULL;
}
};
public:
CliqueMBPT(const Gecode::IntArgs& c)
: Base("Int::MultiBinPacking::Clique::"+Test::str(c)), clique(c) {}
virtual bool run(void) {
using namespace Gecode;
TestSpace* home = new TestSpace;
/*
* Set up a multi-dimensional bin packing problems of dimension 2
* where the item sizes in one dimension are all one but for some
* random items and two in the other dimension if the item is
* included in the clique and where the capacity in both dimensions
* is 3.
*/
// Number of items
int n_items = clique[clique.size()-1] + 1;
// Capacity
IntArgs c({3,3});
// Item sizes
IntArgs s(2*n_items);
for (int i=2*n_items; i--; )
s[i]=1;
// Create some random conflicts
for (int i=clique.size()-1; i--; )
s[rand(n_items)*2+0]=2;
// Create conflicts corresponding to the clique
for (int i=clique.size(); i--; )
s[clique[i]*2+1]=2;
// Load and bin variables
IntVarArgs b(*home, n_items, 0, n_items-1);
IntVarArgs l(*home, 2*n_items, 0, 3);
IntSet mc = binpacking(*home, 2, l, b, s, c);
if (home->status() == SS_FAILED) {
delete home;
return false;
}
if (static_cast<unsigned int>(clique.size()) != mc.size()) {
delete home;
return false;
}
for (int i=clique.size(); i--; )
if (!mc.in(clique[i])) {
delete home;
return false;
}
delete home;
return true;
}
};
class Create {
public:
Create(void) {
using namespace Gecode;
{
IntArgs s0({0,0,0,0});
IntArgs s1({2,1,1});
IntArgs s2({1,2,3,4});
IntArgs s3({4,3,2,1});
IntArgs s4({1,2,4,8});
IntArgs s5({1,1,1,1});
IntArgs s6({1,1,2,2});
IntArgs s7({1,3,3,4});
IntArgs s8({1,3,3,0,4,0});
IntArgs s9({1,2,4,8,16,32});
for (int m=1; m<4; m++) {
(void) new BPT(m, s0);
(void) new BPT(m, s1);
(void) new BPT(m, s2);
(void) new BPT(m, s3);
(void) new BPT(m, s4);
(void) new BPT(m, s5);
(void) new BPT(m, s6);
(void) new BPT(m, s7);
(void) new BPT(m, s8);
(void) new BPT(m, s9);
(void) new BPT(m, s1, false);
}
}
{
IntArgs s1({1,2, 2,1, 1,2, 2,1});
IntArgs c1({3,3});
(void) new MBPT(2, 4, s1, c1);
(void) new MBPT(2, 6, s1, c1);
IntArgs s2({1,1, 1,1, 1,1});
IntArgs c21({1,1});
IntArgs c22({2,2});
(void) new MBPT(2, 6, s2, c21);
(void) new MBPT(2, 6, s2, c22);
IntArgs s3({1,2,3, 3,2,1, 2,1,3, 1,3,2});
IntArgs c31({3,3,3});
IntArgs c32({4,4,4});
IntArgs c33({6,6,6});
(void) new MBPT(3, 4, s3, c31);
(void) new MBPT(3, 4, s3, c32);
(void) new MBPT(3, 4, s3, c33);
(void) new MBPT(3, 5, s3, c31);
(void) new MBPT(3, 5, s3, c32);
(void) new MBPT(3, 5, s3, c33);
}
{
IntArgs c1({0,2,4,6});
IntArgs c2({1,2,3,4,5,6,7,8});
IntArgs c3({1,3,7,10,15,22,27,97});
IntArgs c41({1,2,3,4,5,6,7,14});
IntArgs c42({1,2,3,4,5,6,7,15});
IntArgs c43({1,2,3,4,5,6,7,16});
IntArgs c44({1,2,3,4,5,6,7,30});
IntArgs c45({1,2,3,4,5,6,7,31});
IntArgs c46({1,2,3,4,5,6,7,32});
IntArgs c47({1,2,3,4,5,6,7,62});
IntArgs c48({1,2,3,4,5,6,7,63});
IntArgs c49({1,2,3,4,5,6,7,64});
(void) new CliqueMBPT(c1);
(void) new CliqueMBPT(c2);
(void) new CliqueMBPT(c3);
(void) new CliqueMBPT(c41);
(void) new CliqueMBPT(c42);
(void) new CliqueMBPT(c43);
(void) new CliqueMBPT(c44);
(void) new CliqueMBPT(c45);
(void) new CliqueMBPT(c46);
(void) new CliqueMBPT(c47);
(void) new CliqueMBPT(c48);
(void) new CliqueMBPT(c49);
}
}
};
Create c;
}
}}
// STATISTICS: test-int
Gecode::IntArgs
Passing integer arguments.
Definition int.hh:628
Gecode::IntSetValues
Value iterator for integer sets.
Definition int.hh:333
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::IntSet::in
bool in(int n) const
Return whether n is included in the set.
Definition int-set-1.hpp:177
Gecode::IntSet::size
unsigned int size(void) const
Return size (cardinality) of set.
Definition int-set-1.hpp:198
Gecode::IntVarArgs
Passing integer variables.
Definition int.hh:656
Gecode::IntVarArray
Integer variable array.
Definition int.hh:763
Gecode::IntVar
Integer variables.
Definition int.hh:371
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Test::Base::rand
static Gecode::Support::RandomGenerator rand
Random number generator.
Definition test.hh:134
Test::Base::Base
Base(const std::string &s)
Create and register test with name s.
Definition test.cpp:59
Test::Int::Assignment
Base class for assignments
Definition int.hh:59
Test::Int::Assignment::n
int n
Number of variables.
Definition int.hh:61
Test::Int::Assignment::Assignment
Assignment(int n0, const Gecode::IntSet &d0)
Initialize assignments for n0 variables and values d0.
Definition int.hpp:43
Test::Int::Assignment::size
int size(void) const
Return number of variables.
Definition int.hpp:46
Test::Int::BinPacking::BPT
Test with different bin loads and items
Definition bin-packing.cpp:125
Test::Int::BinPacking::BPT::total
static int total(const Gecode::IntArgs &s)
Compute total size.
Definition bin-packing.cpp:138
Test::Int::BinPacking::BPT::assignment
virtual Assignment * assignment(void) const
Create assignment.
Definition bin-packing.cpp:153
Test::Int::BinPacking::BPT::solution
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition bin-packing.cpp:161
Test::Int::BinPacking::BPT::BPT
BPT(int m0, const Gecode::IntArgs &s0, bool v=true)
Create and register test for m bins and item sizes s.
Definition bin-packing.cpp:146
Test::Int::BinPacking::BPT::s
Gecode::IntArgs s
Item sizes.
Definition bin-packing.cpp:130
Test::Int::BinPacking::BPT::m
int m
Number of bins.
Definition bin-packing.cpp:128
Test::Int::BinPacking::BPT::il
int il[8]
Array of sufficient size for computing item loads.
Definition bin-packing.cpp:136
Test::Int::BinPacking::BPT::valid
bool valid
Whether to generate only valid loads.
Definition bin-packing.cpp:132
Test::Int::BinPacking::BPT::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition bin-packing.cpp:184
Test::Int::BinPacking::BPT::t
int t
Total item sizes.
Definition bin-packing.cpp:134
Test::Int::BinPacking::CliqueMBPT::TestSpace
Simple test space class.
Definition bin-packing.cpp:252
Test::Int::BinPacking::CliqueMBPT::TestSpace::copy
virtual Gecode::Space * copy(void)
Copying member function.
Definition bin-packing.cpp:257
Test::Int::BinPacking::CliqueMBPT::TestSpace::TestSpace
TestSpace(void)
Definition bin-packing.cpp:255
Test::Int::BinPacking::CliqueMBPT
Test for testing the max-clique finding for multi bin-packing.
Definition bin-packing.cpp:245
Test::Int::BinPacking::CliqueMBPT::n_items
int n_items
Number of items.
Definition bin-packing.cpp:248
Test::Int::BinPacking::CliqueMBPT::CliqueMBPT
CliqueMBPT(const Gecode::IntArgs &c)
Test for number of items n expected clique c.
Definition bin-packing.cpp:263
Test::Int::BinPacking::CliqueMBPT::clique
Gecode::IntArgs clique
Expected clique.
Definition bin-packing.cpp:250
Test::Int::BinPacking::CliqueMBPT::run
virtual bool run(void)
Run the actual test.
Definition bin-packing.cpp:266
Test::Int::BinPacking::Create
Help class to create and register tests.
Definition bin-packing.cpp:313
Test::Int::BinPacking::Create::Create
Create(void)
Perform creation and registration.
Definition bin-packing.cpp:316
Test::Int::BinPacking::LoadBinAssignment
Generate load and bin assignments.
Definition bin-packing.cpp:50
Test::Int::BinPacking::LoadBinAssignment::~LoadBinAssignment
virtual ~LoadBinAssignment(void)
Destructor.
Definition bin-packing.cpp:119
Test::Int::BinPacking::LoadBinAssignment::d_bin
Gecode::IntSet d_bin
Domain for bin variables.
Definition bin-packing.cpp:59
Test::Int::BinPacking::LoadBinAssignment::operator++
virtual void operator++(void)
Move to next assignment.
Definition bin-packing.cpp:82
Test::Int::BinPacking::LoadBinAssignment::dsv
Gecode::IntSetValues * dsv
Iterator for each variable.
Definition bin-packing.cpp:63
Test::Int::BinPacking::LoadBinAssignment::operator()
virtual bool operator()(void) const
Test whether all assignments have been iterated.
Definition bin-packing.cpp:78
Test::Int::BinPacking::LoadBinAssignment::LoadBinAssignment
LoadBinAssignment(int m, const Gecode::IntSet &d_m, int n, const Gecode::IntSet &d_n, int l)
Initialize assignments for load and bin variables.
Definition bin-packing.cpp:66
Test::Int::BinPacking::LoadBinAssignment::load
int load
Load to generate (unless -1).
Definition bin-packing.cpp:61
Test::Int::BinPacking::LoadBinAssignment::n_bins
int n_bins
Number of bins.
Definition bin-packing.cpp:53
Test::Int::BinPacking::LoadBinAssignment::d_load
Gecode::IntSet d_load
Domain for load variables.
Definition bin-packing.cpp:57
Test::Int::BinPacking::LoadBinAssignment::n_items
int n_items
Number of items.
Definition bin-packing.cpp:55
Test::Int::BinPacking::LoadBinAssignment::operator[]
virtual int operator[](int i) const
Return value for variable i.
Definition bin-packing.cpp:114
Test::Int::BinPacking::MBPT
Test with different bin loads and items
Definition bin-packing.cpp:197
Test::Int::BinPacking::MBPT::MBPT
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.
Definition bin-packing.cpp:211
Test::Int::BinPacking::MBPT::solution
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition bin-packing.cpp:220
Test::Int::BinPacking::MBPT::c
Gecode::IntArgs c
Bin capacities.
Definition bin-packing.cpp:206
Test::Int::BinPacking::MBPT::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition bin-packing.cpp:235
Test::Int::BinPacking::MBPT::s
Gecode::IntArgs s
Item sizes.
Definition bin-packing.cpp:204
Test::Int::BinPacking::MBPT::il
int il[4][8]
Array of sufficient size for computing item loads.
Definition bin-packing.cpp:208
Test::Int::BinPacking::MBPT::m
int m
Number of bins.
Definition bin-packing.cpp:202
Test::Int::BinPacking::MBPT::d
int d
Dimension.
Definition bin-packing.cpp:200
Test::Int::Test::testsearch
bool testsearch
Whether to perform search test.
Definition int.hh:238
Test::Int::Test::testfix
bool testfix
Whether to perform fixpoint test.
Definition int.hh:240
Test::Int::Test::str
static std::string str(Gecode::IntPropLevel ipl)
Map integer propagation level to string.
Definition int.hpp:209
Gecode::binpacking
void binpacking(Home home, const IntVarArgs &l, const IntVarArgs &b, const IntArgs &s, IntPropLevel ipl=IPL_DEF)
Post propagator for bin packing.
Definition bin-packing.cpp:41
Gecode::Space::status
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition core.cpp:252
Gecode::SS_FAILED
@ SS_FAILED
Space is failed
Definition core.hpp:1682
minimodel.hh
Gecode::Int::Limits::max
const int max
Largest allowed integer value.
Definition int.hh:116
Gecode
Gecode toplevel namespace
Test::Int::BinPacking
Tests for bin-packing constraint
Definition bin-packing.cpp:42
Test::Int::BinPacking::c
Create c
Definition bin-packing.cpp:398
Test::Int
Testing finite domain integers.
Definition int.cpp:40
Test
General test support.
Definition afc.cpp:39
int.hh