Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
37namespace 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)
56 if (min > Limits::max)
58 l = static_cast<int>(min);
59 if (max < Limits::min)
61 if (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>
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
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 {
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
FloatValImpType x
Implementation of float value.
Definition float.hh:425
Sort linear terms by coefficient size and original position.
Definition post.hpp:78
bool operator()(const Term< View > &a, const Term< View > &b)
Definition post.hpp:81
Sort linear terms by view.
Definition post.hpp:68
bool operator()(const Term< View > &a, const Term< View > &b)
Definition post.hpp:71
Class for describing linear term .
Definition linear.hh:1336
int a
Coefficient.
Definition linear.hh:1339
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 int min
Smallest allowed integer value.
Definition int.hh:118
const int max
Largest allowed integer value.
Definition int.hh:116
Linear propagators
void estimate(Term< View > *t, int n, int c, int &l, int &u)
Estimate lower and upper bounds.
Definition post.hpp:41
int gcd(int a, int b)
Compute the greatest common divisor of a and b.
Definition post.hpp:89
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
Finite domain integers.
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode toplevel namespace
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
Definition set.hh:773
#define forceinline
Definition config.hpp:194