Generated on Mon Feb 8 2021 00:00:00 for Gecode by doxygen 1.8.20
post.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2002
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <algorithm>
35 #include <climits>
36 
37 namespace Gecode { namespace Int { namespace Linear {
38 
39  template<class View>
40  inline void
41  estimate(Term<View>* t, int n, int c, int& l, int &u) {
42  long long int min = c;
43  long long int max = c;
44  for (int i=0; i<n; i++) {
45  long long int a = t[i].a;
46  if (a > 0) {
47  min += a*t[i].x.min();
48  max += a*t[i].x.max();
49  } else {
50  max += a*t[i].x.min();
51  min += a*t[i].x.max();
52  }
53  }
54  if (min < Limits::min)
55  min = Limits::min;
56  if (min > Limits::max)
57  min = Limits::max;
58  l = static_cast<int>(min);
59  if (max < Limits::min)
60  max = Limits::min;
61  if (max > Limits::max)
62  max = Limits::max;
63  u = static_cast<int>(max);
64  }
65 
67  template<class View>
68  class TermByView {
69  public:
70  forceinline bool
71  operator ()(const Term<View>& a, const Term<View>& b) {
72  return a.x < b.x;
73  }
74  };
75 
77  template<class View>
78  class TermBySizePos {
79  public:
80  forceinline bool
81  operator ()(const Term<View>& a, const Term<View>& b) {
82  assert((a.a > 0) && (b.a > 0));
83  return (a.a > b.a) || ((a.a == b.a) && (a.p < b.p));
84  }
85  };
86 
88  inline int
89  gcd(int a, int b) {
90  if (b > a)
91  std::swap(a,b);
92  while (b > 0) {
93  int t = b; b = a % b; a = t;
94  }
95  return a;
96  }
97 
98 
99 
124  template<class View>
125  inline bool
127  Term<View>* &t_p, int &n_p,
128  Term<View>* &t_n, int &n_n,
129  int& g) {
130  // Number terms by position
131  for (int i=0; i<n; i++)
132  t[i].p = i;
133 
134  /*
135  * Join coefficients for aliased variables:
136  *
137  */
138  {
139  // Group same variables
140  TermByView<View> tl;
141  Support::quicksort<Term<View>,TermByView<View>>(t,n,tl);
142 
143  // Join adjacent variables
144  int i = 0;
145  int j = 0;
146  while (i < n) {
147  Limits::check(t[i].a,"Int::linear");
148  long long int a = t[i].a;
149  int p = t[i].p;
150  View x = t[i].x;
151  while ((++i < n) && (t[i].x == x)) {
152  a += t[i].a;
153  p = std::min(p,t[i].p);
154  Limits::check(a,"Int::linear");
155  }
156  if (a != 0) {
157  t[j].a = static_cast<int>(a); t[j].x = x; t[j].p = p; j++;
158  }
159  }
160  n = j;
161  }
162 
163  /*
164  * Partition into positive/negative coefficents
165  *
166  */
167  if (n > 0) {
168  int i = 0;
169  int j = n-1;
170  while (true) {
171  while ((t[j].a < 0) && (--j >= 0)) ;
172  while ((t[i].a > 0) && (++i < n)) ;
173  if (j <= i) break;
174  std::swap(t[i],t[j]);
175  }
176  t_p = t; n_p = i;
177  t_n = t+n_p; n_n = n-n_p;
178  } else {
179  t_p = t; n_p = 0;
180  t_n = t; n_n = 0;
181  }
182 
183  /*
184  * Make all coefficients positive
185  *
186  */
187  for (int i=0; i<n_n; i++)
188  t_n[i].a = -t_n[i].a;
189 
190  /*
191  * Sort terms into canonical order (to avoid indeterminstic order)
192  */
193  {
195  Support::quicksort<Term<View>,TermBySizePos<View>>(t_p,n_p,tl);
196  Support::quicksort<Term<View>,TermBySizePos<View>>(t_n,n_n,tl);
197  }
198 
199  /*
200  * Compute greatest common divisor
201  *
202  */
203  if ((n > 0) && (g > 0)) {
204  g = t[0].a;
205  for (int i=1; (g > 1) && (i < n); i++)
206  g = gcd(t[i].a,g);
207  if (g > 1)
208  for (int i=n; i--; )
209  t[i].a /= g;
210  } else {
211  g = 1;
212  }
213 
214  /*
215  * Test for unit coefficients only
216  *
217  */
218  for (int i=0; i<n; i++)
219  if (t[i].a != 1)
220  return false;
221  return true;
222  }
223 
224 }}}
225 
226 // STATISTICS: int-post
227 
Post propagator for SetVar x
Definition: set.hh:767
Sort linear terms by view.
Definition: post.hpp:68
Class for describing linear term .
Definition: linear.hh:1336
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
NodeType t
Type of node.
Definition: bool-expr.cpp:230
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
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
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
bool operator()(const Term< View > &a, const Term< View > &b)
Definition: post.hpp:71
Gecode toplevel namespace
int gcd(int a, int b)
Compute the greatest common divisor of a and b.
Definition: post.hpp:89
union Gecode::@602::NNF::@65 u
Union depending on nodetype t.
Sort linear terms by coefficient size and original position.
Definition: post.hpp:78
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Definition: irt.hpp:37
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
const int max
Largest allowed integer value.
Definition: int.hh:116
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
bool operator()(const Term< View > &a, const Term< View > &b)
Definition: post.hpp:81
void estimate(Term< View > *t, int n, int c, int &l, int &u)
Estimate lower and upper bounds.
Definition: post.hpp:41
const int min
Smallest allowed integer value.
Definition: int.hh:118
#define forceinline
Definition: config.hpp:192
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
Gecode::FloatVal c(-8, 8)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Gecode::IntArgs i({1, 2, 3, 4})
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232