nary.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
* Vincent Barichard <Vincent.Barichard@univ-angers.fr>
*
* Copyright:
* Christian Schulte, 2003
* Vincent Barichard, 2012
*
* 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.
*
*/
namespace Gecode { namespace Float { namespace Linear {
/*
* Linear propagators
*
*/
template<class P, class N, PropCond pc>
forceinline
Lin<P,N,pc>::Lin(Home home, ViewArray<P>& x0, ViewArray<N>& y0, FloatVal c0)
: Propagator(home), x(x0), y(y0), c(c0) {
x.subscribe(home,*this,pc);
y.subscribe(home,*this,pc);
}
template<class P, class N, PropCond pc>
forceinline
Lin<P,N,pc>::Lin(Space& home, Lin<P,N,pc>& p)
: Propagator(home,p), c(p.c) {
x.update(home,p.x);
y.update(home,p.y);
}
template<class P, class N, PropCond pc>
PropCost
Lin<P,N,pc>::cost(const Space&, const ModEventDelta&) const {
return PropCost::linear(PropCost::LO, x.size()+y.size());
}
template<class P, class N, PropCond pc>
void
Lin<P,N,pc>::reschedule(Space& home) {
x.reschedule(home,*this,pc);
y.reschedule(home,*this,pc);
}
template<class P, class N, PropCond pc>
forceinline size_t
Lin<P,N,pc>::dispose(Space& home) {
x.cancel(home,*this,pc);
y.cancel(home,*this,pc);
(void) Propagator::dispose(home);
return sizeof(*this);
}
template<class View>
void
eliminate_p(ModEventDelta med, ViewArray<View>& x, FloatVal& c) {
int n = x.size();
if (FloatView::me(med) == ME_FLOAT_VAL) {
for (int i = n; i--; ) {
if (x[i].assigned()) {
c -= x[i].val(); x[i] = x[--n];
}
}
x.size(n);
}
}
template<class View>
void
eliminate_n(ModEventDelta med, ViewArray<View>& y, FloatVal& c) {
int n = y.size();
if (FloatView::me(med) == ME_FLOAT_VAL) {
for (int i = n; i--; ) {
if (y[i].assigned()) {
c += y[i].val(); y[i] = y[--n];
}
}
y.size(n);
}
}
forceinline bool
infty(const FloatNum& n) {
return ((n == std::numeric_limits<FloatNum>::infinity()) ||
(n == -std::numeric_limits<FloatNum>::infinity()));
}
/*
* Bound consistent linear equation
*
*/
template<class P, class N>
forceinline
Eq<P,N>::Eq(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c)
: Lin<P,N,PC_FLOAT_BND>(home,x,y,c) {}
template<class P, class N>
ExecStatus
Eq<P,N>::post(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c) {
(void) new (home) Eq<P,N>(home,x,y,c);
return ES_OK;
}
template<class P, class N>
forceinline
Eq<P,N>::Eq(Space& home, Eq<P,N>& p)
: Lin<P,N,PC_FLOAT_BND>(home,p) {}
template<class P, class N>
Actor*
Eq<P,N>::copy(Space& home) {
return new (home) Eq<P,N>(home,*this);
}
template<class P, class N>
ExecStatus
Eq<P,N>::propagate(Space& home, const ModEventDelta& med) {
// Eliminate singletons
Rounding r;
eliminate_p<P>(med, x, c);
eliminate_n<N>(med, y, c);
if ((FloatView::me(med) == ME_FLOAT_VAL) && ((x.size() + y.size()) <= 1)) {
if (x.size() == 1) {
GECODE_ME_CHECK(x[0].eq(home,c));
return home.ES_SUBSUMED(*this);
}
if (y.size() == 1) {
GECODE_ME_CHECK(y[0].eq(home,-c));
return home.ES_SUBSUMED(*this);
}
return (c.in(0.0)) ? home.ES_SUBSUMED(*this) : ES_FAILED;
}
ExecStatus es = ES_FIX;
bool assigned = true;
// Propagate max bound for positive variables
for (int i = x.size(); i--; ) {
// Compute bound
FloatNum sl = c.max();
for (int j = x.size(); j--; ) {
if (i == j) continue;
sl = r.sub_up(sl,x[j].min());
}
for (int j = y.size(); j--; )
sl = r.add_up(sl,y[j].max());
ModEvent me = x[i].lq(home,sl);
if (me_failed(me))
return ES_FAILED;
if (me != ME_FLOAT_VAL)
assigned = false;
if (me_modified(me))
es = ES_NOFIX;
}
// Propagate min bound for negative variables
for (int i = y.size(); i--; ) {
// Compute bound
FloatNum sl = -c.max();
for (int j = x.size(); j--; )
sl = r.add_down(sl,x[j].min());
for (int j = y.size(); j--; ) {
if (i == j) continue;
sl = r.sub_down(sl,y[j].max());
}
ModEvent me = y[i].gq(home,sl);
if (me_failed(me))
return ES_FAILED;
if (me != ME_FLOAT_VAL)
assigned = false;
if (me_modified(me))
es = ES_NOFIX;
}
// Propagate min bound for positive variables
for (int i = x.size(); i--; ) {
// Compute bound
FloatNum su = c.min();
for (int j = x.size(); j--; ) {
if (i == j) continue;
su = r.sub_down(su,x[j].max());
}
for (int j = y.size(); j--; )
su = r.add_down(su,y[j].min());
ModEvent me = x[i].gq(home,su);
if (me_failed(me))
return ES_FAILED;
if (me != ME_FLOAT_VAL)
assigned = false;
if (me_modified(me))
es = ES_NOFIX;
}
// Propagate max bound for negative variables
for (int i = y.size(); i--; ) {
// Compute bound
FloatNum su = -c.min();
for (int j = x.size(); j--; )
su = r.add_up(su,x[j].max());
for (int j = y.size(); j--; ) {
if (i == j) continue;
su = r.sub_up(su,y[j].min());
}
ModEvent me = y[i].lq(home,su);
if (me_failed(me))
return ES_FAILED;
if (me != ME_FLOAT_VAL)
assigned = false;
if (me_modified(me))
es = ES_NOFIX;
}
return assigned ? home.ES_SUBSUMED(*this) : es;
}
/*
* Bound consistent linear inequation
*
*/
template<class P, class N>
forceinline
Lq<P,N>::Lq(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c)
: Lin<P,N,PC_FLOAT_BND>(home,x,y,c) {}
template<class P, class N>
ExecStatus
Lq<P,N>::post(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c) {
(void) new (home) Lq<P,N>(home,x,y,c);
return ES_OK;
}
template<class P, class N>
forceinline
Lq<P,N>::Lq(Space& home, Lq<P,N>& p)
: Lin<P,N,PC_FLOAT_BND>(home,p) {}
template<class P, class N>
Actor*
Lq<P,N>::copy(Space& home) {
return new (home) Lq<P,N>(home,*this);
}
template<class P, class N>
ExecStatus
Lq<P,N>::propagate(Space& home, const ModEventDelta& med) {
// Eliminate singletons
FloatNum sl = 0.0;
Rounding r;
if (FloatView::me(med) == ME_FLOAT_VAL) {
for (int i = x.size(); i--; ) {
if (x[i].assigned()) {
c -= x[i].val(); x.move_lst(i);
} else {
sl = r.sub_up(sl,x[i].min());
}
}
for (int i = y.size(); i--; ) {
if (y[i].assigned()) {
c += y[i].val(); y.move_lst(i);
} else {
sl = r.add_up(sl,y[i].max());
}
}
if ((x.size() + y.size()) <= 1) {
if (x.size() == 1) {
GECODE_ME_CHECK(x[0].lq(home,c.max()));
return home.ES_SUBSUMED(*this);
}
if (y.size() == 1) {
GECODE_ME_CHECK(y[0].gq(home,(-c).min()));
return home.ES_SUBSUMED(*this);
}
return (c.max() >= 0) ? home.ES_SUBSUMED(*this) : ES_FAILED;
}
} else {
for (int i = x.size(); i--; )
sl = r.sub_up(sl,x[i].min());
for (int i = y.size(); i--; )
sl = r.add_up(sl,y[i].max());
}
sl = r.add_up(sl,c.max());
ExecStatus es = ES_FIX;
bool assigned = true;
for (int i = x.size(); i--; ) {
assert(!x[i].assigned());
FloatNum slx = r.add_up(sl,x[i].min());
ModEvent me = x[i].lq(home,slx);
if (me == ME_FLOAT_FAILED)
return ES_FAILED;
if (me != ME_FLOAT_VAL)
assigned = false;
if (me_modified(me))
es = ES_NOFIX;
}
for (int i = y.size(); i--; ) {
assert(!y[i].assigned());
FloatNum sly = r.sub_up(y[i].max(),sl);
ModEvent me = y[i].gq(home,sly);
if (me == ME_FLOAT_FAILED)
return ES_FAILED;
if (me != ME_FLOAT_VAL)
assigned = false;
if (me_modified(me))
es = ES_NOFIX;
}
return assigned ? home.ES_SUBSUMED(*this) : es;
}
}}}
// STATISTICS: float-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::FloatVal
Float value type.
Definition float.hh:334
Gecode::Float::Linear::Eq::post
static ExecStatus post(Home home, ViewArray< P > &x, ViewArray< N > &y, FloatVal c)
Post propagator for .
Definition nary.hpp:128
Gecode::Float::Linear::Eq::copy
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition nary.hpp:141
Gecode::Float::Linear::Eq::Eq
Eq(Space &home, Eq &p)
Constructor for cloning p.
Definition nary.hpp:136
Gecode::Float::Linear::Eq::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition nary.hpp:147
Gecode::Float::Linear::Lin::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low linear).
Definition nary.hpp:60
Gecode::Float::Linear::Lin::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition nary.hpp:73
Gecode::Float::Linear::Lin::Lin
Lin(Space &home, Lin< P, N, pc > &p)
Constructor for cloning p.
Definition nary.hpp:52
Gecode::Float::Linear::Lin::x
ViewArray< P > x
Array of positive views.
Definition linear.hh:60
Gecode::Float::Linear::Lin::reschedule
virtual void reschedule(Space &home)
Schedule function.
Definition nary.hpp:66
Gecode::Float::Linear::Lin::y
ViewArray< N > y
Array of negative views.
Definition linear.hh:62
Gecode::Float::Linear::Lin::c
FloatVal c
Constant value.
Definition linear.hh:64
Gecode::Float::Linear::Lq::post
static ExecStatus post(Home home, ViewArray< P > &x, ViewArray< N > &y, FloatVal c)
Post propagator for .
Definition nary.hpp:258
Gecode::Float::Linear::Lq::copy
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition nary.hpp:270
Gecode::Float::Linear::Lq::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition nary.hpp:276
Gecode::Float::Linear::Lq::Lq
Lq(Space &home, Lq &p)
Constructor for cloning p.
Definition nary.hpp:265
Gecode::Float::Rounding
Floating point rounding policy.
Definition float.hh:154
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
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::Space
friend class Space
Definition core.hpp:1066
Gecode::Propagator::med
ModEventDelta med
A set of modification events (used during propagation).
Definition core.hpp:1075
Gecode::Propagator::Propagator
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3498
Gecode::VarImpView< FloatVar >::me
static ModEvent me(const ModEventDelta &med)
Definition view.hpp:552
Gecode::ViewArray
View arrays.
Definition array.hpp:253
Gecode::ViewArray::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1156
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::me_modified
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition modevent.hpp:59
Gecode::FloatNum
double FloatNum
Floating point number base type.
Definition float.hh:106
Gecode::Float::Linear
Linear propagators
Gecode::Float::Linear::eliminate_n
void eliminate_n(ModEventDelta med, ViewArray< View > &y, FloatVal &c)
Definition nary.hpp:98
Gecode::Float::Linear::eliminate_p
void eliminate_p(ModEventDelta med, ViewArray< View > &x, FloatVal &c)
Definition nary.hpp:83
Gecode::Float::Linear::infty
bool infty(const FloatNum &n)
Definition nary.hpp:111
Gecode::Float
Floating point numbers.
Gecode::Float::ME_FLOAT_VAL
const Gecode::ModEvent ME_FLOAT_VAL
Domain operation has resulted in a value (assigned variable).
Definition var-type.hpp:264
Gecode::Float::ME_FLOAT_FAILED
const Gecode::ModEvent ME_FLOAT_FAILED
Domain operation has resulted in failure.
Definition var-type.hpp:260
Gecode::Float::PC_FLOAT_BND
const Gecode::PropCond PC_FLOAT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:292
Gecode
Gecode toplevel namespace
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_FIX
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
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