Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
min-max.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, 2004
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
36#include <cmath>
37
38namespace Gecode { namespace Float { namespace Arithmetic {
39
40 /*
41 * Bounds consistent min propagator
42 *
43 */
44 template<class A, class B, class C>
46 Min<A,B,C>::Min(Home home, A x0, B x1, C x2)
48
49 template<class A, class B, class C>
53
54 template<class A, class B, class C>
57 A x0, B x1, C x2)
59
60 template<class A, class B, class C>
61 Actor*
63 return new (home) Min<A,B,C>(home,*this);
64 }
65
66 template<class A, class B, class C>
68 Min<A,B,C>::post(Home home, A x0, B x1, C x2) {
69 GECODE_ME_CHECK(x2.eq(home,min(x0.domain(),x1.domain())));
70 GECODE_ME_CHECK(x0.gq(home,x2.min()));
71 GECODE_ME_CHECK(x1.gq(home,x2.min()));
72 (void) new (home) Min<A,B,C>(home,x0,x1,x2);
73 return ES_OK;
74 }
75
76 template<class A, class B, class C>
79 GECODE_ME_CHECK(x2.eq(home,min(x0.domain(),x1.domain())));
80 GECODE_ME_CHECK(x0.gq(home,x2.min()));
81 GECODE_ME_CHECK(x1.gq(home,x2.min()));
82 if (x0 == x1) {
83 GECODE_ME_CHECK(x0.lq(home,x2.max()));
84 } else {
85 if (!overlap(x1.val(),x2.val())) GECODE_ME_CHECK(x0.lq(home,x2.max()));
86 if (!overlap(x0.val(),x2.val())) GECODE_ME_CHECK(x1.lq(home,x2.max()));
87 }
88 return (x0.assigned() && x1.assigned()) ? home.ES_SUBSUMED(*this) : ES_FIX;
89 }
90
91 /*
92 * Bounds consistent max propagator
93 *
94 */
95
96 template<class A, class B, class C>
98 Max<A,B,C>::Max(Home home, A x0, B x1, C x2)
100
101 template<class A, class B, class C>
105
106 template<class A, class B, class C>
109 A x0, B x1, C x2)
111
112 template<class A, class B, class C>
113 Actor*
115 return new (home) Max<A,B,C>(home,*this);
116 }
117
118 template<class A, class B, class C>
120 Max<A,B,C>::post(Home home, A x0, B x1, C x2) {
121 GECODE_ME_CHECK(x2.eq(home,max(x0.domain(),x1.domain())));
122 GECODE_ME_CHECK(x0.lq(home,x2.max()));
123 GECODE_ME_CHECK(x1.lq(home,x2.max()));
124 (void) new (home) Max<A,B,C>(home,x0,x1,x2);
125 return ES_OK;
126 }
127
128 template<class A, class B, class C>
131 GECODE_ME_CHECK(x2.eq(home,max(x0.domain(),x1.domain())));
132 GECODE_ME_CHECK(x0.lq(home,x2.max()));
133 GECODE_ME_CHECK(x1.lq(home,x2.max()));
134 if (x0 == x1) {
135 GECODE_ME_CHECK(x0.gq(home,x2.min()));
136 } else {
137 if (!overlap(x1.val(),x2.val())) GECODE_ME_CHECK(x0.gq(home,x2.min()));
138 if (!overlap(x0.val(),x2.val())) GECODE_ME_CHECK(x1.gq(home,x2.min()));
139 }
140 return (x0.assigned() && x1.assigned()) ? home.ES_SUBSUMED(*this) : ES_FIX;
141 }
142
143 /*
144 * Nary bounds consistent maximum
145 *
146 */
147
148 template<class View>
152
153 template<class View>
156 assert(x.size() > 0);
157 x.unique();
158 if (x.size() == 1)
159 return Rel::Eq<View,View>::post(home,x[0],y);
160 if (x.size() == 2)
161 return Max<View,View,View>::post(home,x[0],x[1],y);
164 for (int i=x.size(); i--; ) {
165 l = std::max(l,x[i].min());
166 u = std::max(u,x[i].max());
167 }
168 GECODE_ME_CHECK(y.gq(home,l));
169 GECODE_ME_CHECK(y.lq(home,u));
170 if (x.same(y)) {
171 // Check whether y occurs in x
172 for (int i=x.size(); i--; )
174 } else {
175 (void) new (home) NaryMax<View>(home,x,y);
176 }
177 return ES_OK;
178 }
179
180 template<class View>
184
185 template<class View>
186 Actor*
188 if (x.size() == 1)
189 return new (home) Rel::Eq<View,View>(home,*this,x[0],y);
190 if (x.size() == 2)
191 return new (home) Max<View,View,View>(home,*this,x[0],x[1],y);
192 return new (home) NaryMax<View>(home,*this);
193 }
194
201
202 template<class View>
205 ViewArray<View>& x, View y, PropCond pc) {
206 rerun:
207 assert(x.size() > 0);
208 FloatNum maxmax = x[x.size()-1].max();
209 FloatNum maxmin = x[x.size()-1].min();
210 for (int i = x.size()-1; i--; ) {
211 maxmax = std::max(x[i].max(),maxmax);
212 maxmin = std::max(x[i].min(),maxmin);
213 }
214 GECODE_ME_CHECK(y.lq(home,maxmax));
215 GECODE_ME_CHECK(y.gq(home,maxmin));
216 maxmin = y.min();
217 maxmax = y.max();
218 int status = MPS_ASSIGNED;
219 for (int i = x.size(); i--; ) {
220 ModEvent me = x[i].lq(home,maxmax);
221 if (me == ME_FLOAT_FAILED)
222 return ES_FAILED;
223 if (me_modified(me) && (x[i].max() != maxmax))
224 status |= MPS_NEW_BOUND;
225 if (x[i].max() < maxmin) {
226 x.move_lst(i,home,p,pc);
227 status |= MPS_REMOVED;
228 } else if (!x[i].assigned())
229 status &= ~MPS_ASSIGNED;
230 }
231 if (x.size() == 0)
232 return ES_FAILED;
233 if ((status & MPS_REMOVED) != 0)
234 goto rerun;
235 if (((status & MPS_ASSIGNED) != 0) && y.assigned())
236 return home.ES_SUBSUMED(p);
237 return ((status & MPS_NEW_BOUND) != 0) ? ES_NOFIX : ES_FIX;
238 }
239
240 template<class View>
243 return prop_nary_max(home,*this,x,y,PC_FLOAT_BND);
244 }
245
246}}}
247
248// STATISTICS: float-prop
249
NNF * l
Left subtree.
union Gecode::@603::NNF::@65 u
Union depending on nodetype t.
int p
Number of positive literals for node type.
Base-class for both propagators and branchers.
Definition core.hpp:628
Propagator for bounds consistent max operator
static ExecStatus post(Home home, A x0, B x1, C x2)
Post propagator for .
Definition min-max.hpp:120
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition min-max.hpp:114
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition min-max.hpp:130
Max(Space &home, Max &p)
Constructor for cloning p.
Definition min-max.hpp:103
Propagator for bounds consistent min operator
Min(Space &home, Min &p)
Constructor for cloning p.
Definition min-max.hpp:51
static ExecStatus post(Home home, A x0, B x1, C x2)
Post propagator for .
Definition min-max.hpp:68
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition min-max.hpp:62
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition min-max.hpp:78
Bounds consistent n-ary maximum propagator.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition min-max.hpp:187
static ExecStatus post(Home home, ViewArray< View > &x, View y)
Post propagator .
Definition min-max.hpp:155
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition min-max.hpp:242
NaryMax(Space &home, NaryMax &p)
Constructor for cloning p.
Definition min-max.hpp:182
Binary bounds consistent equality propagator.
Definition rel.hh:67
static ExecStatus post(Home home, View0 x0, View1 x1)
Post bounds consistent propagator .
Definition eq.hpp:50
Less or equal propagator.
Definition rel.hh:241
Home class for posting propagators
Definition core.hpp:856
Mixed ternary propagator.
Definition pattern.hpp:237
(n+1)-ary propagator
Definition pattern.hpp:172
Base-class for propagators.
Definition core.hpp:1064
Computation spaces.
Definition core.hpp:1742
bool assigned(void) const
Test whether view is assigned.
Definition var.hpp:111
View arrays.
Definition array.hpp:253
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
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
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
MaxPropStatus
Status of propagation for nary max.
Definition min-max.hpp:196
@ MPS_ASSIGNED
All views are assigned.
Definition min-max.hpp:197
@ MPS_NEW_BOUND
Telling has found a new upper bound.
Definition min-max.hpp:199
@ MPS_REMOVED
A view is removed.
Definition min-max.hpp:198
ExecStatus prop_nary_max(Space &home, Propagator &p, ViewArray< View > &x, View y, PropCond pc)
Definition min-max.hpp:204
const FloatNum min
Smallest allowed float value.
Definition float.hh:846
bool overlap(const FloatVal &x, const FloatVal &y)
Definition val.hpp:498
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
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 .
int PropCond
Type for propagation conditions.
Definition core.hpp:72
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