post.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>
*
* Copyright:
* Christian Schulte, 2002
*
* 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>
namespace Gecode { namespace Int { namespace Linear {
template<class View>
inline void
estimate(Term<View>* t, int n, int c, int& l, int &u) {
long long int min = c;
long long int max = c;
for (int i=0; i<n; i++) {
long long int a = t[i].a;
if (a > 0) {
min += a*t[i].x.min();
max += a*t[i].x.max();
} else {
max += a*t[i].x.min();
min += a*t[i].x.max();
}
}
if (min < Limits::min)
min = Limits::min;
if (min > Limits::max)
min = Limits::max;
l = static_cast<int>(min);
if (max < Limits::min)
max = Limits::min;
if (max > Limits::max)
max = Limits::max;
u = static_cast<int>(max);
}
template<class View>
class TermByView {
public:
forceinline bool
operator ()(const Term<View>& a, const Term<View>& b) {
return a.x < b.x;
}
};
template<class View>
class TermBySizePos {
public:
forceinline bool
operator ()(const Term<View>& a, const Term<View>& b) {
assert((a.a > 0) && (b.a > 0));
return (a.a > b.a) || ((a.a == b.a) && (a.p < b.p));
}
};
inline int
gcd(int a, int b) {
if (b > a)
std::swap(a,b);
while (b > 0) {
int t = b; b = a % b; a = t;
}
return a;
}
template<class View>
inline bool
normalize(Term<View>* t, int &n,
Term<View>* &t_p, int &n_p,
Term<View>* &t_n, int &n_n,
int& g) {
// Number terms by position
for (int i=0; i<n; i++)
t[i].p = i;
/*
* Join coefficients for aliased variables:
*
*/
{
// Group same variables
TermByView<View> tl;
Support::quicksort<Term<View>,TermByView<View>>(t,n,tl);
// Join adjacent variables
int i = 0;
int j = 0;
while (i < n) {
Limits::check(t[i].a,"Int::linear");
long long int a = t[i].a;
int p = t[i].p;
View x = t[i].x;
while ((++i < n) && (t[i].x == x)) {
a += t[i].a;
p = std::min(p,t[i].p);
Limits::check(a,"Int::linear");
}
if (a != 0) {
t[j].a = static_cast<int>(a); t[j].x = x; t[j].p = p; j++;
}
}
n = j;
}
/*
* 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=0; i<n_n; i++)
t_n[i].a = -t_n[i].a;
/*
* Sort terms into canonical order (to avoid indeterminstic order)
*/
{
TermBySizePos<View> tl;
Support::quicksort<Term<View>,TermBySizePos<View>>(t_p,n_p,tl);
Support::quicksort<Term<View>,TermBySizePos<View>>(t_n,n_n,tl);
}
/*
* Compute greatest common divisor
*
*/
if ((n > 0) && (g > 0)) {
g = t[0].a;
for (int i=1; (g > 1) && (i < n); i++)
g = gcd(t[i].a,g);
if (g > 1)
for (int i=n; i--; )
t[i].a /= g;
} else {
g = 1;
}
/*
* Test for unit coefficients only
*
*/
for (int i=0; i<n; i++)
if (t[i].a != 1)
return false;
return true;
}
}}}
// STATISTICS: int-post
Gecode::FloatVal::x
FloatValImpType x
Implementation of float value.
Definition float.hh:425
Gecode::Int::Linear::TermBySizePos
Sort linear terms by coefficient size and original position.
Definition post.hpp:78
Gecode::Int::Linear::TermBySizePos::operator()
bool operator()(const Term< View > &a, const Term< View > &b)
Definition post.hpp:81
Gecode::Int::Linear::TermByView
Sort linear terms by view.
Definition post.hpp:68
Gecode::Int::Linear::TermByView::operator()
bool operator()(const Term< View > &a, const Term< View > &b)
Definition post.hpp:71
Gecode::Int::Linear::Term
Class for describing linear term .
Definition linear.hh:1336
Gecode::Int::Linear::Term::x
View x
View.
Definition linear.hh:1341
Gecode::Int::Linear::Term::a
int a
Coefficient.
Definition linear.hh:1339
Gecode::View
Gecode::Int::Limits::check
void check(int n, const char *l)
Check whether n is in range, otherwise throw out of limits with information l.
Definition limits.hpp:46
Gecode::Int::Limits::min
const int min
Smallest allowed integer value.
Definition int.hh:118
Gecode::Int::Limits::max
const int max
Largest allowed integer value.
Definition int.hh:116
Gecode::Int::Linear
Linear propagators
Gecode::Int::Linear::estimate
void estimate(Term< View > *t, int n, int c, int &l, int &u)
Estimate lower and upper bounds.
Definition post.hpp:41
Gecode::Int::Linear::gcd
int gcd(int a, int b)
Compute the greatest common divisor of a and b.
Definition post.hpp:89
Gecode::Int::Linear::normalize
bool normalize(Term< View > *t, int &n, Term< View > *&t_p, int &n_p, Term< View > *&t_n, int &n_n, int &g)
Normalize linear integer constraints.
Definition post.hpp:126
Gecode::Int
Finite domain integers.
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