cumulative.cpp

00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *     Guido Tack <tack@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Christian Schulte, 2009
00009  *     Guido Tack, 2010
00010  *
00011  *  Last modified:
00012  *     $Date: 2011-07-13 18:56:36 +0200 (Wed, 13 Jul 2011) $ by $Author: tack $
00013  *     $Revision: 12195 $
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 #include <gecode/int/cumulative.hh>
00041 
00042 #include <algorithm>
00043 
00044 namespace Gecode {
00045 
00046   template<class Cap>
00047   void
00048   cumulative(Home home, Cap c, const TaskTypeArgs& t,
00049              const IntVarArgs& s, const IntArgs& p, const IntArgs& u, 
00050              IntConLevel icl) {
00051     using namespace Gecode::Int;
00052     using namespace Gecode::Int::Cumulative;
00053     if ((s.size() != p.size()) || (s.size() != u.size()) ||
00054         (s.size() != t.size()))
00055       throw Int::ArgumentSizeMismatch("Int::cumulative");
00056     double w = 0.0;
00057     for (int i=p.size(); i--; ) {
00058       Int::Limits::nonnegative(p[i],"Int::cumulative");
00059       Int::Limits::nonnegative(u[i],"Int::cumulative");
00060       Int::Limits::check(static_cast<double>(s[i].max()) + p[i],
00061                          "Int::cumulative");
00062       Int::Limits::double_check(static_cast<double>(p[i]) * u[i],
00063                                 "Int::cumulative");
00064       w += s[i].width();
00065     }
00066     Int::Limits::double_check(c.max() * w * s.size(),
00067                               "Int::cumulative");
00068     if (home.failed()) return;
00069 
00070     int minU = INT_MAX; int minU2 = INT_MAX; int maxU = INT_MIN;
00071     for (int i=u.size(); i--;) {
00072       if (u[i] < minU)
00073         minU = u[i];
00074       else if (u[i] < minU2)
00075         minU2 = u[i];
00076       if (u[i] > maxU)
00077         maxU = u[i];
00078     }
00079     bool disjunctive =
00080       (minU > c.max()/2) || (minU2 > c.max()/2 && minU+minU2>c.max());
00081     if (disjunctive) {
00082       GECODE_ME_FAIL(c.gq(home,maxU));
00083       unary(home,t,s,p,icl);
00084     } else {
00085       bool fixp = true;
00086       for (int i=t.size(); i--;)
00087         if (t[i] != TT_FIXP) {
00088           fixp = false; break;
00089         }
00090       if (fixp) {
00091         TaskArray<ManFixPTask> tasks(home,s.size());
00092         for (int i=0; i<s.size(); i++)
00093           tasks[i].init(s[i],p[i],u[i]);
00094         GECODE_ES_FAIL((ManProp<ManFixPTask,Cap>::post(home,c,tasks)));
00095       } else {
00096         TaskArray<ManFixPSETask> tasks(home,s.size());
00097         for (int i=s.size(); i--;)
00098           tasks[i].init(t[i],s[i],p[i],u[i]);
00099         GECODE_ES_FAIL((ManProp<ManFixPSETask,Cap>::post(home,c,tasks)));
00100       }
00101     }
00102   }
00103 
00104   void
00105   cumulative(Home home, int c, const TaskTypeArgs& t,
00106              const IntVarArgs& s, const IntArgs& p, const IntArgs& u, 
00107              IntConLevel icl) {
00108     Int::Limits::nonnegative(c,"Int::cumulative");
00109     cumulative(home,Int::ConstIntView(c),t,s,p,u,icl);
00110   }
00111   void
00112   cumulative(Home home, IntVar c, const TaskTypeArgs& t,
00113              const IntVarArgs& s, const IntArgs& p, const IntArgs& u, 
00114              IntConLevel icl) {
00115     if (c.assigned())
00116       cumulative(home,c.val(),t,s,p,u,icl);
00117     else
00118       cumulative(home,Int::IntView(c),t,s,p,u,icl);
00119   }
00120 
00121   template<class Cap>
00122   void
00123   cumulative(Home home, Cap c, const TaskTypeArgs& t,
00124              const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
00125              const BoolVarArgs& m, IntConLevel icl) {
00126     using namespace Gecode::Int;
00127     using namespace Gecode::Int::Cumulative;
00128     if ((s.size() != p.size()) || (s.size() != u.size()) ||
00129         (s.size() != t.size()) || (s.size() != m.size()))
00130       throw Int::ArgumentSizeMismatch("Int::cumulative");
00131     double w = 0.0;
00132     for (int i=p.size(); i--; ) {
00133       Int::Limits::nonnegative(p[i],"Int::cumulative");
00134       Int::Limits::nonnegative(u[i],"Int::cumulative");
00135       Int::Limits::check(static_cast<double>(s[i].max()) + p[i],
00136                          "Int::cumulative");
00137       Int::Limits::double_check(static_cast<double>(p[i]) * u[i],
00138                                 "Int::cumulative");
00139       w += s[i].width();
00140     }
00141     Int::Limits::double_check(c.max() * w * s.size(),
00142                               "Int::cumulative");
00143     if (home.failed()) return;
00144     
00145     bool allMandatory = true;
00146     for (int i=m.size(); i--;) {
00147       if (!m[i].one()) {
00148         allMandatory = false;
00149         break;
00150       }
00151     }
00152     if (allMandatory) {
00153       cumulative(home,c,t,s,p,u,icl);
00154     } else {
00155       bool fixp = true;
00156       for (int i=t.size(); i--;)
00157         if (t[i] != TT_FIXP) {
00158           fixp = false; break;
00159         }
00160       if (fixp) {
00161         TaskArray<OptFixPTask> tasks(home,s.size());
00162         for (int i=0; i<s.size(); i++)
00163           tasks[i].init(s[i],p[i],u[i],m[i]);
00164         GECODE_ES_FAIL((OptProp<OptFixPTask,Cap>::post(home,c,tasks)));
00165       } else {
00166         TaskArray<OptFixPSETask> tasks(home,s.size());
00167         for (int i=s.size(); i--;)
00168           tasks[i].init(t[i],s[i],p[i],u[i],m[i]);
00169         GECODE_ES_FAIL((OptProp<OptFixPSETask,Cap>::post(home,c,tasks)));
00170       }
00171     }
00172   }
00173   
00174   void
00175   cumulative(Home home, int c, const TaskTypeArgs& t,
00176              const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
00177              const BoolVarArgs& m, IntConLevel icl) {
00178     Int::Limits::nonnegative(c,"Int::cumulative");
00179     cumulative(home,Int::ConstIntView(c),t,s,p,u,m,icl);
00180   }
00181   void
00182   cumulative(Home home, IntVar c, const TaskTypeArgs& t,
00183              const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
00184              const BoolVarArgs& m, IntConLevel icl) {
00185     if (c.assigned())
00186       cumulative(home,c.val(),t,s,p,u,m,icl);
00187     else
00188       cumulative(home,Int::IntView(c),t,s,p,u,m,icl);
00189   }
00190   
00191   template<class Cap>
00192   void
00193   cumulative(Home home, Cap c, const IntVarArgs& s, 
00194              const IntArgs& p, const IntArgs& u, IntConLevel icl) {
00195     using namespace Gecode::Int;
00196     using namespace Gecode::Int::Cumulative;
00197     if ((s.size() != p.size()) || (s.size() != u.size()))
00198       throw Int::ArgumentSizeMismatch("Int::cumulative");
00199     double w = 0.0;
00200     for (int i=p.size(); i--; ) {
00201       Int::Limits::nonnegative(p[i],"Int::cumulative");
00202       Int::Limits::nonnegative(u[i],"Int::cumulative");
00203       Int::Limits::check(static_cast<double>(s[i].max()) + p[i],
00204                          "Int::cumulative");
00205       Int::Limits::double_check(static_cast<double>(p[i]) * u[i],
00206                                 "Int::cumulative");
00207       w += s[i].width();
00208     }
00209     Int::Limits::double_check(c.max() * w * s.size(),
00210                               "Int::cumulative");
00211     if (home.failed()) return;
00212 
00213     int minU = INT_MAX; int minU2 = INT_MAX; int maxU = INT_MIN;
00214     for (int i=u.size(); i--;) {
00215       if (u[i] < minU)
00216         minU = u[i];
00217       else if (u[i] < minU2)
00218         minU2 = u[i];
00219       if (u[i] > maxU)
00220         maxU = u[i];
00221     }
00222     bool disjunctive = 
00223       (minU > c.max()/2) || (minU2 > c.max()/2 && minU+minU2>c.max());
00224     if (disjunctive) {
00225       GECODE_ME_FAIL(c.gq(home,maxU));
00226       unary(home,s,p,icl);
00227     } else {
00228       TaskArray<ManFixPTask> t(home,s.size());
00229       for (int i=0; i<s.size(); i++) {
00230         t[i].init(s[i],p[i],u[i]);
00231       }
00232       GECODE_ES_FAIL((ManProp<ManFixPTask,Cap>::post(home,c,t)));
00233     }
00234   }
00235 
00236   void
00237   cumulative(Home home, int c, const IntVarArgs& s, 
00238              const IntArgs& p, const IntArgs& u, IntConLevel icl) {
00239     Int::Limits::nonnegative(c,"Int::cumulative");
00240     cumulative(home,Int::ConstIntView(c),s,p,u,icl);
00241   }
00242   void
00243   cumulative(Home home, IntVar c, const IntVarArgs& s, 
00244              const IntArgs& p, const IntArgs& u, IntConLevel icl) {
00245     if (c.assigned())
00246       cumulative(home,c.val(),s,p,u,icl);
00247     else
00248       cumulative(home,Int::IntView(c),s,p,u,icl);
00249   }
00250   
00251   template<class Cap>
00252   void
00253   cumulative(Home home, Cap c, const IntVarArgs& s, const IntArgs& p, 
00254              const IntArgs& u, const BoolVarArgs& m, IntConLevel icl) {
00255     using namespace Gecode::Int;
00256     using namespace Gecode::Int::Cumulative;
00257     if ((s.size() != p.size()) || (s.size() != u.size()) ||
00258         (s.size() != m.size()))
00259       throw Int::ArgumentSizeMismatch("Int::cumulative");
00260     double w = 0.0;
00261     for (int i=p.size(); i--; ) {
00262       Int::Limits::nonnegative(p[i],"Int::cumulative");
00263       Int::Limits::nonnegative(u[i],"Int::cumulative");
00264       Int::Limits::check(static_cast<double>(s[i].max()) + p[i],
00265                          "Int::cumulative");
00266       Int::Limits::double_check(static_cast<double>(p[i]) * u[i],
00267                                 "Int::cumulative");
00268       w += s[i].width();
00269     }
00270     Int::Limits::double_check(c.max() * w * s.size(),
00271                               "Int::cumulative");
00272     if (home.failed()) return;
00273 
00274     bool allMandatory = true;
00275     for (int i=m.size(); i--;) {
00276       if (!m[i].one()) {
00277         allMandatory = false;
00278         break;
00279       }
00280     }
00281     if (allMandatory) {
00282       cumulative(home,c,s,p,u,icl);
00283     } else {
00284       TaskArray<OptFixPTask> t(home,s.size());
00285       for (int i=0; i<s.size(); i++) {
00286         t[i].init(s[i],p[i],u[i],m[i]);
00287       }
00288       GECODE_ES_FAIL((OptProp<OptFixPTask,Cap>::post(home,c,t)));
00289     }
00290   }
00291 
00292   void
00293   cumulative(Home home, int c, const IntVarArgs& s, const IntArgs& p, 
00294              const IntArgs& u, const BoolVarArgs& m, IntConLevel icl) {
00295     Int::Limits::nonnegative(c,"Int::cumulative");
00296     cumulative(home,Int::ConstIntView(c),s,p,u,m,icl);
00297   }
00298   void
00299   cumulative(Home home, IntVar c, const IntVarArgs& s, const IntArgs& p, 
00300              const IntArgs& u, const BoolVarArgs& m, IntConLevel icl) {
00301     if (c.assigned())
00302       cumulative(home,c.val(),s,p,u,m,icl);
00303     else
00304       cumulative(home,Int::IntView(c),s,p,u,m,icl);
00305   }
00306 
00307   template<class Cap>
00308   void
00309   cumulative(Home home, Cap c, const IntVarArgs& s, 
00310              const IntVarArgs& p, const IntVarArgs& e,
00311              const IntArgs& u, IntConLevel icl) {
00312     using namespace Gecode::Int;
00313     using namespace Gecode::Int::Cumulative;
00314     if ((s.size() != p.size()) || (s.size() != e.size()) ||
00315         (s.size() != u.size()))
00316       throw Int::ArgumentSizeMismatch("Int::cumulative");
00317     double w = 0.0;
00318     for (int i=p.size(); i--; ) {
00319       rel(home, p[i], IRT_GQ, 0);
00320     }
00321     for (int i=p.size(); i--; ) {
00322       Int::Limits::nonnegative(u[i],"Int::cumulative");
00323       Int::Limits::check(static_cast<double>(s[i].max()) + p[i].max(),
00324                          "Int::cumulative");
00325       Int::Limits::double_check(static_cast<double>(p[i].max()) * u[i],
00326                                 "Int::cumulative");
00327       w += s[i].width();
00328     }
00329     Int::Limits::double_check(c.max() * w * s.size(),
00330                               "Int::cumulative");
00331     if (home.failed()) return;
00332 
00333     bool fixP = true;
00334     for (int i=p.size(); i--;) {
00335       if (!p[i].assigned()) {
00336         fixP = false;
00337         break;
00338       }
00339     }
00340     if (fixP) {
00341       IntArgs pp(p.size());
00342       for (int i=p.size(); i--;)
00343         pp[i] = p[i].val();
00344       cumulative(home,c,s,pp,u,icl);
00345     } else {
00346       TaskArray<ManFlexTask> t(home,s.size());
00347       for (int i=s.size(); i--; )
00348         t[i].init(s[i],p[i],e[i],u[i]);
00349       GECODE_ES_FAIL((ManProp<ManFlexTask,Cap>::post(home,c,t)));
00350     }
00351   }
00352 
00353   void
00354   cumulative(Home home, int c, const IntVarArgs& s, 
00355              const IntVarArgs& p, const IntVarArgs& e,
00356              const IntArgs& u, IntConLevel icl) {
00357     Int::Limits::nonnegative(c,"Int::cumulative");
00358     cumulative(home,Int::ConstIntView(c),s,p,e,u,icl);
00359   }
00360   void
00361   cumulative(Home home, IntVar c, const IntVarArgs& s, 
00362              const IntVarArgs& p, const IntVarArgs& e,
00363              const IntArgs& u, IntConLevel icl) {
00364     if (c.assigned())
00365       cumulative(home,c.val(),s,p,e,u,icl);
00366     else
00367       cumulative(home,Int::IntView(c),s,p,e,u,icl);
00368   }
00369 
00370   template<class Cap>
00371   void
00372   cumulative(Home home, Cap c, const IntVarArgs& s, const IntVarArgs& p,
00373              const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m, 
00374              IntConLevel icl) {
00375     using namespace Gecode::Int;
00376     using namespace Gecode::Int::Cumulative;
00377     if ((s.size() != p.size()) || (s.size() != u.size()) ||
00378         (s.size() != e.size()) || (s.size() != m.size()))
00379       throw Int::ArgumentSizeMismatch("Int::cumulative");
00380     for (int i=p.size(); i--; ) {
00381       rel(home, p[i], IRT_GQ, 0);
00382     }
00383     double w = 0.0;
00384     for (int i=p.size(); i--; ) {
00385       Int::Limits::nonnegative(u[i],"Int::cumulative");
00386       Int::Limits::check(static_cast<double>(s[i].max()) + p[i].max(),
00387                          "Int::cumulative");
00388       Int::Limits::double_check(static_cast<double>(p[i].max()) * u[i],
00389                                 "Int::cumulative");
00390       w += s[i].width();
00391     }
00392     Int::Limits::double_check(c.max() * w * s.size(),
00393                               "Int::cumulative");
00394     if (home.failed()) return;
00395 
00396     bool allMandatory = true;
00397     for (int i=m.size(); i--;) {
00398       if (!m[i].one()) {
00399         allMandatory = false;
00400         break;
00401       }
00402     }
00403     if (allMandatory) {
00404       cumulative(home,c,s,p,e,u,icl);
00405     } else {
00406       TaskArray<OptFlexTask> t(home,s.size());
00407       for (int i=s.size(); i--; )
00408         t[i].init(s[i],p[i],e[i],u[i],m[i]);
00409       GECODE_ES_FAIL((OptProp<OptFlexTask,Cap>::post(home,c,t)));
00410     }
00411   }
00412 
00413   void
00414   cumulative(Home home, int c, const IntVarArgs& s, const IntVarArgs& p,
00415              const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m, 
00416              IntConLevel icl) {
00417     Int::Limits::nonnegative(c,"Int::cumulative");
00418     cumulative(home,Int::ConstIntView(c),s,p,e,u,m,icl);
00419   }
00420   void
00421   cumulative(Home home, IntVar c, const IntVarArgs& s, const IntVarArgs& p,
00422              const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m, 
00423              IntConLevel icl) {
00424     if (c.assigned())
00425       cumulative(home,c.val(),s,p,e,u,m,icl);
00426     else
00427       cumulative(home,Int::IntView(c),s,p,e,u,m,icl);
00428   }
00429   
00430 }
00431 
00432 // STATISTICS: int-post