post.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>
* Vincent Barichard <Vincent.Barichard@univ-angers.fr>
*
* Copyright:
* Christian Schulte, 2002
* 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.
*
*/
#include <algorithm>
#include <climits>
#include <gecode/float/linear.hh>
#include <gecode/float/rel.hh>
namespace Gecode { namespace Float { namespace Linear {
void
estimate(Term* t, int n, FloatVal c, FloatNum& l, FloatNum &u) {
FloatVal est = c;
for (int i=n; i--; )
est += t[i].a * t[i].x.domain();
FloatNum min = est.min();
FloatNum max = est.max();
if (min < Limits::min)
min = Limits::min;
if (min > Limits::max)
min = Limits::max;
l = min;
if (max < Limits::min)
max = Limits::min;
if (max > Limits::max)
max = Limits::max;
u = max;
}
forceinline bool
overflow(Term* t, int n, FloatVal c) {
FloatVal est = c;
for (int i=n; i--; )
est += t[i].a * t[i].x.domain();
FloatNum min = est.min();
FloatNum max = est.max();
return ((min < Limits::min) || (min > Limits::max) ||
(max < Limits::min) || (max > Limits::max));
}
class TermLess {
public:
forceinline bool
operator ()(const Term& a, const Term& b) {
return a.x < b.x;
}
};
FloatView
extend(Home home, Region& r, Term*& t, int& n) {
FloatNum min, max;
estimate(t,n,0.0,min,max);
FloatVar x(home,min,max);
Term* et = r.alloc<Term>(n+1);
for (int i=n; i--; )
et[i] = t[i];
et[n].a=-1.0; et[n].x=x;
t=et; n++;
return x;
}
template<class View>
forceinline void
post_nary(Home home,
ViewArray<View>& x, ViewArray<View>& y, FloatRelType frt,
FloatVal c) {
switch (frt) {
case FRT_EQ:
GECODE_ES_FAIL((Eq<View,View >::post(home,x,y,c)));
break;
case FRT_LQ:
GECODE_ES_FAIL((Lq<View,View >::post(home,x,y,c)));
break;
default: GECODE_NEVER;
}
}
void
dopost(Home home, Term* t, int n, FloatRelType frt, FloatVal c) {
Limits::check(c,"Float::linear");
for (int i=n; i--; ) {
if ((t[i].a.min() < 0.0) && (t[i].a.max() > 0.0))
throw ValueMixedSign("Float::linear[coefficient]");
if (t[i].x.assigned()) {
c -= t[i].a * t[i].x.val();
t[i]=t[--n];
}
}
if ((c < Limits::min) || (c > Limits::max) || overflow(t, n, c))
throw OutOfLimits("Float::linear");
/*
* Join coefficients for aliased variables:
*
*/
{
// Group same variables
TermLess tl;
Support::quicksort<Term,TermLess>(t,n,tl);
// Join adjacent variables
int i = 0;
int j = 0;
while (i < n) {
Limits::check(t[i].a,"Float::linear");
FloatVal a = t[i].a;
FloatView x = t[i].x;
while ((++i < n) && (t[i].x == x)) {
a += t[i].a;
Limits::check(a,"Float::linear");
}
if (a != 0.0) {
t[j].a = a; t[j].x = x; j++;
}
}
n = j;
}
Term *t_p, *t_n;
int n_p, n_n;
/*
* Partition into positive/negative coefficents
*
*/
if (n > 0) {
int i = 0;
int j = n-1;
while (true) {
while ((t[j].a < 0) && (--j >= 0)) ;
while ((t[i].a > 0) && (++i < n)) ;
if (j <= i) break;
std::swap(t[i],t[j]);
}
t_p = t; n_p = i;
t_n = t+n_p; n_n = n-n_p;
} else {
t_p = t; n_p = 0;
t_n = t; n_n = 0;
}
/*
* Make all coefficients positive
*
*/
for (int i=n_n; i--; )
t_n[i].a = -t_n[i].a;
if (frt == FRT_GQ) {
frt = FRT_LQ;
std::swap(n_p,n_n); std::swap(t_p,t_n); c = -c;
}
if (n == 0) {
switch (frt) {
case FRT_EQ: if (!c.in(0.0)) home.fail(); break;
case FRT_LQ: if (c.max() < 0.0) home.fail(); break;
default: GECODE_NEVER;
}
return;
}
/*
* Test for unit coefficients only
*
*/
bool is_unit = true;
for (int i=n; i--; )
if (!(t[i].a == 1.0)) {
is_unit = false;
break;
}
if (is_unit) {
// Unit coefficients
ViewArray<FloatView> x(home,n_p);
for (int i = n_p; i--; )
x[i] = t_p[i].x;
ViewArray<FloatView> y(home,n_n);
for (int i = n_n; i--; )
y[i] = t_n[i].x;
post_nary<FloatView>(home,x,y,frt,c);
} else {
// Arbitrary coefficients
ViewArray<ScaleView> x(home,n_p);
for (int i = n_p; i--; )
x[i] = ScaleView(t_p[i].a,t_p[i].x);
ViewArray<ScaleView> y(home,n_n);
for (int i = n_n; i--; )
y[i] = ScaleView(t_n[i].a,t_n[i].x);
post_nary<ScaleView>(home,x,y,frt,c);
}
}
void
post(Home home, Term* t, int n, FloatRelType frt, FloatVal c) {
Region re;
switch (frt) {
case FRT_EQ: case FRT_LQ: case FRT_GQ:
break;
case FRT_NQ: case FRT_LE: case FRT_GR:
rel(home, extend(home,re,t,n), frt, c);
frt=FRT_EQ; c=0.0;
break;
default:
throw UnknownRelation("Float::linear");
}
dopost(home, t, n, frt, c);
}
void
post(Home home, Term* t, int n, FloatRelType frt, FloatVal c, Reify r) {
Region re;
rel(home, extend(home,re,t,n), frt, c, r);
dopost(home, t, n, FRT_EQ, 0.0);
}
}}}
// STATISTICS: float-post
Gecode::FloatVal
Float value type.
Definition float.hh:334
Gecode::FloatVal::x
FloatValImpType x
Implementation of float value.
Definition float.hh:425
Gecode::FloatVal::in
bool in(FloatNum n) const
Test whether n is included.
Definition val.hpp:96
Gecode::FloatVal::max
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition val.hpp:386
Gecode::FloatVal::min
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition val.hpp:398
Gecode::FloatVar
Float variables.
Definition float.hh:870
Gecode::Float::FloatView
Float view for float variables.
Definition view.hpp:52
Gecode::Float::FloatView::val
FloatVal val(void) const
Return assigned value.
Definition float.hpp:72
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::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::TermLess
Sort linear terms by view.
Definition post.cpp:75
Gecode::Float::Linear::TermLess::operator()
bool operator()(const Term &a, const Term &b)
Definition post.cpp:78
Gecode::Float::Linear::Term
Class for describing linear term .
Definition linear.hh:166
Gecode::Float::Linear::Term::a
FloatVal a
Coefficient.
Definition linear.hh:169
Gecode::Float::Linear::Term::x
FloatView x
View.
Definition linear.hh:171
Gecode::Float::OutOfLimits
Exception: Value out of limits
Definition exception.hpp:46
Gecode::Float::ScaleView
Scale float view.
Definition view.hpp:395
Gecode::Float::UnknownRelation
Exception: Unknown relation passed as argument
Definition exception.hpp:88
Gecode::Float::ValueMixedSign
Exception: Value with mixed sign
Definition exception.hpp:53
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Home::fail
void fail(void)
Mark space as failed.
Definition core.hpp:4039
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Reify
Reification specification.
Definition int.hh:876
Gecode::ViewArray
View arrays.
Definition array.hpp:253
linear.hh
rel.hh
Gecode::Float::Linear::post
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition post.cpp:238
GECODE_ES_FAIL
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition macros.hpp:103
Gecode::rel
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
Gecode::FloatNum
double FloatNum
Floating point number base type.
Definition float.hh:106
Gecode::FloatRelType
FloatRelType
Relation types for floats.
Definition float.hh:1068
Gecode::FRT_EQ
@ FRT_EQ
Equality ( ).
Definition float.hh:1069
Gecode::FRT_GR
@ FRT_GR
Greater ( ).
Definition float.hh:1074
Gecode::FRT_NQ
@ FRT_NQ
Disequality ( ).
Definition float.hh:1070
Gecode::FRT_LE
@ FRT_LE
Less ( ).
Definition float.hh:1072
Gecode::FRT_LQ
@ FRT_LQ
Less or equal ( ).
Definition float.hh:1071
Gecode::FRT_GQ
@ FRT_GQ
Greater or equal ( ).
Definition float.hh:1073
Gecode::Float::Limits::max
const FloatNum max
Largest allowed float value.
Definition float.hh:844
Gecode::Float::Limits::min
const FloatNum min
Smallest allowed float value.
Definition float.hh:846
Gecode::Float::Limits::check
void check(const FloatVal &n, const char *l)
Check whether float n is a valid number, otherwise throw out of limits exception with information l.
Definition limits.hpp:44
Gecode::Float::Linear
Linear propagators
Gecode::Float::Linear::extend
FloatView extend(Home home, Region &r, Term *&t, int &n)
Extend terms by adding view for result.
Definition post.cpp:85
Gecode::Float::Linear::overflow
bool overflow(Term *t, int n, FloatVal c)
Definition post.cpp:64
Gecode::Float::Linear::post_nary
void post_nary(Home home, ViewArray< View > &x, ViewArray< View > &y, FloatRelType frt, FloatVal c)
Posting n-ary propagators.
Definition post.cpp:104
Gecode::Float::Linear::dopost
void dopost(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Definition post.cpp:119
Gecode::Float::Linear::estimate
void estimate(Term *t, int n, FloatVal c, FloatNum &l, FloatNum &u)
Estimate lower and upper bounds.
Definition post.cpp:45
Gecode::Float
Floating point numbers.
Gecode::Support::quicksort
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode
Gecode toplevel namespace
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:67
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
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56