linear.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, 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>
namespace Test { namespace Int {
namespace Linear {
bool one(const Gecode::IntArgs& a) {
for (int i=a.size(); i--; )
if (a[i] != 1)
return false;
return true;
}
class IntInt : public Test {
protected:
Gecode::IntArgs a;
Gecode::IntRelType irt;
int c;
public:
IntInt(const std::string& s, const Gecode::IntSet& d,
const Gecode::IntArgs& a0, Gecode::IntRelType irt0,
int c0, Gecode::IntPropLevel ipl=Gecode::IPL_BND)
: Test("Linear::Int::Int::"+
str(irt0)+"::"+str(ipl)+"::"+s+"::"+str(c0)+"::"
+str(a0.size()),
a0.size(),d,ipl != Gecode::IPL_DOM,ipl),
a(a0), irt(irt0), c(c0) {
testfix=false;
}
virtual bool solution(const Assignment& x) const {
double e = 0.0;
for (int i=0; i<x.size(); i++)
e += a[i]*x[i];
return cmp(e, irt, static_cast<double>(c));
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
if (one(a))
Gecode::linear(home, x, irt, c, ipl);
else
Gecode::linear(home, a, x, irt, c, ipl);
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
Gecode::Reify r) {
if (one(a))
Gecode::linear(home, x, irt, c, r, ipl);
else
Gecode::linear(home, a, x, irt, c, r, ipl);
}
};
class IntVar : public Test {
protected:
Gecode::IntArgs a;
Gecode::IntRelType irt;
public:
IntVar(const std::string& s, const Gecode::IntSet& d,
const Gecode::IntArgs& a0, Gecode::IntRelType irt0,
Gecode::IntPropLevel ipl=Gecode::IPL_BND)
: Test("Linear::Int::Var::"+
str(irt0)+"::"+str(ipl)+"::"+s+"::"+str(a0.size()),
a0.size()+1,d,ipl != Gecode::IPL_DOM,ipl),
a(a0), irt(irt0) {
testfix=false;
}
virtual bool solution(const Assignment& x) const {
double e = 0.0;
for (int i=0; i<a.size(); i++)
e += a[i]*x[i];
return cmp(e, irt, static_cast<double>(x[a.size()]));
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
int n = a.size();
Gecode::IntVarArgs y(n);
for (int i=n; i--; )
y[i] = x[i];
if (one(a))
Gecode::linear(home, y, irt, x[n], ipl);
else
Gecode::linear(home, a, y, irt, x[n], ipl);
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
Gecode::Reify r) {
int n = a.size();
Gecode::IntVarArgs y(n);
for (int i=n; i--; )
y[i] = x[i];
if (one(a))
Gecode::linear(home, y, irt, x[n], r, ipl);
else
Gecode::linear(home, a, y, irt, x[n], r, ipl);
}
};
class BoolInt : public Test {
protected:
Gecode::IntArgs a;
Gecode::IntRelType irt;
int c;
public:
BoolInt(const std::string& s, const Gecode::IntArgs& a0,
Gecode::IntRelType irt0, int c0)
: Test("Linear::Bool::Int::"+
str(irt0)+"::"+s+"::"+str(a0.size())+"::"+str(c0),
a0.size(),0,1,true,Gecode::IPL_DEF),
a(a0), irt(irt0), c(c0) {
testfix=false;
}
virtual bool solution(const Assignment& x) const {
double e = 0.0;
for (int i=0; i<x.size(); i++)
e += a[i]*x[i];
return cmp(e, irt, static_cast<double>(c));
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
Gecode::BoolVarArgs y(x.size());
for (int i=x.size(); i--; )
y[i]=Gecode::channel(home,x[i]);
if (one(a))
Gecode::linear(home, y, irt, c, Gecode::IPL_DEF);
else
Gecode::linear(home, a, y, irt, c, Gecode::IPL_DEF);
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
Gecode::Reify r) {
Gecode::BoolVarArgs y(x.size());
for (int i=x.size(); i--; )
y[i]=Gecode::channel(home,x[i]);
if (one(a))
Gecode::linear(home, y, irt, c, r, Gecode::IPL_DEF);
else
Gecode::linear(home, a, y, irt, c, r, Gecode::IPL_DEF);
}
};
class BoolVar : public Test {
protected:
Gecode::IntArgs a;
Gecode::IntRelType irt;
public:
BoolVar(const std::string& s,
int min, int max, const Gecode::IntArgs& a0,
Gecode::IntRelType irt0)
: Test("Linear::Bool::Var::"+str(irt0)+"::"+s,a0.size()+1,
min,max,true),
a(a0), irt(irt0) {
testfix=false;
}
virtual bool solution(const Assignment& x) const {
int n=x.size()-1;
for (int i=0; i<n; i++)
if ((x[i] < 0) || (x[i] > 1))
return false;
double e = 0.0;
for (int i=0; i<n; i++)
e += a[i]*x[i];
return cmp(e, irt, static_cast<double>(x[n]));
}
virtual bool ignore(const Assignment& x) const {
for (int i=x.size()-1; i--; )
if ((x[i] < 0) || (x[i] > 1))
return true;
return false;
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
int n=x.size()-1;
Gecode::BoolVarArgs y(n);
for (int i=n; i--; )
y[i]=Gecode::channel(home,x[i]);
if (one(a))
Gecode::linear(home, y, irt, x[n]);
else
Gecode::linear(home, a, y, irt, x[n]);
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
Gecode::Reify r) {
int n=x.size()-1;
Gecode::BoolVarArgs y(n);
for (int i=n; i--; )
y[i]=Gecode::channel(home,x[i]);
if (one(a))
Gecode::linear(home, y, irt, x[n], r);
else
Gecode::linear(home, a, y, irt, x[n], r);
}
};
class Create {
public:
Create(void) {
using namespace Gecode;
{
IntSet d1(-2,2);
const int dv2[] = {-4,-1,0,1,4};
IntSet d2(dv2,5);
const int dv3[] = {0,1500000000};
IntSet d3(dv3,2);
IntArgs a1({0});
for (IntRelTypes irts; irts(); ++irts) {
(void) new IntInt("11",d1,a1,irts.irt(),0);
(void) new IntVar("11",d1,a1,irts.irt());
(void) new IntInt("21",d2,a1,irts.irt(),0);
(void) new IntVar("21",d2,a1,irts.irt());
(void) new IntInt("31",d3,a1,irts.irt(),150000000);
}
(void) new IntInt("11",d1,a1,IRT_EQ,0,IPL_DOM);
(void) new IntVar("11",d1,a1,IRT_EQ,IPL_DOM);
(void) new IntInt("21",d2,a1,IRT_EQ,0,IPL_DOM);
(void) new IntVar("21",d2,a1,IRT_EQ,IPL_DOM);
const int av2[5] = {1,1,1,1,1};
const int av3[5] = {1,-1,-1,1,-1};
const int av4[5] = {2,3,5,7,11};
const int av5[5] = {-2,3,-5,7,-11};
for (int i=1; i<=5; i++) {
IntArgs a2(i, av2);
IntArgs a3(i, av3);
IntArgs a4(i, av4);
IntArgs a5(i, av5);
for (IntRelTypes irts; irts(); ++irts) {
(void) new IntInt("12",d1,a2,irts.irt(),0);
(void) new IntInt("13",d1,a3,irts.irt(),0);
(void) new IntInt("14",d1,a4,irts.irt(),0);
(void) new IntInt("15",d1,a5,irts.irt(),0);
(void) new IntInt("22",d2,a2,irts.irt(),0);
(void) new IntInt("23",d2,a3,irts.irt(),0);
(void) new IntInt("24",d2,a4,irts.irt(),0);
(void) new IntInt("25",d2,a5,irts.irt(),0);
(void) new IntInt("32",d3,a2,irts.irt(),1500000000);
if (i < 5) {
(void) new IntVar("12",d1,a2,irts.irt());
(void) new IntVar("13",d1,a3,irts.irt());
(void) new IntVar("14",d1,a4,irts.irt());
(void) new IntVar("15",d1,a5,irts.irt());
(void) new IntVar("22",d2,a2,irts.irt());
(void) new IntVar("23",d2,a3,irts.irt());
(void) new IntVar("24",d2,a4,irts.irt());
(void) new IntVar("25",d2,a5,irts.irt());
}
}
(void) new IntInt("12",d1,a2,IRT_EQ,0,IPL_DOM);
(void) new IntInt("13",d1,a3,IRT_EQ,0,IPL_DOM);
(void) new IntInt("14",d1,a4,IRT_EQ,0,IPL_DOM);
(void) new IntInt("15",d1,a5,IRT_EQ,0,IPL_DOM);
(void) new IntInt("22",d2,a2,IRT_EQ,0,IPL_DOM);
(void) new IntInt("23",d2,a3,IRT_EQ,0,IPL_DOM);
(void) new IntInt("24",d2,a4,IRT_EQ,0,IPL_DOM);
(void) new IntInt("25",d2,a5,IRT_EQ,0,IPL_DOM);
if (i < 4) {
(void) new IntVar("12",d1,a2,IRT_EQ,IPL_DOM);
(void) new IntVar("13",d1,a3,IRT_EQ,IPL_DOM);
(void) new IntVar("14",d1,a4,IRT_EQ,IPL_DOM);
(void) new IntVar("15",d1,a5,IRT_EQ,IPL_DOM);
}
}
}
{
const int av1[10] = {
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
};
const int av2[10] = {
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
};
for (int i=1; i<=10; i += 3) {
IntArgs a1(i, av1);
IntArgs a2(i, av2);
for (int c=0; c<=6; c++)
for (IntRelTypes irts; irts(); ++irts) {
(void) new BoolInt("1",a1,irts.irt(),c);
(void) new BoolInt("2",a2,irts.irt(),-c);
}
}
IntArgs a3({1,2,3,4,5});
IntArgs a4({-1,-2,-3,-4,-5});
IntArgs a5({-1,-2,1,2,4});
for (IntRelTypes irts; irts(); ++irts) {
for (int c=0; c<=16; c++) {
(void) new BoolInt("3",a3,irts.irt(),c);
(void) new BoolInt("4",a4,irts.irt(),-c);
(void) new BoolInt("5",a5,irts.irt(),c);
(void) new BoolInt("6",a5,irts.irt(),-c);
}
}
for (int i=1; i<=5; i += 2) {
IntArgs a1(i, av1);
IntArgs a2(i, av2);
for (IntRelTypes irts; irts(); ++irts) {
(void) new BoolVar("1::"+Test::str(i),0,5,a1,irts.irt());
(void) new BoolVar("2::"+Test::str(i),-5,0,a2,irts.irt());
}
}
IntArgs a6({1,2,3,4});
IntArgs a7({-1,-2,-3,-4});
IntArgs a8({-1,-2,1,2});
IntArgs a9({-1,-2,1,2,-3,3});
for (IntRelTypes irts; irts(); ++irts) {
(void) new BoolVar("6",0,10,a6,irts.irt());
(void) new BoolVar("7",-10,0,a7,irts.irt());
(void) new BoolVar("8",-3,3,a8,irts.irt());
(void) new BoolVar("9",-3,3,a9,irts.irt());
}
}
}
};
Create c;
}
}}
// STATISTICS: test-int
Gecode::BoolVarArgs
Passing Boolean variables.
Definition int.hh:712
Gecode::FloatVal::size
FloatNum size(void) const
Return size of float value (distance between maximum and minimum).
Definition val.hpp:78
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::Reify
Reification specification.
Definition int.hh:876
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::VarArray::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:926
Test::Int::Assignment
Base class for assignments
Definition int.hh:59
Test::Int::Assignment::size
int size(void) const
Return number of variables.
Definition int.hpp:46
Test::Int::IntRelTypes
Iterator for integer relation types.
Definition int.hh:368
Test::Int::Linear::BoolInt
Test linear relation over Boolean variables equal to constant
Definition linear.cpp:152
Test::Int::Linear::BoolInt::a
Gecode::IntArgs a
Coefficients.
Definition linear.cpp:155
Test::Int::Linear::BoolInt::solution
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition linear.cpp:171
Test::Int::Linear::BoolInt::c
int c
Righthand-side constant.
Definition linear.cpp:159
Test::Int::Linear::BoolInt::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition linear.cpp:178
Test::Int::Linear::BoolInt::BoolInt
BoolInt(const std::string &s, const Gecode::IntArgs &a0, Gecode::IntRelType irt0, int c0)
Create and register test.
Definition linear.cpp:162
Test::Int::Linear::BoolInt::irt
Gecode::IntRelType irt
Integer relation type to propagate.
Definition linear.cpp:157
Test::Int::Linear::BoolInt::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition linear.cpp:188
Test::Int::Linear::BoolVar
Test linear relation over Boolean variables equal to integer variable
Definition linear.cpp:201
Test::Int::Linear::BoolVar::irt
Gecode::IntRelType irt
Integer relation type to propagate.
Definition linear.cpp:206
Test::Int::Linear::BoolVar::BoolVar
BoolVar(const std::string &s, int min, int max, const Gecode::IntArgs &a0, Gecode::IntRelType irt0)
Create and register test.
Definition linear.cpp:209
Test::Int::Linear::BoolVar::ignore
virtual bool ignore(const Assignment &x) const
Test whether x is to be ignored
Definition linear.cpp:229
Test::Int::Linear::BoolVar::solution
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition linear.cpp:218
Test::Int::Linear::BoolVar::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition linear.cpp:236
Test::Int::Linear::BoolVar::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition linear.cpp:247
Test::Int::Linear::BoolVar::a
Gecode::IntArgs a
Coefficients.
Definition linear.cpp:204
Test::Int::Linear::Create
Help class to create and register tests.
Definition linear.cpp:261
Test::Int::Linear::Create::Create
Create(void)
Perform creation and registration.
Definition linear.cpp:264
Test::Int::Linear::IntInt
Test linear relation over integer variables
Definition linear.cpp:57
Test::Int::Linear::IntInt::irt
Gecode::IntRelType irt
Integer relation type to propagate.
Definition linear.cpp:62
Test::Int::Linear::IntInt::a
Gecode::IntArgs a
Coefficients.
Definition linear.cpp:60
Test::Int::Linear::IntInt::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition linear.cpp:85
Test::Int::Linear::IntInt::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition linear.cpp:92
Test::Int::Linear::IntInt::solution
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition linear.cpp:78
Test::Int::Linear::IntInt::IntInt
IntInt(const std::string &s, const Gecode::IntSet &d, const Gecode::IntArgs &a0, Gecode::IntRelType irt0, int c0, Gecode::IntPropLevel ipl=Gecode::IPL_BND)
Create and register test.
Definition linear.cpp:67
Test::Int::Linear::IntInt::c
int c
Result.
Definition linear.cpp:64
Test::Int::Linear::IntVar
Test linear relation over integer variables
Definition linear.cpp:102
Test::Int::Linear::IntVar::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition linear.cpp:138
Test::Int::Linear::IntVar::IntVar
IntVar(const std::string &s, const Gecode::IntSet &d, const Gecode::IntArgs &a0, Gecode::IntRelType irt0, Gecode::IntPropLevel ipl=Gecode::IPL_BND)
Create and register test.
Definition linear.cpp:110
Test::Int::Linear::IntVar::a
Gecode::IntArgs a
Coefficients.
Definition linear.cpp:105
Test::Int::Linear::IntVar::solution
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition linear.cpp:120
Test::Int::Linear::IntVar::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition linear.cpp:127
Test::Int::Linear::IntVar::irt
Gecode::IntRelType irt
Integer relation type to propagate.
Definition linear.cpp:107
Test::Int::Test::testfix
bool testfix
Whether to perform fixpoint test.
Definition int.hh:240
Test::Int::Test::ipl
Gecode::IntPropLevel ipl
Propagation level.
Definition int.hh:234
Test::Int::Test::str
static std::string str(Gecode::IntPropLevel ipl)
Map integer propagation level to string.
Definition int.hpp:209
Test::Int::Test::cmp
static bool cmp(T x, Gecode::IntRelType r, T y)
Compare x and y with respect to r.
Definition int.hpp:285
Gecode::linear
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition linear.cpp:41
Gecode::IntRelType
IntRelType
Relation types for integers.
Definition int.hh:925
Gecode::IntPropLevel
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:974
Gecode::IRT_EQ
@ IRT_EQ
Equality ( ).
Definition int.hh:926
Gecode::IPL_DOM
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:979
Gecode::IPL_DEF
@ IPL_DEF
Simple propagation levels.
Definition int.hh:976
Gecode::IPL_BND
@ IPL_BND
Bounds propagation.
Definition int.hh:978
minimodel.hh
Gecode
Gecode toplevel namespace
Gecode::channel
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition channel.cpp:41
Test::Int::Linear
Tests for linear constraints
Definition linear.cpp:41
Test::Int::Linear::c
Create c
Definition linear.cpp:392
Test::Int::Linear::one
bool one(const Gecode::IntArgs &a)
Check whether a has only one coefficients.
Definition linear.cpp:44
Test::Int
Testing finite domain integers.
Definition int.cpp:40
Test
General test support.
Definition afc.cpp:39
Test::r
Region r
Definition region.cpp:65
int.hh