main page
modules
namespaces
classes
files
Gecode home
Generated on Mon Sep 17 2012 22:20:39 for Gecode by
doxygen
1.8.1.1
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
* Last modified:
10
* $Date: 2011-08-12 23:27:20 +1000 (Fri, 12 Aug 2011) $ by $Author: tack $
11
* $Revision: 12285 $
12
*
13
* This file is part of Gecode, the generic constraint
14
* development environment:
15
* http://www.gecode.org
16
*
17
* Permission is hereby granted, free of charge, to any person obtaining
18
* a copy of this software and associated documentation files (the
19
* "Software"), to deal in the Software without restriction, including
20
* without limitation the rights to use, copy, modify, merge, publish,
21
* distribute, sublicense, and/or sell copies of the Software, and to
22
* permit persons to whom the Software is furnished to do so, subject to
23
* the following conditions:
24
*
25
* The above copyright notice and this permission notice shall be
26
* included in all copies or substantial portions of the Software.
27
*
28
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35
*
36
*/
37
38
#include <algorithm>
39
#include <climits>
40
41
namespace
Gecode {
namespace
Int {
namespace
Linear {
42
43
template
<
class
View>
44
inline
void
45
estimate
(
Term<View>
* t,
int
n,
int
c
,
int
& l,
int
&u) {
46
double
min
=
c
;
47
double
max
=
c
;
48
for
(
int
i
=n;
i
--; ) {
49
double
a
= t[
i
].
a
;
50
if
(a > 0) {
51
min += a*t[
i
].
x
.min();
52
max += a*t[
i
].
x
.max();
53
}
else
{
54
max += a*t[
i
].
x
.min();
55
min += a*t[
i
].
x
.max();
56
}
57
}
58
if
(min <
Limits::min
)
59
min =
Limits::min
;
60
if
(min >
Limits::max
)
61
min =
Limits::max
;
62
l =
static_cast<
int
>
(
min
);
63
if
(max <
Limits::min
)
64
max =
Limits::min
;
65
if
(max >
Limits::max
)
66
max =
Limits::max
;
67
u =
static_cast<
int
>
(
max
);
68
}
69
71
template
<
class
View>
72
class
TermLess
{
73
public
:
74
forceinline
bool
75
operator ()
(
const
Term<View>
&
a
,
const
Term<View>
&
b
) {
76
return
before
(a.
x
,b.
x
);
77
}
78
};
79
80
template
<
class
View>
81
inline
bool
82
normalize
(
Term<View>
* t,
int
&n,
83
Term<View>
* &t_p,
int
&n_p,
84
Term<View>
* &t_n,
int
&n_n) {
85
/*
86
* Join coefficients for aliased variables:
87
*
88
*/
89
{
90
// Group same variables
91
TermLess<View>
tl;
92
Support::quicksort<Term<View>,
TermLess<View>
>(t,n,tl);
93
94
// Join adjacent variables
95
int
i
= 0;
96
int
j = 0;
97
while
(i < n) {
98
Limits::check
(t[i].
a
,
"Int::linear"
);
99
double
a = t[
i
].a;
100
View x = t[
i
].x;
101
while
((++i < n) &&
same
(t[i].x,x)) {
102
a += t[
i
].a;
103
Limits::check
(a,
"Int::linear"
);
104
}
105
if
(a != 0.0) {
106
t[j].a =
static_cast<
int
>
(
a
); t[j].x = x; j++;
107
}
108
}
109
n = j;
110
}
111
112
/*
113
* Partition into positive/negative coefficents
114
*
115
*/
116
if
(n > 0) {
117
int
i
= 0;
118
int
j = n-1;
119
while
(
true
) {
120
while
((t[j].
a
< 0) && (--j >= 0)) ;
121
while
((t[i].
a
> 0) && (++i < n)) ;
122
if
(j <= i)
break
;
123
std::swap(t[i],t[j]);
124
}
125
t_p = t; n_p =
i
;
126
t_n = t+n_p; n_n = n-n_p;
127
}
else
{
128
t_p = t; n_p = 0;
129
t_n = t; n_n = 0;
130
}
131
132
/*
133
* Make all coefficients positive
134
*
135
*/
136
for
(
int
i
=n_n;
i
--; )
137
t_n[
i
].
a
= -t_n[
i
].
a
;
138
139
/*
140
* Test for unit coefficients only
141
*
142
*/
143
for
(
int
i
=n;
i
--; )
144
if
(t[
i
].
a
!= 1)
145
return
false
;
146
return
true
;
147
}
148
149
}}}
150
151
// STATISTICS: int-post
152