00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040 namespace Gecode { namespace Float { namespace Linear {
00041
00042
00043
00044
00045
00046 template<class P, class N, PropCond pc>
00047 forceinline
00048 Lin<P,N,pc>::Lin(Home home, ViewArray<P>& x0, ViewArray<N>& y0, FloatVal c0)
00049 : Propagator(home), x(x0), y(y0), c(c0) {
00050 x.subscribe(home,*this,pc);
00051 y.subscribe(home,*this,pc);
00052 }
00053
00054 template<class P, class N, PropCond pc>
00055 forceinline
00056 Lin<P,N,pc>::Lin(Space& home, bool share, Lin<P,N,pc>& p)
00057 : Propagator(home,share,p), c(p.c) {
00058 x.update(home,share,p.x);
00059 y.update(home,share,p.y);
00060 }
00061
00062 template<class P, class N, PropCond pc>
00063 PropCost
00064 Lin<P,N,pc>::cost(const Space&, const ModEventDelta&) const {
00065 return PropCost::linear(PropCost::LO, x.size()+y.size());
00066 }
00067
00068 template<class P, class N, PropCond pc>
00069 void
00070 Lin<P,N,pc>::reschedule(Space& home) {
00071 x.reschedule(home,*this,pc);
00072 y.reschedule(home,*this,pc);
00073 }
00074
00075 template<class P, class N, PropCond pc>
00076 forceinline size_t
00077 Lin<P,N,pc>::dispose(Space& home) {
00078 x.cancel(home,*this,pc);
00079 y.cancel(home,*this,pc);
00080 (void) Propagator::dispose(home);
00081 return sizeof(*this);
00082 }
00083
00084
00085 template<class View>
00086 void
00087 eliminate_p(ModEventDelta med, ViewArray<View>& x, FloatVal& c) {
00088 int n = x.size();
00089
00090 if (FloatView::me(med) == ME_FLOAT_VAL) {
00091 for (int i = n; i--; ) {
00092 if (x[i].assigned()) {
00093 c -= x[i].val(); x[i] = x[--n];
00094 }
00095 }
00096 x.size(n);
00097 }
00098 }
00099
00100 template<class View>
00101 void
00102 eliminate_n(ModEventDelta med, ViewArray<View>& y, FloatVal& c) {
00103 int n = y.size();
00104 if (FloatView::me(med) == ME_FLOAT_VAL) {
00105 for (int i = n; i--; ) {
00106 if (y[i].assigned()) {
00107 c += y[i].val(); y[i] = y[--n];
00108 }
00109 }
00110 y.size(n);
00111 }
00112 }
00113
00114 forceinline bool
00115 infty(const FloatNum& n) {
00116 return ((n == std::numeric_limits<FloatNum>::infinity()) ||
00117 (n == -std::numeric_limits<FloatNum>::infinity()));
00118 }
00119
00120
00121
00122
00123
00124
00125 template<class P, class N>
00126 forceinline
00127 Eq<P,N>::Eq(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c)
00128 : Lin<P,N,PC_FLOAT_BND>(home,x,y,c) {}
00129
00130 template<class P, class N>
00131 ExecStatus
00132 Eq<P,N>::post(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c) {
00133 (void) new (home) Eq<P,N>(home,x,y,c);
00134 return ES_OK;
00135 }
00136
00137
00138 template<class P, class N>
00139 forceinline
00140 Eq<P,N>::Eq(Space& home, bool share, Eq<P,N>& p)
00141 : Lin<P,N,PC_FLOAT_BND>(home,share,p) {}
00142
00143 template<class P, class N>
00144 Actor*
00145 Eq<P,N>::copy(Space& home, bool share) {
00146 return new (home) Eq<P,N>(home,share,*this);
00147 }
00148
00149 template<class P, class N>
00150 ExecStatus
00151 Eq<P,N>::propagate(Space& home, const ModEventDelta& med) {
00152
00153 Rounding r;
00154 eliminate_p<P>(med, x, c);
00155 eliminate_n<N>(med, y, c);
00156
00157 if ((FloatView::me(med) == ME_FLOAT_VAL) && ((x.size() + y.size()) <= 1)) {
00158 if (x.size() == 1) {
00159 GECODE_ME_CHECK(x[0].eq(home,c));
00160 return home.ES_SUBSUMED(*this);
00161 }
00162 if (y.size() == 1) {
00163 GECODE_ME_CHECK(y[0].eq(home,-c));
00164 return home.ES_SUBSUMED(*this);
00165 }
00166 return (c.in(0.0)) ? home.ES_SUBSUMED(*this) : ES_FAILED;
00167 }
00168
00169 ExecStatus es = ES_FIX;
00170 bool assigned = true;
00171
00172
00173 for (int i = x.size(); i--; ) {
00174
00175 FloatNum sl = c.max();
00176 for (int j = x.size(); j--; ) {
00177 if (i == j) continue;
00178 sl = r.sub_up(sl,x[j].min());
00179 }
00180 for (int j = y.size(); j--; )
00181 sl = r.add_up(sl,y[j].max());
00182 ModEvent me = x[i].lq(home,sl);
00183 if (me_failed(me))
00184 return ES_FAILED;
00185 if (me != ME_FLOAT_VAL)
00186 assigned = false;
00187 if (me_modified(me))
00188 es = ES_NOFIX;
00189 }
00190
00191 for (int i = y.size(); i--; ) {
00192
00193 FloatNum sl = -c.max();
00194 for (int j = x.size(); j--; )
00195 sl = r.add_down(sl,x[j].min());
00196 for (int j = y.size(); j--; ) {
00197 if (i == j) continue;
00198 sl = r.sub_down(sl,y[j].max());
00199 }
00200 ModEvent me = y[i].gq(home,sl);
00201 if (me_failed(me))
00202 return ES_FAILED;
00203 if (me != ME_FLOAT_VAL)
00204 assigned = false;
00205 if (me_modified(me))
00206 es = ES_NOFIX;
00207 }
00208
00209
00210 for (int i = x.size(); i--; ) {
00211
00212 FloatNum su = c.min();
00213 for (int j = x.size(); j--; ) {
00214 if (i == j) continue;
00215 su = r.sub_down(su,x[j].max());
00216 }
00217 for (int j = y.size(); j--; )
00218 su = r.add_down(su,y[j].min());
00219 ModEvent me = x[i].gq(home,su);
00220 if (me_failed(me))
00221 return ES_FAILED;
00222 if (me != ME_FLOAT_VAL)
00223 assigned = false;
00224 if (me_modified(me))
00225 es = ES_NOFIX;
00226 }
00227
00228 for (int i = y.size(); i--; ) {
00229
00230 FloatNum su = -c.min();
00231 for (int j = x.size(); j--; )
00232 su = r.add_up(su,x[j].max());
00233 for (int j = y.size(); j--; ) {
00234 if (i == j) continue;
00235 su = r.sub_up(su,y[j].min());
00236 }
00237 ModEvent me = y[i].lq(home,su);
00238 if (me_failed(me))
00239 return ES_FAILED;
00240 if (me != ME_FLOAT_VAL)
00241 assigned = false;
00242 if (me_modified(me))
00243 es = ES_NOFIX;
00244 }
00245
00246 return assigned ? home.ES_SUBSUMED(*this) : es;
00247 }
00248
00249
00250
00251
00252
00253
00254
00255 template<class P, class N>
00256 forceinline
00257 Lq<P,N>::Lq(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c)
00258 : Lin<P,N,PC_FLOAT_BND>(home,x,y,c) {}
00259
00260 template<class P, class N>
00261 ExecStatus
00262 Lq<P,N>::post(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c) {
00263 (void) new (home) Lq<P,N>(home,x,y,c);
00264 return ES_OK;
00265 }
00266
00267 template<class P, class N>
00268 forceinline
00269 Lq<P,N>::Lq(Space& home, bool share, Lq<P,N>& p)
00270 : Lin<P,N,PC_FLOAT_BND>(home,share,p) {}
00271
00272 template<class P, class N>
00273 Actor*
00274 Lq<P,N>::copy(Space& home, bool share) {
00275 return new (home) Lq<P,N>(home,share,*this);
00276 }
00277
00278 template<class P, class N>
00279 ExecStatus
00280 Lq<P,N>::propagate(Space& home, const ModEventDelta& med) {
00281
00282 FloatNum sl = 0.0;
00283
00284 Rounding r;
00285
00286 if (FloatView::me(med) == ME_FLOAT_VAL) {
00287 for (int i = x.size(); i--; ) {
00288 if (x[i].assigned()) {
00289 c -= x[i].val(); x.move_lst(i);
00290 } else {
00291 sl = r.sub_up(sl,x[i].min());
00292 }
00293 }
00294 for (int i = y.size(); i--; ) {
00295 if (y[i].assigned()) {
00296 c += y[i].val(); y.move_lst(i);
00297 } else {
00298 sl = r.add_up(sl,y[i].max());
00299 }
00300 }
00301 if ((x.size() + y.size()) <= 1) {
00302 if (x.size() == 1) {
00303 GECODE_ME_CHECK(x[0].lq(home,c.max()));
00304 return home.ES_SUBSUMED(*this);
00305 }
00306 if (y.size() == 1) {
00307 GECODE_ME_CHECK(y[0].gq(home,(-c).min()));
00308 return home.ES_SUBSUMED(*this);
00309 }
00310 return (c.max() >= 0) ? home.ES_SUBSUMED(*this) : ES_FAILED;
00311 }
00312 } else {
00313 for (int i = x.size(); i--; )
00314 sl = r.sub_up(sl,x[i].min());
00315 for (int i = y.size(); i--; )
00316 sl = r.add_up(sl,y[i].max());
00317 }
00318
00319 sl = r.add_up(sl,c.max());
00320
00321 ExecStatus es = ES_FIX;
00322 bool assigned = true;
00323 for (int i = x.size(); i--; ) {
00324 assert(!x[i].assigned());
00325 FloatNum slx = r.add_up(sl,x[i].min());
00326 ModEvent me = x[i].lq(home,slx);
00327 if (me == ME_FLOAT_FAILED)
00328 return ES_FAILED;
00329 if (me != ME_FLOAT_VAL)
00330 assigned = false;
00331 if (me_modified(me))
00332 es = ES_NOFIX;
00333 }
00334
00335 for (int i = y.size(); i--; ) {
00336 assert(!y[i].assigned());
00337 FloatNum sly = r.sub_up(y[i].max(),sl);
00338 ModEvent me = y[i].gq(home,sly);
00339 if (me == ME_FLOAT_FAILED)
00340 return ES_FAILED;
00341 if (me != ME_FLOAT_VAL)
00342 assigned = false;
00343 if (me_modified(me))
00344 es = ES_NOFIX;
00345 }
00346
00347 return assigned ? home.ES_SUBSUMED(*this) : es;
00348 }
00349
00350 }}}
00351
00352
00353