main page
modules
namespaces
classes
files
Gecode home
Generated on Sat Nov 9 2013 19:18:26 for Gecode by
doxygen
1.8.4
gecode
float
linear
nary.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
* Vincent Barichard <Vincent.Barichard@univ-angers.fr>
6
*
7
* Copyright:
8
* Christian Schulte, 2003
9
* Vincent Barichard, 2012
10
*
11
* Last modified:
12
* $Date: 2013-02-13 16:01:33 +0100 (Wed, 13 Feb 2013) $ by $Author: vbarichard $
13
* $Revision: 13289 $
14
*
15
* This file is part of Gecode, the generic constraint
16
* development environment:
17
* http://www.gecode.org
18
*
19
* Permission is hereby granted, free of charge, to any person obtaining
20
* a copy of this software and associated documentation files (the
21
* "Software"), to deal in the Software without restriction, including
22
* without limitation the rights to use, copy, modify, merge, publish,
23
* distribute, sublicense, and/or sell copies of the Software, and to
24
* permit persons to whom the Software is furnished to do so, subject to
25
* the following conditions:
26
*
27
* The above copyright notice and this permission notice shall be
28
* included in all copies or substantial portions of the Software.
29
*
30
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37
*
38
*/
39
40
namespace
Gecode {
namespace
Float {
namespace
Linear {
41
42
/*
43
* Linear propagators
44
*
45
*/
46
template
<
class
P,
class
N, PropCond pc>
47
forceinline
48
Lin<P,N,pc>::Lin
(
Home
home,
ViewArray<P>
& x0,
ViewArray<N>
& y0,
FloatVal
c0)
49
:
Propagator
(home),
x
(x0), y(y0),
c
(c0) {
50
x
.
subscribe
(home,*
this
,pc);
51
y
.
subscribe
(home,*
this
,pc);
52
}
53
54
template
<
class
P,
class
N, PropCond pc>
55
forceinline
56
Lin<P,N,pc>::Lin
(
Space
& home,
bool
share,
Lin<P,N,pc>
&
p
)
57
:
Propagator
(home,share,p),
c
(p.
c
) {
58
x
.
update
(home,share,p.
x
);
59
y
.
update
(home,share,p.
y
);
60
}
61
62
template
<
class
P,
class
N, PropCond pc>
63
PropCost
64
Lin<P,N,pc>::cost
(
const
Space
&,
const
ModEventDelta
&)
const
{
65
return
PropCost::linear
(
PropCost::LO
,
x
.size()+y.size());
66
}
67
68
template
<
class
P,
class
N, PropCond pc>
69
forceinline
size_t
70
Lin<P,N,pc>::dispose
(
Space
& home) {
71
x
.cancel(home,*
this
,pc);
72
y.cancel(home,*
this
,pc);
73
(void)
Propagator::dispose
(home);
74
return
sizeof
(*this);
75
}
76
77
78
/*
79
* Computing bounds
80
*
81
*/
82
// template<class View>
83
// void
84
// bounds_p(Rounding& r, ModEventDelta med, ViewArray<View>& x, FloatVal& c, FloatNum& sl, FloatNum& su) {
85
// int n = x.size();
86
// if (FloatView::me(med) == ME_FLOAT_VAL) {
87
// for (int i = n; i--; ) {
88
// if (x[i].assigned()) {
89
// c -= x[i].val(); x[i] = x[--n];
90
// } else {
91
// sl = r.sub_up(sl,x[i].min()); su = r.sub_down(su,x[i].max());
92
// }
93
// }
94
// x.size(n);
95
// } else {
96
// for (int i = n; i--; ) {
97
// sl = r.sub_up(sl,x[i].min()); su = r.sub_down(su,x[i].max());
98
// }
99
// }
100
// }
101
//
102
// template<class View>
103
// void
104
// bounds_n(Rounding& r, ModEventDelta med, ViewArray<View>& y, FloatVal& c, FloatNum& sl, FloatNum& su) {
105
// int n = y.size();
106
// if (FloatView::me(med) == ME_FLOAT_VAL) {
107
// for (int i = n; i--; ) {
108
// if (y[i].assigned()) {
109
// c += y[i].val(); y[i] = y[--n];
110
// } else {
111
// sl = r.add_up(sl,y[i].max()); su = r.add_down(su,y[i].min());
112
// }
113
// }
114
// y.size(n);
115
// } else {
116
// for (int i = n; i--; ) {
117
// sl = r.add_up(sl,y[i].max()); su = r.add_down(su,y[i].min());
118
// }
119
// }
120
// }
121
122
template
<
class
View>
123
void
124
eliminate_p
(
ModEventDelta
med,
ViewArray<View>
&
x
,
FloatVal
&
c
) {
125
int
n
= x.
size
();
126
127
if
(
FloatView::me
(med) ==
ME_FLOAT_VAL
) {
128
for
(
int
i
= n;
i
--; ) {
129
if
(x[
i
].
assigned
()) {
130
c -= x[
i
].val(); x[
i
] = x[--
n
];
131
}
132
}
133
x.
size
(n);
134
}
135
}
136
137
template
<
class
View>
138
void
139
eliminate_n
(
ModEventDelta
med,
ViewArray<View>
& y,
FloatVal
&
c
) {
140
int
n
= y.
size
();
141
if
(
FloatView::me
(med) ==
ME_FLOAT_VAL
) {
142
for
(
int
i
= n;
i
--; ) {
143
if
(y[
i
].
assigned
()) {
144
c += y[
i
].val(); y[
i
] = y[--
n
];
145
}
146
}
147
y.
size
(n);
148
}
149
}
150
151
forceinline
bool
152
infty
(
const
FloatNum
&
n
) {
153
return
((n ==
std::numeric_limits<FloatNum>::infinity
()) ||
154
(n == -
std::numeric_limits<FloatNum>::infinity
()));
155
}
156
157
/*
158
* Bound consistent linear equation
159
*
160
*/
161
162
template
<
class
P,
class
N>
163
forceinline
164
Eq<P,N>::Eq
(
Home
home,
ViewArray<P>
&
x
,
ViewArray<N>
& y,
FloatVal
c
)
165
:
Lin
<P,N,
PC_FLOAT_BND
>(home,x,y,c) {}
166
167
template
<
class
P,
class
N>
168
ExecStatus
169
Eq<P,N>::post
(
Home
home,
ViewArray<P>
&
x
,
ViewArray<N>
& y,
FloatVal
c
) {
170
(void)
new
(home)
Eq<P,N>
(home,
x
,y,
c
);
171
return
ES_OK
;
172
}
173
174
175
template
<
class
P,
class
N>
176
forceinline
177
Eq<P,N>::Eq
(
Space
& home,
bool
share,
Eq<P,N>
&
p
)
178
:
Lin
<P,N,
PC_FLOAT_BND
>(home,share,p) {}
179
180
template
<
class
P,
class
N>
181
Actor
*
182
Eq<P,N>::copy
(
Space
& home,
bool
share) {
183
return
new
(home)
Eq<P,N>
(home,share,*
this
);
184
}
185
186
template
<
class
P,
class
N>
187
ExecStatus
188
Eq<P,N>::propagate
(
Space
& home,
const
ModEventDelta
& med) {
189
// Eliminate singletons
190
Rounding
r
;
191
eliminate_p<P>(med,
x
,
c
);
192
eliminate_n<N>(med, y,
c
);
193
194
if
((
FloatView::me
(med) ==
ME_FLOAT_VAL
) && ((x.size() + y.size()) <= 1)) {
195
if
(x.size() == 1) {
196
GECODE_ME_CHECK
(x[0].eq(home,
c
));
197
return
home.
ES_SUBSUMED
(*
this
);
198
}
199
if
(y.size() == 1) {
200
GECODE_ME_CHECK
(y[0].eq(home,-
c
));
201
return
home.
ES_SUBSUMED
(*
this
);
202
}
203
return
(
c
.
in
(0.0)) ? home.
ES_SUBSUMED
(*
this
) :
ES_FAILED
;
204
}
205
206
ExecStatus
es =
ES_FIX
;
207
bool
assigned
=
true
;
208
209
// Propagate max bound for positive variables
210
for
(
int
i
= x.
size
();
i
--; ) {
211
// Compute bound
212
FloatNum
sl =
c
.
max
();
213
for
(
int
j = x.size(); j--; ) {
214
if
(
i
== j)
continue
;
215
sl = r.
sub_up
(sl,x[j].
min
());
216
}
217
for
(
int
j = y.size(); j--; )
218
sl = r.
add_up
(sl,y[j].max());
219
ModEvent
me = x[
i
].lq(home,sl);
220
if
(
me_failed
(me))
221
return
ES_FAILED
;
222
if
(me !=
ME_FLOAT_VAL
)
223
assigned =
false
;
224
if
(
me_modified
(me))
225
es =
ES_NOFIX
;
226
}
227
// Propagate min bound for negative variables
228
for
(
int
i
= y.
size
();
i
--; ) {
229
// Compute bound
230
FloatNum
sl = -
c
.
max
();
231
for
(
int
j = x.size(); j--; )
232
sl = r.
add_down
(sl,x[j].min());
233
for
(
int
j = y.size(); j--; ) {
234
if
(
i
== j)
continue
;
235
sl = r.
sub_down
(sl,y[j].
max
());
236
}
237
ModEvent
me = y[
i
].gq(home,sl);
238
if
(
me_failed
(me))
239
return
ES_FAILED
;
240
if
(me !=
ME_FLOAT_VAL
)
241
assigned =
false
;
242
if
(
me_modified
(me))
243
es =
ES_NOFIX
;
244
}
245
246
// Propagate min bound for positive variables
247
for
(
int
i
= x.
size
();
i
--; ) {
248
// Compute bound
249
FloatNum
su =
c
.
min
();
250
for
(
int
j = x.size(); j--; ) {
251
if
(
i
== j)
continue
;
252
su = r.
sub_down
(su,x[j].
max
());
253
}
254
for
(
int
j = y.size(); j--; )
255
su = r.
add_down
(su,y[j].min());
256
ModEvent
me = x[
i
].gq(home,su);
257
if
(
me_failed
(me))
258
return
ES_FAILED
;
259
if
(me !=
ME_FLOAT_VAL
)
260
assigned =
false
;
261
if
(
me_modified
(me))
262
es =
ES_NOFIX
;
263
}
264
// Propagate max bound for negative variables
265
for
(
int
i
= y.
size
();
i
--; ) {
266
// Compute bound
267
FloatNum
su = -
c
.
min
();
268
for
(
int
j = x.size(); j--; )
269
su = r.
add_up
(su,x[j].max());
270
for
(
int
j = y.size(); j--; ) {
271
if
(
i
== j)
continue
;
272
su = r.
sub_up
(su,y[j].
min
());
273
}
274
ModEvent
me = y[
i
].lq(home,su);
275
if
(
me_failed
(me))
276
return
ES_FAILED
;
277
if
(me !=
ME_FLOAT_VAL
)
278
assigned =
false
;
279
if
(
me_modified
(me))
280
es =
ES_NOFIX
;
281
}
282
283
return
assigned ? home.
ES_SUBSUMED
(*
this
) : es;
284
}
285
286
287
/*
288
* Bound consistent linear inequation
289
*
290
*/
291
292
template
<
class
P,
class
N>
293
forceinline
294
Lq<P,N>::Lq
(
Home
home,
ViewArray<P>
&
x
,
ViewArray<N>
& y,
FloatVal
c
)
295
:
Lin
<P,N,
PC_FLOAT_BND
>(home,x,y,c) {}
296
297
template
<
class
P,
class
N>
298
ExecStatus
299
Lq<P,N>::post
(
Home
home,
ViewArray<P>
&
x
,
ViewArray<N>
& y,
FloatVal
c
) {
300
(void)
new
(home)
Lq<P,N>
(home,
x
,y,
c
);
301
return
ES_OK
;
302
}
303
304
template
<
class
P,
class
N>
305
forceinline
306
Lq<P,N>::Lq
(
Space
& home,
bool
share,
Lq<P,N>
&
p
)
307
:
Lin
<P,N,
PC_FLOAT_BND
>(home,share,p) {}
308
309
template
<
class
P,
class
N>
310
Actor
*
311
Lq<P,N>::copy
(
Space
& home,
bool
share) {
312
return
new
(home)
Lq<P,N>
(home,share,*
this
);
313
}
314
315
template
<
class
P,
class
N>
316
ExecStatus
317
Lq<P,N>::propagate
(
Space
& home,
const
ModEventDelta
& med) {
318
// Eliminate singletons
319
FloatNum
sl = 0.0;
320
321
Rounding
r
;
322
323
if
(
FloatView::me
(med) ==
ME_FLOAT_VAL
) {
324
for
(
int
i
=
x
.size();
i
--; ) {
325
if
(
x
[
i
].
assigned
()) {
326
c
-=
x
[
i
].val();
x
.move_lst(
i
);
327
}
else
{
328
sl = r.
sub_up
(sl,
x
[
i
].
min
());
329
}
330
}
331
for
(
int
i
= y.
size
();
i
--; ) {
332
if
(y[
i
].
assigned
()) {
333
c
+= y[
i
].val(); y.move_lst(
i
);
334
}
else
{
335
sl = r.
add_up
(sl,y[
i
].
max
());
336
}
337
}
338
if
((
x
.size() + y.size()) <= 1) {
339
if
(
x
.size() == 1) {
340
GECODE_ME_CHECK
(
x
[0].lq(home,
c
.
max
()));
341
return
home.
ES_SUBSUMED
(*
this
);
342
}
343
if
(y.size() == 1) {
344
GECODE_ME_CHECK
(y[0].gq(home,(-
c
).
min
()));
345
return
home.
ES_SUBSUMED
(*
this
);
346
}
347
return
(
c
.
max
() >= 0) ? home.
ES_SUBSUMED
(*
this
) :
ES_FAILED
;
348
}
349
}
else
{
350
for
(
int
i
=
x
.size();
i
--; )
351
sl = r.
sub_up
(sl,
x
[
i
].min());
352
for
(
int
i
= y.
size
();
i
--; )
353
sl = r.
add_up
(sl,y[
i
].max());
354
}
355
356
sl = r.
add_up
(sl,
c
.
max
());
357
358
ExecStatus
es =
ES_FIX
;
359
bool
assigned
=
true
;
360
for
(
int
i
=
x
.size();
i
--; ) {
361
assert(!
x
[
i
].
assigned
());
362
FloatNum
slx = r.
add_up
(sl,
x
[
i
].
min
());
363
ModEvent
me =
x
[
i
].lq(home,slx);
364
if
(me ==
ME_FLOAT_FAILED
)
365
return
ES_FAILED
;
366
if
(me !=
ME_FLOAT_VAL
)
367
assigned =
false
;
368
if
(
me_modified
(me))
369
es =
ES_NOFIX
;
370
}
371
372
for
(
int
i
= y.
size
();
i
--; ) {
373
assert(!y[
i
].
assigned
());
374
FloatNum
sly = r.
sub_up
(y[
i
].
max
(),sl);
375
ModEvent
me = y[
i
].gq(home,sly);
376
if
(me ==
ME_FLOAT_FAILED
)
377
return
ES_FAILED
;
378
if
(me !=
ME_FLOAT_VAL
)
379
assigned =
false
;
380
if
(
me_modified
(me))
381
es =
ES_NOFIX
;
382
}
383
384
return
assigned ? home.
ES_SUBSUMED
(*
this
) : es;
385
}
386
387
}}}
388
389
// STATISTICS: float-prop
390