FIM_CP+CIMCP: cimcp/src/constraint_Fmonotone.cpp Source File

00001 /*
00002  *  Main authors:
00003  *      Tias Guns <tias.guns@cs.kuleuven.be>
00004  *
00005  *  Copyright:
00006  *      Tias Guns, 2008
00007  *
00008  *  Revision information:
00009  *      $Id: graph_cp.cc 128 2008-08-07 11:23:23Z tias $
00010  *
00011  *  This file is part of Graph_cp and uses Gecode.
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include "gecode/kernel.hh"
00035 #include "gecode/int.hh"
00036 #include "gecode/iter.hh"
00037 #include "gecode/int/rel.hh"
00038 
00039 namespace FmonotoneBool {
00040   using namespace ::Gecode;
00041   using namespace ::Gecode::Int;
00042 
00043   /**
00044    * \brief Base-class for monotone function boolean propagators
00045    *
00046    * This class NEEDS a global function:
00047    * monotone_function(int pos_total, int pos, int neg_total, int neg, int precision)
00048    */
00049   template <class VA, class VC>
00050   class FmonotoneBoolGq : public Propagator {
00051   protected:
00052     /// total class 1
00053     int X;
00054     /// Boolean views class 1
00055     ViewArray<VA> x;
00056     /// lower bound class 1 (part from class1 views assigned to 1)
00057     int l_x;
00058     /// total class 2
00059     int Y;
00060     /// Boolean views class y
00061     ViewArray<VA> y;
00062     /// lower bound class 2 (part from class2 views assigned to 1)
00063     int l_y;
00064     /// Righthandside, the treshold
00065     VC c;
00066     /// Precision of treshold-integer conversion (eg. 1000)
00067     int precision;
00068 
00069     /// Constructor for creation
00070     FmonotoneBoolGq(Space& home, int X, ViewArray<VA>& x, int l_x,
00071             int Y, ViewArray<VA>& y, int l_y, VC c, int precision);
00072     /// Constructor for cloning \a p
00073     FmonotoneBoolGq(Space& home, bool share, FmonotoneBoolGq& p);
00074   public:
00075     /// Cost function (defined as low linear)
00076     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00077     /// Delete propagator and return its size
00078     virtual size_t dispose(Space& home);
00079     /// Create copy during cloning
00080     virtual Actor* copy(Space& home, bool share);
00081     /// Perform propagation
00082     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00083     /// Eliminate assigned vars and update bounds
00084     void eliminate(ViewArray<VA>& v, int& l, int& u);
00085     /// Post propagator but
00086     static ExecStatus post(Space& home, int X, ViewArray<VA>& x, int l_x, int Y, ViewArray<VA>& y, int l_y, VC c, int precision);
00087   };
00088 
00089   /*
00090    * Chi2 Class
00091    */
00092   template <class VA, class VC>
00093   FmonotoneBoolGq<VA,VC>::FmonotoneBoolGq(Space& home, int X0,
00094         ViewArray<VA>& x0, int l_x0, int Y0, ViewArray<VA>& y0, int l_y0, VC c0, int precision0)
00095     :  Propagator(home), X(X0),x(x0),l_x(l_x0),Y(Y0),y(y0),l_y(l_y0),c(c0),precision(precision0) {
00096     x.subscribe(home,*this,PC_INT_VAL);
00097     y.subscribe(home,*this,PC_INT_VAL);
00098     c.subscribe(home,*this,PC_INT_BND);
00099   }
00100 
00101   template <class VA, class VC>
00102   forceinline size_t
00103   FmonotoneBoolGq<VA,VC>::dispose(Space& home) {
00104     assert(!home.failed());
00105     x.cancel(home,*this,PC_INT_VAL);
00106     y.cancel(home,*this,PC_INT_VAL);
00107     c.cancel(home,*this,PC_INT_BND);
00108     (void) Propagator::dispose(home);
00109     return sizeof(*this);
00110   }
00111 
00112   template <class VA, class VC>
00113   forceinline
00114   FmonotoneBoolGq<VA,VC>::FmonotoneBoolGq(Space& home,
00115             bool share, FmonotoneBoolGq& p)
00116     : Propagator(home,share,p), X(p.X),l_x(p.l_x),Y(p.Y),l_y(p.l_y),precision(p.precision) {
00117     x.update(home,share,p.x);
00118     y.update(home,share,p.y);
00119     c.update(home,share,p.c);
00120   }
00121 
00122   template <class VA, class VC>
00123   PropCost
00124   FmonotoneBoolGq<VA,VC>::cost(const Space&, const ModEventDelta&) const {
00125     return PropCost::linear(PropCost::LO, x.size());
00126   }
00127 
00128   template <class VA, class VC>
00129   ExecStatus
00130   FmonotoneBoolGq<VA,VC>::post(Space& home, int X, ViewArray<VA>& x, int l_x,
00131                                 int Y, ViewArray<VA>& y, int l_y, VC c, int precision) {
00132 
00133     (void) new (home) FmonotoneBoolGq<VA,VC>(home,X,x,l_x,Y,y,l_y,c,precision);
00134     return ES_OK;
00135   }
00136 
00137   template <class VA, class VC>
00138   Actor*
00139   FmonotoneBoolGq<VA,VC>::copy(Space& home, bool share) {
00140     return new (home) FmonotoneBoolGq<VA,VC>(home,share,*this);
00141   }
00142 
00143   template <class VA, class VC>
00144   ExecStatus
00145   FmonotoneBoolGq<VA,VC>::propagate(Space& home, const ModEventDelta&) {
00146     int u_x = 0; int u_y = 0;
00147     eliminate(x, l_x, u_x);
00148     eliminate(y, l_y, u_y);
00149     u_x += l_x;
00150     u_y += l_y;
00151     /*
00152     // Tias debug
00153     std::cerr << "X("<<X<<") "<<l_x<<" "<<u_x<<"\tY("<<Y<<") "<<l_y<<" "<<u_y;
00154     std::cerr << "u_x l_y "<<u_x<<" "<<l_y<<" : "<<monotone_function(X,u_x,Y,l_y,precision)
00155               <<" l_x u_y "<<l_x<<" "<<u_y<<" : "<<monotone_function(X,l_x,Y,u_y,precision)
00156               << " >?= " << c << std::endl;
00157     */
00158 
00159     // maximum of monotone function must be greater or equal than treshold
00160     if (monotone_function(X, u_x, Y, l_y, precision) < c.min()) {
00161       return ES_FAILED;
00162     } else if (x.size() == 0 && y.size() == 0) {
00163       return home.ES_SUBSUMED(*this);
00164     }
00165     return ES_FIX;
00166   }
00167 
00168   template <class VA, class VC>
00169   void FmonotoneBoolGq<VA,VC>::eliminate(ViewArray<VA>& v, int& l, int& u) {
00170     int n = v.size();
00171     for (int i = n; i--; )
00172       if (v[i].zero()) {
00173         v[i]=v[--n];
00174       } else if (v[i].one()) {
00175         v[i]=v[--n];
00176         l += 1;
00177       } else {
00178         u += 1;
00179       }
00180     v.size(n);
00181   }
00182 
00183 
00184   /** \brief Post propagator for the monotone function propagator for booleans
00185    * Calculates and prunes based on a monotone function value
00186    *
00187    */
00188   void monotone(Space& home,
00189                 const int classX_tot, const BoolVarArgs& classX,
00190                 const int classY_tot, const BoolVarArgs& classY,
00191                 IntRelType r, IntVar c, int precision) {
00192     if (home.failed()) return;
00193 
00194     // check float limit ?
00195 
00196     ViewArray<BoolView> classXv(home, classX);
00197     ViewArray<BoolView> classYv(home, classY);
00198 
00199     // Tias debug
00200     //std::cout << "gonna post: " << std::endl
00201     //          << xv << yv << std::endl
00202     //          << " and it better be good" << std::endl;
00203     // post
00204     if (r == IRT_GQ) {
00205         GECODE_ES_FAIL((FmonotoneBoolGq<BoolView,IntView>
00206                              ::post(home, classX_tot, classXv, 0, classY_tot, classYv, 0, c, precision)));
00207     } else {
00208       throw UnknownRelation("FmonotoneBool::convex");
00209     }
00210   }
00211 
00212 
00213 
00214 
00215   /************************************
00216    *      REIFY-IMPLIED               *
00217    ***********************************/
00218 
00219   /**
00220    * \brief Base-class for reify-implied monotone function boolean propagators
00221    *
00222    * This class NEEDS a global function:
00223    * monotone_function(int pos_total, int pos, int neg_total, int neg, int precision)
00224    */
00225   template <class VA, class VC>
00226   class ImplyFmonotoneBoolGq : public FmonotoneBoolGq<VA,VC> {
00227   protected:
00228     using FmonotoneBoolGq<VA,VC>::X;
00229     using FmonotoneBoolGq<VA,VC>::x;
00230     using FmonotoneBoolGq<VA,VC>::l_x;
00231     using FmonotoneBoolGq<VA,VC>::Y;
00232     using FmonotoneBoolGq<VA,VC>::y;
00233     using FmonotoneBoolGq<VA,VC>::l_y;
00234     using FmonotoneBoolGq<VA,VC>::c;
00235     using FmonotoneBoolGq<VA,VC>::precision;
00236     /// reify-implication variable
00237     BoolView b;
00238 
00239     ImplyFmonotoneBoolGq(Space& home, BoolView b, int X, ViewArray<VA>& x, int l_x,
00240             int Y, ViewArray<VA>& y, int l_y, VC c, int precision);
00241     /// Constructor for cloning \a p
00242     ImplyFmonotoneBoolGq(Space& home, bool share, ImplyFmonotoneBoolGq& p);
00243   public:
00244     /// Delete propagator and return its size
00245     virtual size_t dispose(Space& home);
00246     /// Create copy during cloning
00247     virtual Actor* copy(Space& home, bool share);
00248     /// Perform propagation
00249     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00250     /// Post propagator
00251     static ExecStatus post(Space& home, BoolView b, int X, ViewArray<VA>& x, int l_x, int Y, ViewArray<VA>& y, int l_y, VC c, int precision);
00252   };
00253 
00254   /*
00255    * reify-implied FmonotoneBoolGq Class
00256    */
00257   template <class VA, class VC>
00258   ImplyFmonotoneBoolGq<VA,VC>::ImplyFmonotoneBoolGq(Space& home, BoolView b0, int X0,
00259         ViewArray<VA>& x0, int l_x0, int Y0, ViewArray<VA>& y0, int l_y0, VC c0, int precision0)
00260     : FmonotoneBoolGq<VA,VC>(home,X0,x0,l_x0,Y0,y0,l_y0,c0,precision0), b(b0) {
00261     b.subscribe(home,*this,PC_INT_VAL);
00262   }
00263 
00264   template <class VA, class VC>
00265   forceinline
00266   ImplyFmonotoneBoolGq<VA,VC>::ImplyFmonotoneBoolGq(Space& home,
00267             bool share, ImplyFmonotoneBoolGq& p)
00268     : FmonotoneBoolGq<VA,VC>(home, share, p) {
00269     b.update(home,share,p.b);
00270   }
00271 
00272   template <class VA, class VC>
00273   forceinline size_t
00274   ImplyFmonotoneBoolGq<VA,VC>::dispose(Space& home) {
00275     assert(!home.failed());
00276     b.cancel(home,*this,PC_INT_VAL);
00277     return  FmonotoneBoolGq<VA,VC>::dispose(home);
00278   }
00279 
00280   template <class VA, class VC>
00281   Actor*
00282   ImplyFmonotoneBoolGq<VA,VC>::copy(Space& home, bool share) {
00283     return new (home) ImplyFmonotoneBoolGq<VA,VC>(home,share,*this);
00284   }
00285 
00286   template <class VA, class VC>
00287   ExecStatus
00288   ImplyFmonotoneBoolGq<VA,VC>::post(Space& home, BoolView b, int X, ViewArray<VA>& x, int l_x, int Y, ViewArray<VA>& y, int l_y, VC c, int precision) {
00289 
00290     (void) new (home) ImplyFmonotoneBoolGq<VA,VC>(home,b,X,x,l_x,Y,y,l_y,c,precision);
00291     return ES_OK;
00292   }
00293 
00294   template <class VA, class VC>
00295   ExecStatus
00296   ImplyFmonotoneBoolGq<VA,VC>::propagate(Space& home, const ModEventDelta&) {
00297     if (b.one())
00298         GECODE_REWRITE(*this,(FmonotoneBoolGq<VA,VC>::post(home,X,x,l_x,Y,y,l_y,c,precision)));
00299     if (b.zero())
00300         return home.ES_SUBSUMED(*this); // couldn't care less
00301 
00302     int u_x = 0; int u_y = 0;
00303     eliminate(x, l_x, u_x);
00304     eliminate(y, l_y, u_y);
00305     u_x += l_x;
00306     u_y += l_y;
00307     /*
00308     // Tias debug
00309     std::cerr << "X("<<X<<") "<<l_x<<" "<<u_x<<"\tY("<<Y<<") "<<l_y<<" "<<u_y;
00310     std::cerr <<" l_x u_y "<<l_x<<" "<<u_y<<" : "<<monotone_function(X,l_x,Y,u_y,precision)
00311               << "u_x l_y "<<u_x<<" "<<l_y<<" : "<<monotone_function(X,u_x,Y,l_y,precision)
00312               << " >?= " << c << std::endl;
00313     */
00314 
00315     // maximum of monotone function must be greater or equal than treshold
00316     if (monotone_function(X, u_x, Y, l_y, precision) < c.min()) {
00317       GECODE_ME_CHECK(b.zero_none(home));
00318       return home.ES_SUBSUMED(*this);
00319     } else if (x.size() == 0 && y.size() == 0) {
00320       return home.ES_SUBSUMED(*this); // couldn't care less
00321     }
00322     return ES_FIX;
00323   }
00324 
00325   /** \brief Post propagator for the convex chi2 propagator for booleans, reified version
00326    * Calculates and prunes based on the chi2 value
00327    *
00328    * The IntArgs represent the class and must be positive unit (0 or 1)
00329    * Returns Error if not positive unit.
00330    *
00331    */
00332   void imply_monotone(Space& home, const BoolVar b,
00333                 const int classX_tot, const BoolVarArgs& classX,
00334                 const int classY_tot, const BoolVarArgs& classY,
00335                 IntRelType r, IntVar c, int precision) {
00336     if (home.failed()) return;
00337 
00338     if (b.one()) {
00339         return monotone(home, classX_tot, classX, classY_tot, classY, r, c, precision);
00340     }
00341     if (b.zero())
00342         return; // couldn't care less
00343 
00344 
00345     // check float limit ?
00346 
00347     // Only accept IRT_GQ (for now)
00348     if (r != IRT_GQ)
00349       throw UnknownRelation("ConvexBool::imply_convex");
00350 
00351     ViewArray<BoolView> classXv(home, classX);
00352     ViewArray<BoolView> classYv(home, classY);
00353 
00354     // Tias debug
00355     //std::cout << "gonna post: " << std::endl
00356     //          << xv << yv << std::endl
00357     //          << " and it better be good" << std::endl;
00358     // post
00359     GECODE_ES_FAIL((ImplyFmonotoneBoolGq<BoolView,IntView>
00360                              ::post(home, b, classX_tot, classXv, 0,
00361                                              classY_tot, classYv, 0, c, precision)));
00362   }
00363 
00364 
00365 
00366 }