cumulatives.cpp
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 "test/int.hh"
#include <gecode/minimodel.hh>
#include <gecode/search.hh>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
namespace Test { namespace Int {
namespace Cumulatives {
class Ass : public Gecode::Space {
public:
Gecode::IntVarArray x;
Ass(int n, const Gecode::IntSet& d) : x(*this, n, d) {
using namespace Gecode;
for (int i = 0; i < n; i += 4) {
rel(*this, x[i+0] >= 0);
rel(*this, x[i+1] >= 0);
rel(*this, x[i+2] >= 0);
rel(*this, x[i] + x[i+1] == x[i+2]);
branch(*this, x, INT_VAR_NONE(), INT_VAL_MIN());
}
}
Ass(Ass& s) : Gecode::Space(s) {
x.update(*this, s.x);
}
virtual Gecode::Space* copy(void) {
return new Ass(*this);
}
};
class CumulativeAssignment : public Assignment {
Ass* cur;
Ass* nxt;
Gecode::DFS<Ass>* e;
public:
CumulativeAssignment(int n, const Gecode::IntSet& d) : Assignment(n,d) {
Ass* a = new Ass(n, d);
e = new Gecode::DFS<Ass>(a);
delete a;
nxt = cur = e->next();
if (cur != NULL)
nxt = e->next();
}
virtual bool operator()(void) const {
return nxt != NULL;
}
virtual void operator++(void) {
delete cur;
cur = nxt;
if (cur != NULL) nxt = e->next();
}
virtual int operator[](int i) const {
assert((i>=0) && (i<n) && (cur != NULL));
return cur->x[i].val();
}
virtual ~CumulativeAssignment(void) {
delete cur; delete nxt; delete e;
}
};
class Event {
public:
int p, h;
bool start;
Event(int pos, int height, bool s) : p(pos), h(height), start(s) {}
bool operator<(const Event& e) const {
return p<e.p;
}
};
class Below {
public:
int limit;
Below(int l) : limit(l) {}
bool operator()(int val) {
return val <= limit;
}
};
class Above {
public:
int limit;
Above(int l) : limit(l) {}
bool operator()(int val) {
return val >= limit;
}
};
template<class C>
bool valid(std::vector<Event> e, C comp) {
std::sort(e.begin(), e.end());
unsigned int i = 0;
int p = 0;
int h = 0;
int n = 0;
while (i < e.size()) {
p = e[i].p;
while (i < e.size() && e[i].p == p) {
h += e[i].h;
n += (e[i].start ? +1 : -1);
++i;
}
if (n && !comp(h))
return false;
}
return true;
}
class Cumulatives : public Test {
protected:
int ntasks;
bool at_most;
int limit;
public:
Cumulatives(const std::string& s, int nt, bool am, int l)
: Test("Cumulatives::"+s,nt*4,-1,2), ntasks(nt), at_most(am), limit(l) {
testsearch = false;
}
virtual Assignment* assignment(void) const {
assert(arity == 4*ntasks);
return new CumulativeAssignment(arity, dom);
}
virtual bool solution(const Assignment& x) const {
std::vector<Event> e;
for (int i = 0; i < ntasks; ++i) {
int p = i*4;
// Positive start, duration and end
if (x[p+0] < 0 || x[p+1] < 1 || x[p+2] < 1) return false;
// Start + Duration == End
if (x[p+0] + x[p+1] != x[p+2]) {
return false;
}
}
for (int i = 0; i < ntasks; ++i) {
int p = i*4;
// Up at start, down at end.
e.push_back(Event(x[p+0], +x[p+3], true));
e.push_back(Event(x[p+2], -x[p+3], false));
}
if (at_most) {
return valid(e, Below(limit));
} else {
return valid(e, Above(limit));
}
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
using namespace Gecode;
IntArgs m(ntasks), l({limit});
IntVarArgs s(ntasks), d(ntasks), e(ntasks), h(ntasks);
for (int i = 0; i < ntasks; ++i) {
int p = i*4;
m[i] = 0;
s[i] = x[p+0]; rel(home, x[p+0], Gecode::IRT_GQ, 0);
d[i] = x[p+1]; rel(home, x[p+1], Gecode::IRT_GQ, 1);
e[i] = x[p+2]; rel(home, x[p+2], Gecode::IRT_GQ, 1);
h[i] = x[p+3];
}
cumulatives(home, m, s, d, e, h, l, at_most);
}
};
Cumulatives c1t1("1t1", 1, true, 1);
Cumulatives c1f1("1f1", 1, false, 1);
Cumulatives c1t2("1t2", 1, true, 2);
Cumulatives c1f2("1f2", 1, false, 2);
Cumulatives c1t3("1t3", 1, true, 3);
Cumulatives c1f3("1f3", 1, false, 3);
Cumulatives c2t1("2t1", 2, true, 1);
Cumulatives c2f1("2f1", 2, false, 1);
Cumulatives c2t2("2t2", 2, true, 2);
Cumulatives c2f2("2f2", 2, false, 2);
Cumulatives c2t3("2t3", 2, true, 3);
Cumulatives c2f3("2f3", 2, false, 3);
Cumulatives c3t1("3t1", 3, true, 1);
Cumulatives c3f1("3f1", 3, false, 1);
Cumulatives c3t2("3t2", 3, true, 2);
Cumulatives c3f2("3f2", 3, false, 2);
Cumulatives c3t3("3t3", 3, true, 3);
Cumulatives c3f3("3f3", 3, false, 3);
Cumulatives c3t_1("3t-1", 3, true, -1);
Cumulatives c3f_1("3f-1", 3, false, -1);
Cumulatives c3t_2("3t-2", 3, true, -2);
Cumulatives c3f_2("3f-2", 3, false, -2);
Cumulatives c3t_3("3t-3", 3, true, -3);
Cumulatives c3f_3("3f-3", 3, false, -3);
}
}}
// STATISTICS: test-int
Gecode::ArgArrayBase::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1607
Gecode::DFS
Depth-first search engine.
Definition search.hh:1036
Gecode::IntArgs
Passing integer arguments.
Definition int.hh:628
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::IntVarArgs
Passing integer variables.
Definition int.hh:656
Gecode::IntVarArray
Integer variable array.
Definition int.hh:763
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Test::Int::Assignment
Base class for assignments
Definition int.hh:59
Test::Int::Assignment::d
Gecode::IntSet d
Domain for each variable.
Definition int.hh:62
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::Cumulatives::Above
Describe that event is above a certain limit.
Definition cumulatives.cpp:153
Test::Int::Cumulatives::Above::operator()
bool operator()(int val)
Test whether val is above limit
Definition cumulatives.cpp:159
Test::Int::Cumulatives::Above::limit
int limit
limit Initialize
Definition cumulatives.cpp:155
Test::Int::Cumulatives::Above::Above
Above(int l)
Definition cumulatives.cpp:157
Test::Int::Cumulatives::Ass
Script for generating assignments.
Definition cumulatives.cpp:64
Test::Int::Cumulatives::Ass::Ass
Ass(Ass &s)
Constructor for cloning s.
Definition cumulatives.cpp:80
Test::Int::Cumulatives::Ass::copy
virtual Gecode::Space * copy(void)
Create copy during cloning.
Definition cumulatives.cpp:84
Test::Int::Cumulatives::Ass::Ass
Ass(int n, const Gecode::IntSet &d)
Initialize model for assignments.
Definition cumulatives.cpp:69
Test::Int::Cumulatives::Ass::x
Gecode::IntVarArray x
Store task information.
Definition cumulatives.cpp:67
Test::Int::Cumulatives::Below
Describe that event is below a certain limit.
Definition cumulatives.cpp:142
Test::Int::Cumulatives::Below::limit
int limit
limit Initialize
Definition cumulatives.cpp:144
Test::Int::Cumulatives::Below::operator()
bool operator()(int val)
Test whether val is below limit
Definition cumulatives.cpp:148
Test::Int::Cumulatives::Below::Below
Below(int l)
Definition cumulatives.cpp:146
Test::Int::Cumulatives::CumulativeAssignment
Class for generating reasonable assignments.
Definition cumulatives.cpp:90
Test::Int::Cumulatives::CumulativeAssignment::operator++
virtual void operator++(void)
Move to next assignment.
Definition cumulatives.cpp:112
Test::Int::Cumulatives::CumulativeAssignment::operator()
virtual bool operator()(void) const
Test whether all assignments have been iterated
Definition cumulatives.cpp:108
Test::Int::Cumulatives::CumulativeAssignment::CumulativeAssignment
CumulativeAssignment(int n, const Gecode::IntSet &d)
Initialize assignments for n0 variables and values d0.
Definition cumulatives.cpp:99
Test::Int::Cumulatives::CumulativeAssignment::~CumulativeAssignment
virtual ~CumulativeAssignment(void)
Destructor.
Definition cumulatives.cpp:123
Test::Int::Cumulatives::CumulativeAssignment::operator[]
virtual int operator[](int i) const
Return value for variable i.
Definition cumulatives.cpp:118
Test::Int::Cumulatives::Cumulatives
Test for cumulatives constraint
Definition cumulatives.cpp:186
Test::Int::Cumulatives::Cumulatives::ntasks
int ntasks
Number of tasks.
Definition cumulatives.cpp:188
Test::Int::Cumulatives::Cumulatives::limit
int limit
Limit.
Definition cumulatives.cpp:190
Test::Int::Cumulatives::Cumulatives::at_most
bool at_most
Whether to use atmost reasoning.
Definition cumulatives.cpp:189
Test::Int::Cumulatives::Cumulatives::solution
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition cumulatives.cpp:203
Test::Int::Cumulatives::Cumulatives::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition cumulatives.cpp:227
Test::Int::Cumulatives::Cumulatives::assignment
virtual Assignment * assignment(void) const
Create first assignment.
Definition cumulatives.cpp:198
Test::Int::Cumulatives::Cumulatives::Cumulatives
Cumulatives(const std::string &s, int nt, bool am, int l)
Create and register test.
Definition cumulatives.cpp:193
Test::Int::Cumulatives::Event
Event to be scheduled
Definition cumulatives.cpp:129
Test::Int::Cumulatives::Event::start
bool start
Whether event has just started Initialize event.
Definition cumulatives.cpp:132
Test::Int::Cumulatives::Event::h
int h
Position and height of event.
Definition cumulatives.cpp:131
Test::Int::Cumulatives::Event::operator<
bool operator<(const Event &e) const
Test whether this event is before event e
Definition cumulatives.cpp:136
Test::Int::Cumulatives::Event::p
int p
Definition cumulatives.cpp:131
Test::Int::Cumulatives::Event::Event
Event(int pos, int height, bool s)
Definition cumulatives.cpp:134
Test::Int::Test::testsearch
bool testsearch
Whether to perform search test.
Definition int.hh:238
Test::Int::Test::arity
int arity
Number of variables.
Definition int.hh:226
Test::Int::Test::dom
Gecode::IntSet dom
Domain of variables.
Definition int.hh:228
Gecode::branch
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
Gecode::rel
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
Gecode::IRT_GQ
@ IRT_GQ
Greater or equal ( ).
Definition int.hh:930
Gecode::Space::Space
Space(void)
Default constructor.
Definition core.cpp:115
minimodel.hh
Gecode
Gecode toplevel namespace
Gecode::INT_VAR_NONE
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
Gecode::cumulatives
void cumulatives(Home home, const IntVarArgs &m, const IntVarArgs &s, const IntVarArgs &p, const IntVarArgs &e, const IntVarArgs &u, const IntArgs &c, bool at_most, IntPropLevel ipl=IPL_DEF)
Post propagators for the cumulatives constraint.
Definition cumulatives.cpp:110
Gecode::INT_VAL_MIN
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
Test::Int::Cumulatives::c1t3
Cumulatives c1t3("1t3", 1, true, 3)
Test::Int::Cumulatives::valid
bool valid(std::vector< Event > e, C comp)
Check whether event e is valid.
Definition cumulatives.cpp:166
Test::Int::Cumulatives::c3f1
Cumulatives c3f1("3f1", 3, false, 1)
Test::Int::Cumulatives::c3f_2
Cumulatives c3f_2("3f-2", 3, false, -2)
Test::Int::Cumulatives::c2t2
Cumulatives c2t2("2t2", 2, true, 2)
Test::Int::Cumulatives::c1t1
Cumulatives c1t1("1t1", 1, true, 1)
Test::Int::Cumulatives::c3t_2
Cumulatives c3t_2("3t-2", 3, true, -2)
Test::Int::Cumulatives::c3f3
Cumulatives c3f3("3f3", 3, false, 3)
Test::Int::Cumulatives::c2f1
Cumulatives c2f1("2f1", 2, false, 1)
Test::Int::Cumulatives::c1f1
Cumulatives c1f1("1f1", 1, false, 1)
Test::Int::Cumulatives::c2f2
Cumulatives c2f2("2f2", 2, false, 2)
Test::Int::Cumulatives::c2t3
Cumulatives c2t3("2t3", 2, true, 3)
Test::Int::Cumulatives::c1t2
Cumulatives c1t2("1t2", 1, true, 2)
Test::Int::Cumulatives::c2t1
Cumulatives c2t1("2t1", 2, true, 1)
Test::Int::Cumulatives::c3t_3
Cumulatives c3t_3("3t-3", 3, true, -3)
Test::Int::Cumulatives::c3t2
Cumulatives c3t2("3t2", 3, true, 2)
Test::Int::Cumulatives::c2f3
Cumulatives c2f3("2f3", 2, false, 3)
Test::Int::Cumulatives::c3f2
Cumulatives c3f2("3f2", 3, false, 2)
Test::Int::Cumulatives::c1f2
Cumulatives c1f2("1f2", 1, false, 2)
Test::Int::Cumulatives::c1f3
Cumulatives c1f3("1f3", 1, false, 3)
Test::Int::Cumulatives::c3t1
Cumulatives c3t1("3t1", 3, true, 1)
Test::Int::Cumulatives::c3f_3
Cumulatives c3f_3("3f-3", 3, false, -3)
Test::Int::Cumulatives::c3f_1
Cumulatives c3f_1("3f-1", 3, false, -1)
Test::Int::Cumulatives::c3t_1
Cumulatives c3t_1("3t-1", 3, true, -1)
Test::Int::Cumulatives::c3t3
Cumulatives c3t3("3t3", 3, true, 3)
Test::Int
Testing finite domain integers.
Definition int.cpp:40
Test
General test support.
Definition afc.cpp:39
search.hh
int.hh