val.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Mikael Lagerkvist <lagerkvist@gecode.org>
*
* Copyright:
* Mikael Lagerkvist, 2005
*
* 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 <algorithm>
/*
* This is the propagation algorithm of the cumulatives constraint as
* presented in:
* Nicolas Beldiceanu and Mats Carlsson, A New Multi-resource cumulatives
* Constraint with Negative Heights. CP 2002, pages 63-79, Springer-Verlag.
*/
namespace Gecode { namespace Int { namespace Cumulatives {
template<class ViewM, class ViewP, class ViewU, class View>
forceinline
Val<ViewM,ViewP,ViewU,View>::Val(Home home,
const ViewArray<ViewM>& _m,
const ViewArray<View>& _s,
const ViewArray<ViewP>& _p,
const ViewArray<View>& _e,
const ViewArray<ViewU>& _u,
const SharedArray<int>& _c,
bool _at_most) :
Propagator(home),
m(_m), s(_s), p(_p), e(_e), u(_u), c(_c), at_most(_at_most) {
home.notice(*this,AP_DISPOSE);
m.subscribe(home,*this,Int::PC_INT_DOM);
s.subscribe(home,*this,Int::PC_INT_BND);
p.subscribe(home,*this,Int::PC_INT_BND);
e.subscribe(home,*this,Int::PC_INT_BND);
u.subscribe(home,*this,Int::PC_INT_BND);
}
template<class ViewM, class ViewP, class ViewU, class View>
ExecStatus
Val<ViewM,ViewP,ViewU,View>
::post(Home home, const ViewArray<ViewM>& m,
const ViewArray<View>& s, const ViewArray<ViewP>& p,
const ViewArray<View>& e, const ViewArray<ViewU>& u,
const SharedArray<int>& c, bool at_most) {
(void) new (home) Val(home, m,s,p,e,u,c,at_most);
return ES_OK;
}
template<class ViewM, class ViewP, class ViewU, class View>
forceinline
Val<ViewM,ViewP,ViewU,View>::Val(Space& home,
Val<ViewM,ViewP,ViewU,View>& vp)
: Propagator(home,vp), c(vp.c), at_most(vp.at_most) {
m.update(home,vp.m);
s.update(home, vp.s);
p.update(home, vp.p);
e.update(home, vp.e);
u.update(home, vp.u);
}
template<class ViewM, class ViewP, class ViewU, class View>
size_t
Val<ViewM,ViewP,ViewU,View>::dispose(Space& home) {
home.ignore(*this,AP_DISPOSE);
if (!home.failed()) {
m.cancel(home,*this,Int::PC_INT_DOM);
s.cancel(home,*this,Int::PC_INT_BND);
p.cancel(home,*this,Int::PC_INT_BND);
e.cancel(home,*this,Int::PC_INT_BND);
u.cancel(home,*this,Int::PC_INT_BND);
}
c.~SharedArray();
(void) Propagator::dispose(home);
return sizeof(*this);
}
template<class ViewM, class ViewP, class ViewU, class View>
PropCost
Val<ViewM,ViewP,ViewU,View>::cost(const Space&, const ModEventDelta&) const {
return PropCost::quadratic(PropCost::LO, s.size());
}
template<class ViewM, class ViewP, class ViewU, class View>
void
Val<ViewM,ViewP,ViewU,View>::reschedule(Space& home) {
m.reschedule(home,*this,Int::PC_INT_DOM);
s.reschedule(home,*this,Int::PC_INT_BND);
p.reschedule(home,*this,Int::PC_INT_BND);
e.reschedule(home,*this,Int::PC_INT_BND);
u.reschedule(home,*this,Int::PC_INT_BND);
}
template<class ViewM, class ViewP, class ViewU, class View>
Actor*
Val<ViewM,ViewP,ViewU,View>::copy(Space& home) {
return new (home) Val<ViewM,ViewP,ViewU,View>(home,*this);
}
typedef enum {EVENT_CHCK, EVENT_PROF, EVENT_PRUN} ev_t;
class Event
{
public:
ev_t e;
int task;
int date;
int inc;
bool first_prof;
Event(ev_t _e, int _task, int _date, int _inc = 0, bool _first_prof = false)
: e(_e), task(_task), date(_date), inc(_inc), first_prof(_first_prof)
{}
// Default constructor for region-allocated memory
Event(void) {}
bool operator <(const Event& ev) const {
if (date == ev.date) {
if (e == EVENT_PROF && ev.e != EVENT_PROF) return true;
if (e == EVENT_CHCK && ev.e == EVENT_PRUN) return true;
return false;
}
return date < ev.date;
}
};
template<class ViewM, class ViewP, class ViewU, class View>
ExecStatus
Val<ViewM,ViewP,ViewU,View>::prune(Space& home, int low, int up, int r,
int ntask, int su,
int* contribution,
int* prune_tasks, int& prune_tasks_size) {
if (ntask > 0 && (at_most ? su > c[r] : su < c[r])) {
return ES_FAILED;
}
int pti = 0;
while (pti != prune_tasks_size) {
int t = prune_tasks[pti];
// Algorithm 2.
// Prune the machine, start, and end for required
// tasks for machine r that have heights possibly greater than 0.
if (ntask != 0 &&
(at_most ? u[t].min() < 0
: u[t].max() > 0) &&
(at_most ? su-contribution[t] > c[r]
: su-contribution[t] < c[r])) {
if (me_failed(m[t].eq(home, r))||
me_failed(s[t].gq(home, up-p[t].max()+1))||
me_failed(s[t].lq(home, low))||
me_failed(e[t].lq(home,low+p[t].max()))||
me_failed(e[t].gq(home, up+1))||
me_failed(p[t].gq(home,std::min(up-s[t].max()+1,e[t].min()-low)))
) {
return ES_FAILED;
}
}
// Algorithm 3.
// Remove values that prevent us from reaching the limit
if (at_most ? u[t].min() > std::min(0, c[r])
: u[t].max() < std::max(0, c[r])) {
if (at_most ? su-contribution[t]+u[t].min() > c[r]
: su-contribution[t]+u[t].max() < c[r]) {
if (e[t].min() > low &&
s[t].max() <= up &&
p[t].min() > 0) {
if (me_failed(m[t].nq(home, r))) {
return ES_FAILED;
}
} else if (m[t].assigned()) {
int ptmin = p[t].min();
if (ptmin > 0) {
Iter::Ranges::Singleton
a(low-ptmin+1, up), b(low+1, up+ptmin);
if (me_failed(s[t].minus_r(home,a,false)) ||
me_failed(e[t].minus_r(home, b,false)))
return ES_FAILED;
}
if (me_failed(p[t].lq(home,std::max(std::max(low-s[t].min(),
e[t].max()-up-1),
0)))) {
return ES_FAILED;
}
}
}
}
// Algorithm 4.
// Remove bad negative values from for-sure heights.
/* \note "It is not sufficient to only test for assignment of machine[t]
* since Algorithm 3 can remove the value." Check this against
* the conditions for Alg3.
*/
if (m[t].assigned() &&
m[t].val() == r &&
e[t].min() > low &&
s[t].max() <= up &&
p[t].min() > 0 ) {
if (me_failed(at_most
? u[t].lq(home, c[r]-su+contribution[t])
: u[t].gq(home, c[r]-su+contribution[t]))) {
return ES_FAILED;
}
}
// Remove tasks that are no longer relevant.
if (!m[t].in(r) || (e[t].max() <= up+1)) {
prune_tasks[pti] = prune_tasks[--prune_tasks_size];
} else {
++pti;
}
}
return ES_OK;
}
namespace {
template<class C>
class Less {
public:
bool operator ()(const C& lhs, const C& rhs) {
return lhs < rhs;
}
};
}
template<class ViewM, class ViewP, class ViewU, class View>
ExecStatus
Val<ViewM,ViewP,ViewU,View>::propagate(Space& home, const ModEventDelta&) {
// Check for subsumption
bool subsumed = true;
for (int t=0; t<s.size(); t++)
if (!(p[t].assigned() && e[t].assigned() &&
m[t].assigned() && s[t].assigned() &&
u[t].assigned())) {
subsumed = false;
break;
}
// Propagate information for machine r
Region region;
Event *events = region.alloc<Event>(s.size()*8);
int events_size;
int *prune_tasks = region.alloc<int>(s.size());
int prune_tasks_size;
int *contribution = region.alloc<int>(s.size());
for (int r = c.size(); r--; ) {
events_size = 0;
#define GECODE_PUSH_EVENTS(E) assert(events_size < s.size()*8); \
events[events_size++] = E
// Find events for sweep-line
for (int t = s.size(); t--; ) {
if (m[t].assigned() &&
m[t].val() == r &&
s[t].max() < e[t].min()) {
if (at_most
? u[t].min() > std::min(0, c[r])
: u[t].max() < std::max(0, c[r])) {
GECODE_PUSH_EVENTS(Event(EVENT_CHCK, t, s[t].max(), 1));
GECODE_PUSH_EVENTS(Event(EVENT_CHCK, t, e[t].min(), -1));
}
if (at_most
? u[t].min() > 0
: u[t].max() < 0) {
GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, s[t].max(),
at_most ? u[t].min() : u[t].max(), true));
GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, e[t].min(),
at_most ? -u[t].min() : -u[t].max()));
}
}
if (m[t].in(r)) {
if (at_most
? u[t].min() < 0
: u[t].max() > 0) {
GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, s[t].min(),
at_most ? u[t].min() : u[t].max(), true));
GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, e[t].max(),
at_most ? -u[t].min() : -u[t].max()));
}
if (!(m[t].assigned() &&
u[t].assigned() &&
s[t].assigned() &&
e[t].assigned())) {
GECODE_PUSH_EVENTS(Event(EVENT_PRUN, t, s[t].min()));
}
}
}
#undef GECODE_PUSH_EVENTS
// If there are no events, continue with next machine
if (events_size == 0) {
continue;
}
// Sort the events according to date
Less<Event> less;
Support::insertion(&events[0], events_size, less);
// Sweep line along d, starting at 0
int d = 0;
int ntask = 0;
int su = 0;
int ei = 0;
prune_tasks_size = 0;
for (int i = s.size(); i--; ) contribution[i] = 0;
d = events[ei].date;
while (ei < events_size) {
if (events[ei].e != EVENT_PRUN) {
if (d != events[ei].date) {
GECODE_ES_CHECK(prune(home, d, events[ei].date-1, r,
ntask, su,
contribution, prune_tasks, prune_tasks_size));
d = events[ei].date;
}
if (events[ei].e == EVENT_CHCK) {
ntask += events[ei].inc;
} else /* if (events[ei].e == EVENT_PROF) */ {
su += events[ei].inc;
if(events[ei].first_prof)
contribution[events[ei].task] = at_most
? std::max(contribution[events[ei].task], events[ei].inc)
: std::min(contribution[events[ei].task], events[ei].inc);
}
} else /* if (events[ei].e == EVENT_PRUN) */ {
assert(prune_tasks_size<s.size());
prune_tasks[prune_tasks_size++] = events[ei].task;
}
ei++;
}
GECODE_ES_CHECK(prune(home, d, d, r,
ntask, su,
contribution, prune_tasks, prune_tasks_size));
}
return subsumed ? home.ES_SUBSUMED(*this): ES_NOFIX;
}
}}}
// STATISTICS: int-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::Int::Cumulatives::Event
An event collects the information for one evnet for the sweep-line.
Definition val.hpp:131
Gecode::Int::Cumulatives::Event::first_prof
bool first_prof
Definition val.hpp:145
Gecode::Int::Cumulatives::Event::date
int date
The date of this event.
Definition val.hpp:138
Gecode::Int::Cumulatives::Event::Event
Event(ev_t _e, int _task, int _date, int _inc=0, bool _first_prof=false)
Simple constructor.
Definition val.hpp:148
Gecode::Int::Cumulatives::Event::task
int task
The task this event refers to.
Definition val.hpp:136
Gecode::Int::Cumulatives::Event::e
ev_t e
The type of the event.
Definition val.hpp:134
Gecode::Int::Cumulatives::Event::operator<
bool operator<(const Event &ev) const
Order events based on date.
Definition val.hpp:156
Gecode::Int::Cumulatives::Event::Event
Event(void)
Definition val.hpp:153
Gecode::Int::Cumulatives::Event::inc
int inc
The quantity changed by this event (if any).
Definition val.hpp:140
Gecode::Int::Cumulatives::Val
Propagator for the cumulatives constraint
Definition cumulatives.hh:86
Gecode::Int::Cumulatives::Val::u
ViewArray< ViewU > u
Definition cumulatives.hh:92
Gecode::Int::Cumulatives::Val::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition val.hpp:271
Gecode::Int::Cumulatives::Val::prune
ExecStatus prune(Space &home, int low, int up, int r, int ntask, int su, int *contribution, int *prune_tasks, int &prune_tasks_size)
Definition val.hpp:168
Gecode::Int::Cumulatives::Val::s
ViewArray< View > s
Definition cumulatives.hh:89
Gecode::Int::Cumulatives::Val::copy
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition val.hpp:123
Gecode::Int::Cumulatives::Val::at_most
const bool at_most
Definition cumulatives.hh:94
Gecode::Int::Cumulatives::Val::reschedule
virtual void reschedule(Space &home)
Schedule function.
Definition val.hpp:113
Gecode::Int::Cumulatives::Val::m
ViewArray< ViewM > m
Definition cumulatives.hh:88
Gecode::Int::Cumulatives::Val::Val
Val(Space &home, Val< ViewM, ViewP, ViewU, View > &p)
Definition val.hpp:79
Gecode::Int::Cumulatives::Val::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low quadratic).
Definition val.hpp:107
Gecode::Int::Cumulatives::Val::e
ViewArray< View > e
Definition cumulatives.hh:91
Gecode::Int::Cumulatives::Val::dispose
virtual size_t dispose(Space &home)
Dispose propagator.
Definition val.hpp:91
Gecode::Int::Cumulatives::Val::c
SharedArray< int > c
Definition cumulatives.hh:93
Gecode::Int::Cumulatives::Val::p
ViewArray< ViewP > p
Definition cumulatives.hh:90
Gecode::Iter::Ranges::Singleton
Range iterator for singleton range.
Definition ranges-singleton.hpp:42
Gecode::PropCost
Propagation cost.
Definition core.hpp:486
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::LO
@ LO
Cheap.
Definition core.hpp:513
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::Region::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition region.hpp:386
Gecode::SharedArray
Shared array with arbitrary number of elements.
Definition shared-array.hpp:53
Gecode::ViewArray
View arrays.
Definition array.hpp:253
Gecode::Int::OffsetView::operator()
View & operator()(View &x)
Integer-precision integer scale view.
Definition view.hpp:632
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::Space::failed
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4044
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::AP_DISPOSE
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:562
GECODE_PUSH_EVENTS
#define GECODE_PUSH_EVENTS(E)
Gecode::Int::Cumulatives
Cumulatives propagators
Definition cumulatives.hh:39
Gecode::Int::Cumulatives::ev_t
ev_t
Types of events for the sweep-line.
Definition val.hpp:128
Gecode::Int::Cumulatives::EVENT_CHCK
@ EVENT_CHCK
Definition val.hpp:128
Gecode::Int::Cumulatives::EVENT_PRUN
@ EVENT_PRUN
Definition val.hpp:128
Gecode::Int::Cumulatives::EVENT_PROF
@ EVENT_PROF
Definition val.hpp:128
Gecode::Int::LDSB::prune
ModEvent prune(Space &home, View x, int v)
Exclude value \v from variable view \x.
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::Support::insertion
void insertion(Type *l, Type *r, Less &less)
Standard insertion sort.
Definition sort.hpp:97
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_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
forceinline
#define forceinline
Definition config.hpp:187