main page
modules
namespaces
classes
files
Gecode home
Generated on Mon Feb 8 2021 00:00:00 for Gecode by
doxygen
1.8.20
gecode
int
linear
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
126
normalize
(
Term<View>
*
t
,
int
&
n
,
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
{
194
TermBySizePos<View>
tl;
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
Gecode::x
Post propagator for SetVar x
Definition:
set.hh:767
Gecode::Int::Linear::TermByView
Sort linear terms by view.
Definition:
post.hpp:68
Gecode::Int::Linear::Term
Class for describing linear term .
Definition:
linear.hh:1336
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:49
t
NodeType t
Type of node.
Definition:
bool-expr.cpp:230
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::Float::Limits::min
const FloatNum min
Smallest allowed float value.
Definition:
float.hh:846
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::Linear::TermByView::operator()
bool operator()(const Term< View > &a, const Term< View > &b)
Definition:
post.hpp:71
Gecode
Gecode toplevel namespace
Gecode::Int::Linear::gcd
int gcd(int a, int b)
Compute the greatest common divisor of a and b.
Definition:
post.hpp:89
u
union Gecode::@602::NNF::@65 u
Union depending on nodetype t.
Gecode::Int::Linear::TermBySizePos
Sort linear terms by coefficient size and original position.
Definition:
post.hpp:78
Gecode::swap
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Definition:
irt.hpp:37
b
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Gecode::Int::Limits::max
const int max
Largest allowed integer value.
Definition:
int.hh:116
a
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
l
NNF * l
Left subtree.
Definition:
bool-expr.cpp:240
Gecode::Int::Linear::TermBySizePos::operator()
bool operator()(const Term< View > &a, const Term< View > &b)
Definition:
post.hpp:81
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::Limits::min
const int min
Smallest allowed integer value.
Definition:
int.hh:118
forceinline
#define forceinline
Definition:
config.hpp:192
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:67
Test::Float::Arithmetic::c
Gecode::FloatVal c(-8, 8)
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:234
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
p
int p
Number of positive literals for node type.
Definition:
bool-expr.cpp:232