Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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 * This file is part of Gecode, the generic constraint
12 * development environment:
13 * http://www.gecode.org
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining
16 * a copy of this software and associated documentation files (the
17 * "Software"), to deal in the Software without restriction, including
18 * without limitation the rights to use, copy, modify, merge, publish,
19 * distribute, sublicense, and/or sell copies of the Software, and to
20 * permit persons to whom the Software is furnished to do so, subject to
21 * the following conditions:
22 *
23 * The above copyright notice and this permission notice shall be
24 * included in all copies or substantial portions of the Software.
25 *
26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 *
34 */
35
36namespace Gecode { namespace Float { namespace Linear {
37
38 /*
39 * Linear propagators
40 *
41 */
42 template<class P, class N, PropCond pc>
45 : Propagator(home), x(x0), y(y0), c(c0) {
46 x.subscribe(home,*this,pc);
47 y.subscribe(home,*this,pc);
48 }
49
50 template<class P, class N, PropCond pc>
53 : Propagator(home,p), c(p.c) {
54 x.update(home,p.x);
55 y.update(home,p.y);
56 }
57
58 template<class P, class N, PropCond pc>
60 Lin<P,N,pc>::cost(const Space&, const ModEventDelta&) const {
61 return PropCost::linear(PropCost::LO, x.size()+y.size());
62 }
63
64 template<class P, class N, PropCond pc>
65 void
67 x.reschedule(home,*this,pc);
68 y.reschedule(home,*this,pc);
69 }
70
71 template<class P, class N, PropCond pc>
74 x.cancel(home,*this,pc);
75 y.cancel(home,*this,pc);
76 (void) Propagator::dispose(home);
77 return sizeof(*this);
78 }
79
80
81 template<class View>
82 void
84 int n = x.size();
85
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 }
91 }
92 x.size(n);
93 }
94 }
95
96 template<class View>
97 void
99 int n = y.size();
100 if (FloatView::me(med) == ME_FLOAT_VAL) {
101 for (int i = n; i--; ) {
102 if (y[i].assigned()) {
103 c += y[i].val(); y[i] = y[--n];
104 }
105 }
106 y.size(n);
107 }
108 }
109
110 forceinline bool
111 infty(const FloatNum& n) {
112 return ((n == std::numeric_limits<FloatNum>::infinity()) ||
113 (n == -std::numeric_limits<FloatNum>::infinity()));
114 }
115
116 /*
117 * Bound consistent linear equation
118 *
119 */
120
121 template<class P, class N>
124 : Lin<P,N,PC_FLOAT_BND>(home,x,y,c) {}
125
126 template<class P, class N>
129 (void) new (home) Eq<P,N>(home,x,y,c);
130 return ES_OK;
131 }
132
133
134 template<class P, class N>
137 : Lin<P,N,PC_FLOAT_BND>(home,p) {}
138
139 template<class P, class N>
140 Actor*
142 return new (home) Eq<P,N>(home,*this);
143 }
144
145 template<class P, class N>
148 // Eliminate singletons
149 Rounding r;
150 eliminate_p<P>(med, x, c);
151 eliminate_n<N>(med, y, c);
152
153 if ((FloatView::me(med) == ME_FLOAT_VAL) && ((x.size() + y.size()) <= 1)) {
154 if (x.size() == 1) {
155 GECODE_ME_CHECK(x[0].eq(home,c));
156 return home.ES_SUBSUMED(*this);
157 }
158 if (y.size() == 1) {
159 GECODE_ME_CHECK(y[0].eq(home,-c));
160 return home.ES_SUBSUMED(*this);
161 }
162 return (c.in(0.0)) ? home.ES_SUBSUMED(*this) : ES_FAILED;
163 }
164
165 ExecStatus es = ES_FIX;
166 bool assigned = true;
167
168 // Propagate max bound for positive variables
169 for (int i = x.size(); i--; ) {
170 // Compute bound
171 FloatNum sl = c.max();
172 for (int j = x.size(); j--; ) {
173 if (i == j) continue;
174 sl = r.sub_up(sl,x[j].min());
175 }
176 for (int j = y.size(); j--; )
177 sl = r.add_up(sl,y[j].max());
178 ModEvent me = x[i].lq(home,sl);
179 if (me_failed(me))
180 return ES_FAILED;
181 if (me != ME_FLOAT_VAL)
182 assigned = false;
183 if (me_modified(me))
184 es = ES_NOFIX;
185 }
186 // Propagate min bound for negative variables
187 for (int i = y.size(); i--; ) {
188 // Compute bound
189 FloatNum sl = -c.max();
190 for (int j = x.size(); j--; )
191 sl = r.add_down(sl,x[j].min());
192 for (int j = y.size(); j--; ) {
193 if (i == j) continue;
194 sl = r.sub_down(sl,y[j].max());
195 }
196 ModEvent me = y[i].gq(home,sl);
197 if (me_failed(me))
198 return ES_FAILED;
199 if (me != ME_FLOAT_VAL)
200 assigned = false;
201 if (me_modified(me))
202 es = ES_NOFIX;
203 }
204
205 // Propagate min bound for positive variables
206 for (int i = x.size(); i--; ) {
207 // Compute bound
208 FloatNum su = c.min();
209 for (int j = x.size(); j--; ) {
210 if (i == j) continue;
211 su = r.sub_down(su,x[j].max());
212 }
213 for (int j = y.size(); j--; )
214 su = r.add_down(su,y[j].min());
215 ModEvent me = x[i].gq(home,su);
216 if (me_failed(me))
217 return ES_FAILED;
218 if (me != ME_FLOAT_VAL)
219 assigned = false;
220 if (me_modified(me))
221 es = ES_NOFIX;
222 }
223 // Propagate max bound for negative variables
224 for (int i = y.size(); i--; ) {
225 // Compute bound
226 FloatNum su = -c.min();
227 for (int j = x.size(); j--; )
228 su = r.add_up(su,x[j].max());
229 for (int j = y.size(); j--; ) {
230 if (i == j) continue;
231 su = r.sub_up(su,y[j].min());
232 }
233 ModEvent me = y[i].lq(home,su);
234 if (me_failed(me))
235 return ES_FAILED;
236 if (me != ME_FLOAT_VAL)
237 assigned = false;
238 if (me_modified(me))
239 es = ES_NOFIX;
240 }
241
242 return assigned ? home.ES_SUBSUMED(*this) : es;
243 }
244
245
246 /*
247 * Bound consistent linear inequation
248 *
249 */
250
251 template<class P, class N>
254 : Lin<P,N,PC_FLOAT_BND>(home,x,y,c) {}
255
256 template<class P, class N>
259 (void) new (home) Lq<P,N>(home,x,y,c);
260 return ES_OK;
261 }
262
263 template<class P, class N>
266 : Lin<P,N,PC_FLOAT_BND>(home,p) {}
267
268 template<class P, class N>
269 Actor*
271 return new (home) Lq<P,N>(home,*this);
272 }
273
274 template<class P, class N>
277 // Eliminate singletons
278 FloatNum sl = 0.0;
279
280 Rounding r;
281
282 if (FloatView::me(med) == ME_FLOAT_VAL) {
283 for (int i = x.size(); i--; ) {
284 if (x[i].assigned()) {
285 c -= x[i].val(); x.move_lst(i);
286 } else {
287 sl = r.sub_up(sl,x[i].min());
288 }
289 }
290 for (int i = y.size(); i--; ) {
291 if (y[i].assigned()) {
292 c += y[i].val(); y.move_lst(i);
293 } else {
294 sl = r.add_up(sl,y[i].max());
295 }
296 }
297 if ((x.size() + y.size()) <= 1) {
298 if (x.size() == 1) {
299 GECODE_ME_CHECK(x[0].lq(home,c.max()));
300 return home.ES_SUBSUMED(*this);
301 }
302 if (y.size() == 1) {
303 GECODE_ME_CHECK(y[0].gq(home,(-c).min()));
304 return home.ES_SUBSUMED(*this);
305 }
306 return (c.max() >= 0) ? home.ES_SUBSUMED(*this) : ES_FAILED;
307 }
308 } else {
309 for (int i = x.size(); i--; )
310 sl = r.sub_up(sl,x[i].min());
311 for (int i = y.size(); i--; )
312 sl = r.add_up(sl,y[i].max());
313 }
314
315 sl = r.add_up(sl,c.max());
316
317 ExecStatus es = ES_FIX;
318 bool assigned = true;
319 for (int i = x.size(); i--; ) {
320 assert(!x[i].assigned());
321 FloatNum slx = r.add_up(sl,x[i].min());
322 ModEvent me = x[i].lq(home,slx);
323 if (me == ME_FLOAT_FAILED)
324 return ES_FAILED;
325 if (me != ME_FLOAT_VAL)
326 assigned = false;
327 if (me_modified(me))
328 es = ES_NOFIX;
329 }
330
331 for (int i = y.size(); i--; ) {
332 assert(!y[i].assigned());
333 FloatNum sly = r.sub_up(y[i].max(),sl);
334 ModEvent me = y[i].gq(home,sly);
335 if (me == ME_FLOAT_FAILED)
336 return ES_FAILED;
337 if (me != ME_FLOAT_VAL)
338 assigned = false;
339 if (me_modified(me))
340 es = ES_NOFIX;
341 }
342
343 return assigned ? home.ES_SUBSUMED(*this) : es;
344 }
345
346}}}
347
348// STATISTICS: float-prop
349
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
Base-class for both propagators and branchers.
Definition core.hpp:628
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3252
Float value type.
Definition float.hh:334
bool in(FloatNum n) const
Test whether n is included.
Definition val.hpp:96
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition val.hpp:386
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition val.hpp:398
Propagator for bounds consistent n-ary linear equality
Definition linear.hh:106
static ExecStatus post(Home home, ViewArray< P > &x, ViewArray< N > &y, FloatVal c)
Post propagator for .
Definition nary.hpp:128
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition nary.hpp:141
Eq(Space &home, Eq &p)
Constructor for cloning p.
Definition nary.hpp:136
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition nary.hpp:147
Base-class for n-ary linear propagators.
Definition linear.hh:57
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low linear)
Definition nary.hpp:60
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition nary.hpp:73
Lin(Space &home, Lin< P, N, pc > &p)
Constructor for cloning p.
Definition nary.hpp:52
ViewArray< P > x
Array of positive views.
Definition linear.hh:60
virtual void reschedule(Space &home)
Schedule function.
Definition nary.hpp:66
ViewArray< N > y
Array of negative views.
Definition linear.hh:62
Propagator for bounds consistent n-ary linear less or equal
Definition linear.hh:136
static ExecStatus post(Home home, ViewArray< P > &x, ViewArray< N > &y, FloatVal c)
Post propagator for .
Definition nary.hpp:258
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition nary.hpp:270
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition nary.hpp:276
Lq(Space &home, Lq &p)
Constructor for cloning p.
Definition nary.hpp:265
Floating point rounding policy.
Definition float.hh:154
Home class for posting propagators
Definition core.hpp:856
Propagation cost.
Definition core.hpp:486
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:4796
Base-class for propagators.
Definition core.hpp:1064
Computation spaces.
Definition core.hpp:1742
static ModEvent me(const ModEventDelta &med)
Definition view.hpp:552
View arrays.
Definition array.hpp:253
void update(Space &home, ViewArray< View > &a)
Update array to be a clone of array a.
Definition array.hpp:1328
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition array.hpp:1341
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition modevent.hpp:59
double FloatNum
Floating point number base type.
Definition float.hh:106
void eliminate_n(ModEventDelta med, ViewArray< View > &y, FloatVal &c)
Definition nary.hpp:98
void eliminate_p(ModEventDelta med, ViewArray< View > &x, FloatVal &c)
Definition nary.hpp:83
bool infty(const FloatNum &n)
Definition nary.hpp:111
const Gecode::ModEvent ME_FLOAT_VAL
Domain operation has resulted in a value (assigned variable)
Definition var-type.hpp:264
const Gecode::ModEvent ME_FLOAT_FAILED
Domain operation has resulted in failure.
Definition var-type.hpp:260
const Gecode::PropCond PC_FLOAT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:292
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:767
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
Definition set.hh:767
int ModEvent
Type for modification events.
Definition core.hpp:62
#define forceinline
Definition config.hpp:187