weights.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Guido Tack <tack@gecode.org>
* Christian Schulte <schulte@gecode.org>
* Gabor Szokoli <szokoli@gecode.org>
*
* Copyright:
* Guido Tack, 2004
* Christian Schulte, 2004
* Gabor Szokoli, 2004
*
* 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/set.hh>
#include <gecode/int.hh>
namespace Gecode { namespace Set { namespace Int {
template<class I>
class OverweightValues {
private:
int threshold;
I iter;
SharedArray<int> elements;
SharedArray<int> weights;
int index;
void next(void);
public:
OverweightValues(void);
OverweightValues(int t,
SharedArray<int>& elements0,
SharedArray<int>& weights0,
I& i);
void init(int t,
SharedArray<int>& elements0,
SharedArray<int>& weights0,
I& i);
bool operator ()(void) const;
void operator ++(void);
int val(void) const;
};
template<class I>
forceinline void
OverweightValues<I>::next(void) {
while (iter()) {
while (elements[index]<iter.val()) index++;
assert(elements[index]==iter.val());
if (weights[index] > threshold) {
return;
}
++iter;
}
}
template<class I>
forceinline
OverweightValues<I>::OverweightValues(void) {}
template<class I>
forceinline
OverweightValues<I>::OverweightValues(int t,
SharedArray<int>& elements0,
SharedArray<int>& weights0,
I& i) : threshold(t),
iter(i),
elements(elements0),
weights(weights0),
index(0) {
next();
}
template<class I>
forceinline void
OverweightValues<I>::init(int t,
SharedArray<int>& elements0,
SharedArray<int>& weights0,
I& i) {
threshold = t; iter = i;
elements = elements0; weights = weights0;
index = 0;
next();
}
template<class I>
forceinline bool
OverweightValues<I>::operator ()(void) const { return iter(); }
template<class I>
forceinline void
OverweightValues<I>::operator ++(void) { ++iter; next(); }
template<class I>
forceinline int
OverweightValues<I>::val(void) const { return elements[index]; }
template<class View>
forceinline
Weights<View>::Weights(Home home,
const SharedArray<int>& elements0,
const SharedArray<int>& weights0,
View x0, Gecode::Int::IntView y0)
: Propagator(home), elements(elements0), weights(weights0),
x(x0), y(y0) {
home.notice(*this,AP_DISPOSE);
x.subscribe(home,*this, PC_SET_ANY);
y.subscribe(home,*this, Gecode::Int::PC_INT_BND);
}
template<class View>
forceinline
Weights<View>::Weights(Space& home, Weights& p)
: Propagator(home,p), elements(p.elements), weights(p.weights) {
x.update(home,p.x);
y.update(home,p.y);
}
template<class View>
inline ExecStatus
Weights<View>::post(Home home, const SharedArray<int>& elements,
const SharedArray<int>& weights,
View x, Gecode::Int::IntView y) {
if (elements.size() != weights.size())
throw ArgumentSizeMismatch("Weights");
Region r;
int* els_arr = r.alloc<int>(elements.size());
for (int i=elements.size(); i--;)
els_arr[i] = elements[i];
IntSet els(els_arr, elements.size());
IntSetRanges er(els);
GECODE_ME_CHECK(x.intersectI(home, er));
(void) new (home) Weights(home,elements,weights,x,y);
return ES_OK;
}
template<class View>
PropCost
Weights<View>::cost(const Space&, const ModEventDelta&) const {
return PropCost::linear(PropCost::LO, y.size()+1);
}
template<class View>
void
Weights<View>::reschedule(Space& home) {
x.reschedule(home,*this, PC_SET_ANY);
y.reschedule(home,*this, Gecode::Int::PC_INT_BND);
}
template<class View>
forceinline size_t
Weights<View>::dispose(Space& home) {
home.ignore(*this,AP_DISPOSE);
x.cancel(home,*this, PC_SET_ANY);
y.cancel(home,*this, Gecode::Int::PC_INT_BND);
elements.~SharedArray();
weights.~SharedArray();
(void) Propagator::dispose(home);
return sizeof(*this);
}
template<class View>
Actor*
Weights<View>::copy(Space& home) {
return new (home) Weights(home,*this);
}
template<class I>
forceinline
int weightI(SharedArray<int>& elements,
SharedArray<int>& weights,
I& iter) {
int sum = 0;
int i = 0;
Iter::Ranges::ToValues<I> v(iter);
for (; v(); ++v) {
// Skip all elements below the current
while (elements[i]<v.val()) i++;
assert(elements[i] == v.val());
sum += weights[i];
}
assert(!v());
return sum;
}
class IntLess {
public:
bool operator ()(int x, int y);
};
forceinline bool
IntLess::operator ()(int x, int y) {
return x < y;
}
template<class View>
ExecStatus
Weights<View>::propagate(Space& home, const ModEventDelta&) {
ModEvent me = ME_SET_NONE;
if (!x.assigned()) {
// Collect the weights of the elements in the unknown set in an array
int size = elements.size();
Region r;
int* minWeights = r.alloc<int>(size);
int* maxWeights = r.alloc<int>(size);
UnknownRanges<View> ur(x);
Iter::Ranges::ToValues<UnknownRanges<View> > urv(ur);
for (int i=0; i<size; i++) {
if (!urv() || elements[i]<urv.val()) {
minWeights[i] = INT_MAX;
maxWeights[i] = INT_MIN;
} else {
assert(elements[i] == urv.val());
minWeights[i] = weights[i];
maxWeights[i] = weights[i];
++urv;
}
}
// Sort the weights of the unknown elements
IntLess il;
Support::quicksort<int>(minWeights, size, il);
Support::quicksort<int>(maxWeights, size, il);
// The maximum number of elements that can still be added to x
int delta = static_cast<int>(std::min(x.unknownSize(), x.cardMax() - x.glbSize()));
// The weight of the elements already in x
GlbRanges<View> glb(x);
int glbWeight = weightI<GlbRanges<View> >(elements, weights, glb);
// Compute the weight of the current lower bound of x, plus at most
// delta-1 further elements with smallest negative weights. This weight
// determines which elements in the upper bound cannot possibly be
// added to x (those whose weight would exceed the capacity even if
// all other elements are minimal)
int lowWeight = glbWeight;
for (int i=0; i<delta-1; i++) {
if (minWeights[i] >= 0)
break;
lowWeight+=minWeights[i];
}
// Compute the lowest possible weight of x. If there is another element
// with negative weight left, then add its weight to lowWeight.
// Otherwise lowWeight is already the lowest possible weight.
int lowestWeight = lowWeight;
if (delta>0 && minWeights[delta-1]<0)
lowestWeight+=minWeights[delta-1];
// If after including the minimal number of required elements,
// no more element with negative weight is available, then
// a tighter lower bound can be computed.
if ( (x.cardMin() - x.glbSize() > 0 &&
minWeights[x.cardMin() - x.glbSize() - 1] >= 0) ||
minWeights[0] >= 0 ) {
int lowestPosWeight = glbWeight;
for (unsigned int i=0; i<x.cardMin() - x.glbSize(); i++) {
lowestPosWeight += minWeights[i];
}
lowestWeight = std::max(lowestWeight, lowestPosWeight);
}
// Compute the highest possible weight of x as the weight of the lower
// bound plus the weight of the delta heaviest elements still in the
// upper bound.
int highestWeight = glbWeight;
for (int i=0; i<delta; i++) {
if (maxWeights[size-i-1]<=0)
break;
highestWeight += maxWeights[size-i-1];
}
// Prune the weight using the computed bounds
GECODE_ME_CHECK(y.gq(home, lowestWeight));
GECODE_ME_CHECK(y.lq(home, highestWeight));
// Exclude all elements that are too heavy from the set x.
// Elements are too heavy if their weight alone already
// exceeds the remaining capacity
int remainingCapacity = y.max()-lowWeight;
UnknownRanges<View> ur2(x);
Iter::Ranges::ToValues<UnknownRanges<View> > urv2(ur2);
OverweightValues<Iter::Ranges::ToValues<UnknownRanges<View> > >
ov(remainingCapacity, elements, weights, urv2);
Iter::Values::ToRanges<OverweightValues<
Iter::Ranges::ToValues<UnknownRanges<View> > > > ovr(ov);
me = x.excludeI(home, ovr);
GECODE_ME_CHECK(me);
}
if (x.assigned()) {
// If x is assigned, just compute its weight and assign y.
GlbRanges<View> glb(x);
int w =
weightI<GlbRanges<View> >(elements, weights, glb);
GECODE_ME_CHECK(y.eq(home, w));
return home.ES_SUBSUMED(*this);
}
// return me_modified(me) ? ES_NOFIX : ES_FIX;
return ES_NOFIX;
}
}}}
// STATISTICS: set-prop
Gecode::Actor
Base-class for both propagators and branchers.
Definition core.hpp:628
Gecode::Actor::dispose
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3252
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Home::notice
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3219
Gecode::IntSetRanges
Range iterator for integer sets.
Definition int.hh:292
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::Int::ArgumentSizeMismatch
Exception: Arguments are of different size
Definition exception.hpp:73
Gecode::Int::IntView
Integer view for integer variables.
Definition view.hpp:129
Gecode::Iter::Ranges::ToValues
Value iterator from range iterator.
Definition ranges-values.hpp:42
Gecode::Iter::Ranges::ToValues::val
int val(void) const
Return current value.
Definition ranges-values.hpp:129
Gecode::Iter::Values::ToRanges
Range iterator from value iterator.
Definition values-ranges.hpp:46
Gecode::PropCost
Propagation cost.
Definition core.hpp:486
Gecode::PropCost::linear
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:4796
Gecode::PropCost::LO
@ LO
Cheap.
Definition core.hpp:513
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::Propagator
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3498
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Set::GlbRanges
Range iterator for the greatest lower bound.
Definition var-imp.hpp:359
Gecode::Set::Int::IntLess
Sort order for integers.
Definition weights.hpp:235
Gecode::Set::Int::IntLess::operator()
bool operator()(int x, int y)
Definition weights.hpp:241
Gecode::Set::Int::OverweightValues
Value Iterator for values above a certain weight.
Definition weights.hpp:45
Gecode::Set::Int::OverweightValues::operator++
void operator++(void)
Move iterator to next value (if possible).
Definition weights.hpp:138
Gecode::Set::Int::OverweightValues::init
void init(int t, SharedArray< int > &elements0, SharedArray< int > &weights0, I &i)
Initialize with elements/weights pairs, threshold t and iterator i.
Definition weights.hpp:122
Gecode::Set::Int::OverweightValues::operator()
bool operator()(void) const
Test whether iterator is still at a value or done.
Definition weights.hpp:134
Gecode::Set::Int::OverweightValues::val
int val(void) const
Return current value.
Definition weights.hpp:142
Gecode::Set::Int::OverweightValues::OverweightValues
OverweightValues(void)
Default constructor.
Definition weights.hpp:105
Gecode::Set::Int::Weights::y
Gecode::Int::IntView y
The integer view.
Definition int.hh:267
Gecode::Set::Int::Weights::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition weights.hpp:247
Gecode::Set::Int::Weights::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition weights.hpp:210
Gecode::Set::Int::Weights::weights
SharedArray< int > weights
Weights for the elements in the upper bound.
Definition int.hh:262
Gecode::Set::Int::Weights::x
View x
The set view.
Definition int.hh:265
Gecode::Set::Int::Weights::Weights
Weights(Space &home, Weights &p)
Constructor for cloning p.
Definition weights.hpp:159
Gecode::Set::Int::Weights::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as PC_LINEAR_LO).
Definition weights.hpp:185
Gecode::Set::Int::Weights::post
static ExecStatus post(Home home, const SharedArray< int > &elements, const SharedArray< int > &weights, View x, Gecode::Int::IntView y)
Post propagator for .
Definition weights.hpp:167
Gecode::Set::Int::Weights::elements
SharedArray< int > elements
List of elements in the upper bound.
Definition int.hh:260
Gecode::Set::Int::Weights::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition weights.hpp:198
Gecode::Set::Int::Weights::reschedule
virtual void reschedule(Space &home)
Schedule function.
Definition weights.hpp:191
Gecode::Set::UnknownRanges
Range iterator for the unknown set.
Definition var-imp.hpp:402
Gecode::SharedArray
Shared array with arbitrary number of elements.
Definition shared-array.hpp:53
Gecode::View
int.hh
set.hh
Gecode::Space::ES_SUBSUMED
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
Gecode::Space::ignore
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4074
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::AP_DISPOSE
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:562
Gecode::weights
void weights(Home home, IntSharedArray elements, IntSharedArray weights, SetVar x, IntVar y)
Post propagator for .
Definition int.cpp:292
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::Set::Int
Propagators connecting set and int variables.
Definition int.cpp:105
Gecode::Set::Int::weightI
int weightI(SharedArray< int > &elements, SharedArray< int > &weights, I &iter)
Compute the weight of the elements in the iterator I.
Definition weights.hpp:217
Gecode::Set
Finite integer sets.
Definition var-imp.hpp:137
Gecode::Set::ME_SET_NONE
const Gecode::ModEvent ME_SET_NONE
Domain operation has not changed domain.
Definition var-type.hpp:140
Gecode::Set::PC_SET_ANY
const Gecode::PropCond PC_SET_ANY
Propagate when any bound or the cardinality of a view changes.
Definition var-type.hpp:248
Gecode::Support::quicksort
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode
Gecode toplevel namespace
Gecode::sum
LinIntExpr sum(const IntVarArgs &x)
Construct linear expression as sum of integer variables.
Definition int-expr.cpp:880
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition core.hpp:476
Gecode::ES_NOFIX
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
Gecode::ModEvent
int ModEvent
Type for modification events.
Definition core.hpp:62
forceinline
#define forceinline
Definition config.hpp:187