propagate.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 <gecode/int/bin-packing.hh>
namespace Gecode { namespace Int { namespace BinPacking {
/*
* Packing propagator
*
*/
PropCost
Pack::cost(const Space&, const ModEventDelta&) const {
return PropCost::quadratic(PropCost::HI,bs.size());
}
void
Pack::reschedule(Space& home) {
l.reschedule(home,*this,PC_INT_BND);
bs.reschedule(home,*this,PC_INT_DOM);
}
Actor*
Pack::copy(Space& home) {
return new (home) Pack(home,*this);
}
class TellCache {
protected:
int* _nq;
int _n_nq;
int _eq;
public:
TellCache(Region& region, int m);
void nq(int j);
void eq(int j);
ExecStatus tell(Space& home, IntView x);
};
forceinline
TellCache::TellCache(Region& region, int m)
: _nq(region.alloc<int>(m)), _n_nq(0), _eq(-1) {}
forceinline void
TellCache::nq(int j) {
_nq[_n_nq++] = j;
}
forceinline void
TellCache::eq(int j) {
// For eq: -1 mean not yet assigned, -2 means failure, positive means value
if (_eq == -1)
_eq = j;
else
_eq = -2;
}
ExecStatus
TellCache::tell(Space& home, IntView x) {
if (_eq == -2) {
return ES_FAILED;
} else if (_eq >= 0) {
GECODE_ME_CHECK(x.eq(home,_eq));
}
Iter::Values::Array nqi(_nq, _n_nq);
GECODE_ME_CHECK(x.minus_v(home, nqi));
_n_nq=0; _eq=-1;
return ES_OK;
}
/*
* Propagation proper
*
*/
ExecStatus
Pack::propagate(Space& home, const ModEventDelta& med) {
// Number of items
int n = bs.size();
// Number of bins
int m = l.size();
Region region;
{
// Possible sizes for bins
int* s = region.alloc<int>(m);
for (int j=0; j<m; j++)
s[j] = 0;
// Compute sizes for bins
if (OffsetView::me(med) == ME_INT_VAL) {
// Also eliminate assigned items
int k=0;
for (int i=0; i<n; i++)
if (bs[i].assigned()) {
int j = bs[i].bin().val();
l[j].offset(l[j].offset() - bs[i].size());
t -= bs[i].size();
} else {
for (ViewValues<IntView> j(bs[i].bin()); j(); ++j)
s[j.val()] += bs[i].size();
bs[k++] = bs[i];
}
n=k; bs.size(n);
} else {
for (int i=0; i<n; i++) {
assert(!bs[i].assigned());
for (ViewValues<IntView> j(bs[i].bin()); j(); ++j)
s[j.val()] += bs[i].size();
}
}
// Propagate bin loads and compute lower and upper bound
int min = t, max = t;
for (int j=0; j<m; j++) {
GECODE_ME_CHECK(l[j].gq(home,0));
GECODE_ME_CHECK(l[j].lq(home,s[j]));
min -= l[j].max(); max -= l[j].min();
}
// Propagate that load must be equal to total size
for (bool mod = true; mod; ) {
mod = false; ModEvent me;
for (int j=0; j<m; j++) {
int lj_min = l[j].min();
me = l[j].gq(home, min + l[j].max());
if (me_failed(me))
return ES_FAILED;
if (me_modified(me)) {
max += lj_min - l[j].min(); mod = true;
}
int lj_max = l[j].max();
me = l[j].lq(home, max + l[j].min());
if (me_failed(me))
return ES_FAILED;
if (me_modified(me)) {
min += lj_max - l[j].max(); mod = true;
}
}
}
if (n == 0) {
assert(l.assigned());
return home.ES_SUBSUMED(*this);
}
{
TellCache tc(region,m);
int k=0;
for (int i=0; i<n; i++) {
for (ViewValues<IntView> j(bs[i].bin()); j(); ++j) {
if (bs[i].size() > l[j.val()].max())
tc.nq(j.val());
if (s[j.val()] - bs[i].size() < l[j.val()].min())
tc.eq(j.val());
}
GECODE_ES_CHECK(tc.tell(home,bs[i].bin()));
// Eliminate assigned bin
if (bs[i].assigned()) {
int j = bs[i].bin().val();
l[j].offset(l[j].offset() - bs[i].size());
t -= bs[i].size();
} else {
bs[k++] = bs[i];
}
}
n=k; bs.size(n);
}
region.free();
}
// Only if the propagator is at fixpoint here, continue with the more
// expensive stage for propagation.
if (IntView::me(modeventdelta()) != ME_INT_NONE)
return ES_NOFIX;
// Now the invariant holds that no more assigned bins exist!
{
// Size of items
SizeSetMinusOne* s = region.alloc<SizeSetMinusOne>(m);
for (int j=0; j<m; j++)
s[j] = SizeSetMinusOne(region,n);
// Set up size information
for (int i=0; i<n; i++) {
assert(!bs[i].assigned());
for (ViewValues<IntView> j(bs[i].bin()); j(); ++j)
s[j.val()].add(bs[i].size());
}
for (int j=0; j<m; j++) {
// Can items still be packed into bin?
if (nosum(static_cast<SizeSet&>(s[j]), l[j].min(), l[j].max()))
return ES_FAILED;
int ap, bp;
// Must there be packed more items into bin?
if (nosum(static_cast<SizeSet&>(s[j]), l[j].min(), l[j].min(),
ap, bp))
GECODE_ME_CHECK(l[j].gq(home,bp));
// Must there be packed less items into bin?
if (nosum(static_cast<SizeSet&>(s[j]), l[j].max(), l[j].max(),
ap, bp))
GECODE_ME_CHECK(l[j].lq(home,ap));
}
TellCache tc(region,m);
int k=0;
for (int i=0; i<n; i++) {
assert(!bs[i].assigned());
for (ViewValues<IntView> j(bs[i].bin()); j(); ++j) {
// Items must be removed in decreasing size!
s[j.val()].minus(bs[i].size());
// Can item i still be packed into bin j?
if (nosum(s[j.val()],
l[j.val()].min() - bs[i].size(),
l[j.val()].max() - bs[i].size()))
tc.nq(j.val());
// Must item i be packed into bin j?
if (nosum(s[j.val()], l[j.val()].min(), l[j.val()].max()))
tc.eq(j.val());
}
GECODE_ES_CHECK(tc.tell(home,bs[i].bin()));
if (bs[i].assigned()) {
int j = bs[i].bin().val();
l[j].offset(l[j].offset() - bs[i].size());
t -= bs[i].size();
} else {
bs[k++] = bs[i];
}
}
n=k; bs.size(n);
region.free();
}
// Perform lower bound checking
if (n > 0) {
// Find capacity estimate (we start from bs[0] as it might be
// not packable, actually (will be detected later anyway)!
int c = bs[0].size();
for (int j=0; j<m; j++)
c = std::max(c,l[j].max());
// Count how many items have a certain size (bucket sort)
int* n_s = region.alloc<int>(c+1);
for (int i=0; i<c+1; i++)
n_s[i] = 0;
// Count unpacked items
for (int i=0; i<n; i++)
n_s[bs[i].size()]++;
// Number of items and remaining bin load
int nm = n;
// Only count positive remaining bin loads
for (int j=0; j<m; j++)
if (l[j].max() < 0) {
return ES_FAILED;
} else if (c > l[j].max()) {
n_s[c - l[j].max()]++; nm++;
}
// Sizes of items and remaining bin loads
int* s = region.alloc<int>(nm);
// Setup sorted sizes
{
int k=0;
for (int i=c+1; i--; )
for (int j=n_s[i]; j--; )
s[k++]=i;
assert(k == nm);
}
// Items in N1 are from 0 ... n1 - 1
int n1 = 0;
// Items in N2 are from n1 ... n12 - 1, we count elements in N1 and N2
int n12 = 0;
// Items in N3 are from n12 ... n3 - 1
int n3 = 0;
// Free space in N2
int f2 = 0;
// Total size of items in N3
int s3 = 0;
// Initialize n12 and f2
for (; (n12 < nm) && (s[n12] > c/2); n12++)
f2 += c - s[n12];
// Initialize n3 and s3
for (n3 = n12; n3 < nm; n3++)
s3 += s[n3];
// Compute lower bounds
for (int k=0; k<=c/2; k++) {
// Make N1 larger by adding elements and N2 smaller
for (; (n1 < nm) && (s[n1] > c-k); n1++)
f2 -= c - s[n1];
assert(n1 <= n12);
// Make N3 smaller by removing elements
for (; (s[n3-1] < k) && (n3 > n12); n3--)
s3 -= s[n3-1];
// Overspill
int o = (s3 > f2) ? ((s3 - f2 + c - 1) / c) : 0;
if (n12 + o > m)
return ES_FAILED;
}
region.free();
}
return ES_NOFIX;
}
ExecStatus
Pack::post(Home home, ViewArray<OffsetView>& l, ViewArray<Item>& bs) {
// Sort according to size
Support::quicksort(&bs[0], bs.size());
// Total size of items
int s = 0;
// Constrain bins
for (int i=0; i<bs.size(); i++) {
s += bs[i].size();
GECODE_ME_CHECK(bs[i].bin().gq(home,0));
GECODE_ME_CHECK(bs[i].bin().le(home,l.size()));
}
// Eliminate zero sized items (which are at the end as the size are sorted)
{
int n = bs.size();
while ((n > 0) && (bs[n-1].size() == 0))
n--;
bs.size(n);
}
if (bs.size() == 0) {
// No items to be packed
for (int i=0; i<l.size(); i++)
GECODE_ME_CHECK(l[i].eq(home,0));
return ES_OK;
} else if (l.size() == 0) {
// No bins available
return ES_FAILED;
} else {
// Constrain load
for (int j=0; j<l.size(); j++) {
GECODE_ME_CHECK(l[j].gq(home,0));
GECODE_ME_CHECK(l[j].lq(home,s));
}
(void) new (home) Pack(home,l,bs);
return ES_OK;
}
}
}}}
// STATISTICS: int-prop
bin-packing.hh
Gecode::Actor
Base-class for both propagators and branchers.
Definition core.hpp:628
Gecode::DerivedView< IntView >::me
static ModEvent me(const ModEventDelta &med)
Definition view.hpp:639
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Int::BinPacking::Pack::l
ViewArray< OffsetView > l
Views for load of bins.
Definition bin-packing.hh:144
Gecode::Int::BinPacking::Pack::post
static ExecStatus post(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Post propagator for loads l and items bs.
Definition propagate.cpp:360
Gecode::Int::BinPacking::Pack::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition propagate.cpp:113
Gecode::Int::BinPacking::Pack::bs
ViewArray< Item > bs
Items with bin and size.
Definition bin-packing.hh:146
Gecode::Int::BinPacking::Pack::Pack
Pack(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Constructor for posting.
Definition propagate.hpp:150
Gecode::Int::BinPacking::Pack::t
int t
Total size of all items.
Definition bin-packing.hh:148
Gecode::Int::BinPacking::Pack::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition propagate.cpp:55
Gecode::Int::BinPacking::Pack::nosum
bool nosum(const SizeSet &s, int a, int b, int &ap, int &bp)
Detect non-existence of sums in a .. b.
Definition propagate.hpp:175
Gecode::Int::BinPacking::Pack::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition propagate.cpp:44
Gecode::Int::BinPacking::Pack::reschedule
virtual void reschedule(Space &home)
Schedule function.
Definition propagate.cpp:49
Gecode::Int::BinPacking::SizeSetMinusOne
Size sets with one element discarded.
Definition bin-packing.hh:111
Gecode::Int::BinPacking::SizeSetMinusOne::minus
void minus(int s)
Discard size s.
Definition propagate.hpp:119
Gecode::Int::BinPacking::SizeSet
Size sets.
Definition bin-packing.hh:87
Gecode::Int::BinPacking::SizeSet::add
void add(int s)
Add new size s.
Definition propagate.hpp:97
Gecode::Int::BinPacking::TellCache
Record tell information.
Definition propagate.cpp:60
Gecode::Int::BinPacking::TellCache::_nq
int * _nq
Values (sorted) to be pruned from view.
Definition propagate.cpp:63
Gecode::Int::BinPacking::TellCache::_n_nq
int _n_nq
Number of values to be pruned.
Definition propagate.cpp:65
Gecode::Int::BinPacking::TellCache::TellCache
TellCache(Region &region, int m)
Initialize cache for at most m values.
Definition propagate.cpp:80
Gecode::Int::BinPacking::TellCache::tell
ExecStatus tell(Space &home, IntView x)
Perform tell to view x and reset cache.
Definition propagate.cpp:95
Gecode::Int::BinPacking::TellCache::eq
void eq(int j)
Record that view must be equal to j, return false if not possible.
Definition propagate.cpp:87
Gecode::Int::BinPacking::TellCache::_eq
int _eq
Value to which view should be assigned.
Definition propagate.cpp:67
Gecode::Int::BinPacking::TellCache::nq
void nq(int j)
Record that view must be different from j.
Definition propagate.cpp:83
Gecode::Int::IntView
Integer view for integer variables.
Definition view.hpp:129
Gecode::Int::IntView::minus_v
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition int.hpp:206
Gecode::Int::IntView::eq
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition int.hpp:166
Gecode::Int::ViewValues
Value iterator for integer views.
Definition view.hpp:94
Gecode::Iter::Values::Array
Value iterator for array of integers
Definition values-array.hpp:46
Gecode::PropCost::quadratic
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition core.hpp:4787
Gecode::PropCost::HI
@ HI
Expensive.
Definition core.hpp:514
Gecode::Propagator::size
size_t size
The size of the propagator (used during subsumption).
Definition core.hpp:1077
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Propagator::modeventdelta
ModEventDelta modeventdelta(void) const
Return the modification event delta.
Definition core.hpp:3520
Gecode::Propagator::med
ModEventDelta med
A set of modification events (used during propagation).
Definition core.hpp:1075
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Region::free
void free(void)
Free allocate memory.
Definition region.hpp:356
Gecode::Region::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition region.hpp:386
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::VarImpView< IntVar >::me
static ModEvent me(const ModEventDelta &med)
Definition view.hpp:552
Gecode::ViewArray
View arrays.
Definition array.hpp:253
Gecode::Int::OffsetView::offset
int offset(void) const
Integer-precision integer scale view.
Definition view.hpp:642
Gecode::Space::ES_SUBSUMED
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
Gecode::ModEventDelta
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
GECODE_ME_CHECK
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
Gecode::me_failed
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
GECODE_ES_CHECK
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
Gecode::me_modified
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition modevent.hpp:59
Gecode::Int::BinPacking
Bin-packing propagators
Gecode::Int
Finite domain integers.
Gecode::Int::PC_INT_BND
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:91
Gecode::Int::PC_INT_DOM
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
Gecode::Int::ME_INT_VAL
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable).
Definition var-type.hpp:56
Gecode::Int::ME_INT_NONE
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition var-type.hpp:54
Gecode::Support::quicksort
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode
Gecode toplevel namespace
Gecode::mod
void mod(Home home, IntVar x0, IntVar x1, IntVar x2, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition arithmetic.cpp:360
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:67
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition core.hpp:476
Gecode::ES_FAILED
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
Gecode::ES_NOFIX
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:49
Gecode::ModEvent
int ModEvent
Type for modification events.
Definition core.hpp:62
forceinline
#define forceinline
Definition config.hpp:187