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: 2015-03-20 15:37:34 +0100 (Fri, 20 Mar 2015) $ by $Author: schulte $
00013  *     $Revision: 14471 $
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     long long int w = 0;
00057     for (int i=p.size(); i--; ) {
00058       Limits::nonnegative(p[i],"Int::cumulative");
00059       Limits::nonnegative(u[i],"Int::cumulative");
00060       Limits::check(static_cast<long long int>(s[i].max()) + p[i], 
00061                     "Int::cumulative");
00062       mul_check(p[i],u[i]);
00063       w += s[i].width();
00064     }
00065     mul_check(c.max(),w,s.size());
00066     if (home.failed()) return;
00067 
00068     int minU = INT_MAX; int minU2 = INT_MAX; int maxU = INT_MIN;
00069     for (int i=u.size(); i--;) {
00070       if (u[i] < minU) {
00071         minU2 = minU;
00072         minU = u[i];
00073       } else if (u[i] < minU2)
00074         minU2 = u[i];
00075       if (u[i] > maxU)
00076         maxU = u[i];
00077     }
00078     bool disjunctive =
00079       (minU > c.max()/2) || (minU2 > c.max()/2 && minU+minU2>c.max());
00080     if (disjunctive) {
00081       GECODE_ME_FAIL(c.gq(home,maxU));
00082       unary(home,t,s,p,icl);
00083     } else {
00084       bool fixp = true;
00085       for (int i=t.size(); i--;)
00086         if (t[i] != TT_FIXP) {
00087           fixp = false; break;
00088         }
00089       int nonOptionals = 0;
00090       for (int i=u.size(); i--;)
00091         if (u[i]>0) nonOptionals++;
00092       if (fixp) {
00093         TaskArray<ManFixPTask> tasks(home,nonOptionals);
00094         int cur = 0;
00095         for (int i=0; i<s.size(); i++)
00096           if (u[i] > 0)
00097             tasks[cur++].init(s[i],p[i],u[i]);
00098         GECODE_ES_FAIL((ManProp<ManFixPTask,Cap>::post(home,c,tasks)));
00099       } else {
00100         TaskArray<ManFixPSETask> tasks(home,nonOptionals);
00101         int cur = 0;
00102         for (int i=s.size(); i--;)
00103           if (u[i] > 0)
00104             tasks[cur++].init(t[i],s[i],p[i],u[i]);
00105         GECODE_ES_FAIL((ManProp<ManFixPSETask,Cap>::post(home,c,tasks)));
00106       }
00107     }
00108   }
00109 
00110   void
00111   cumulative(Home home, int c, const TaskTypeArgs& t,
00112              const IntVarArgs& s, const IntArgs& p, const IntArgs& u, 
00113              IntConLevel icl) {
00114     Int::Limits::nonnegative(c,"Int::cumulative");
00115     cumulative(home,Int::ConstIntView(c),t,s,p,u,icl);
00116   }
00117   void
00118   cumulative(Home home, IntVar c, const TaskTypeArgs& t,
00119              const IntVarArgs& s, const IntArgs& p, const IntArgs& u, 
00120              IntConLevel icl) {
00121     if (c.assigned())
00122       cumulative(home,c.val(),t,s,p,u,icl);
00123     else
00124       cumulative(home,Int::IntView(c),t,s,p,u,icl);
00125   }
00126 
00127   template<class Cap>
00128   void
00129   cumulative(Home home, Cap c, const TaskTypeArgs& t,
00130              const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
00131              const BoolVarArgs& m, IntConLevel icl) {
00132     using namespace Gecode::Int;
00133     using namespace Gecode::Int::Cumulative;
00134     if ((s.size() != p.size()) || (s.size() != u.size()) ||
00135         (s.size() != t.size()) || (s.size() != m.size()))
00136       throw Int::ArgumentSizeMismatch("Int::cumulative");
00137     long long int w = 0;
00138     for (int i=p.size(); i--; ) {
00139       Limits::nonnegative(p[i],"Int::cumulative");
00140       Limits::nonnegative(u[i],"Int::cumulative");
00141       Limits::check(static_cast<long long int>(s[i].max()) + p[i],
00142                     "Int::cumulative");
00143       mul_check(p[i],u[i]);
00144       w += s[i].width();
00145     }
00146     mul_check(c.max(),w,s.size());
00147     if (home.failed()) return;
00148     
00149     bool allMandatory = true;
00150     for (int i=m.size(); i--;) {
00151       if (!m[i].one()) {
00152         allMandatory = false;
00153         break;
00154       }
00155     }
00156     if (allMandatory) {
00157       cumulative(home,c,t,s,p,u,icl);
00158     } else {
00159       bool fixp = true;
00160       for (int i=t.size(); i--;)
00161         if (t[i] != TT_FIXP) {
00162           fixp = false; break;
00163         }
00164       int nonOptionals = 0;
00165       for (int i=u.size(); i--;)
00166         if (u[i]>0) nonOptionals++;
00167       if (fixp) {
00168         TaskArray<OptFixPTask> tasks(home,nonOptionals);
00169         int cur = 0;
00170         for (int i=0; i<s.size(); i++)
00171           if (u[i]>0)
00172             tasks[cur++].init(s[i],p[i],u[i],m[i]);
00173         GECODE_ES_FAIL((OptProp<OptFixPTask,Cap>::post(home,c,tasks)));
00174       } else {
00175         TaskArray<OptFixPSETask> tasks(home,nonOptionals);
00176         int cur = 0;
00177         for (int i=s.size(); i--;)
00178           if (u[i]>0)
00179             tasks[cur++].init(t[i],s[i],p[i],u[i],m[i]);
00180         GECODE_ES_FAIL((OptProp<OptFixPSETask,Cap>::post(home,c,tasks)));
00181       }
00182     }
00183   }
00184   
00185   void
00186   cumulative(Home home, int c, const TaskTypeArgs& t,
00187              const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
00188              const BoolVarArgs& m, IntConLevel icl) {
00189     Int::Limits::nonnegative(c,"Int::cumulative");
00190     cumulative(home,Int::ConstIntView(c),t,s,p,u,m,icl);
00191   }
00192   void
00193   cumulative(Home home, IntVar c, const TaskTypeArgs& t,
00194              const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
00195              const BoolVarArgs& m, IntConLevel icl) {
00196     if (c.assigned())
00197       cumulative(home,c.val(),t,s,p,u,m,icl);
00198     else
00199       cumulative(home,Int::IntView(c),t,s,p,u,m,icl);
00200   }
00201   
00202   template<class Cap>
00203   void
00204   cumulative(Home home, Cap c, const IntVarArgs& s, 
00205              const IntArgs& p, const IntArgs& u, IntConLevel icl) {
00206     using namespace Gecode::Int;
00207     using namespace Gecode::Int::Cumulative;
00208     if ((s.size() != p.size()) || (s.size() != u.size()))
00209       throw Int::ArgumentSizeMismatch("Int::cumulative");
00210     long long int w = 0;
00211     for (int i=p.size(); i--; ) {
00212       Limits::nonnegative(p[i],"Int::cumulative");
00213       Limits::nonnegative(u[i],"Int::cumulative");
00214       Limits::check(static_cast<long long int>(s[i].max()) + p[i],
00215                     "Int::cumulative");
00216       mul_check(p[i],u[i]);
00217       w += s[i].width();
00218     }
00219     mul_check(c.max(),w,s.size());
00220     if (home.failed()) return;
00221 
00222     int minU = INT_MAX; int minU2 = INT_MAX; int maxU = INT_MIN;
00223     for (int i=u.size(); i--;) {
00224       if (u[i] < minU) {
00225         minU2 = minU;
00226         minU = u[i];
00227       } else if (u[i] < minU2)
00228         minU2 = u[i];
00229       if (u[i] > maxU)
00230         maxU = u[i];
00231     }
00232     bool disjunctive = 
00233       (minU > c.max()/2) || (minU2 > c.max()/2 && minU+minU2>c.max());
00234     if (disjunctive) {
00235       GECODE_ME_FAIL(c.gq(home,maxU));
00236       unary(home,s,p,icl);
00237     } else {
00238       int nonOptionals = 0;
00239       for (int i=u.size(); i--;)
00240         if (u[i]>0) nonOptionals++;
00241       TaskArray<ManFixPTask> t(home,nonOptionals);
00242       int cur = 0;
00243       for (int i=0; i<s.size(); i++)
00244         if (u[i]>0)
00245           t[cur++].init(s[i],p[i],u[i]);
00246       GECODE_ES_FAIL((ManProp<ManFixPTask,Cap>::post(home,c,t)));
00247     }
00248   }
00249 
00250   void
00251   cumulative(Home home, int c, const IntVarArgs& s, 
00252              const IntArgs& p, const IntArgs& u, IntConLevel icl) {
00253     Int::Limits::nonnegative(c,"Int::cumulative");
00254     cumulative(home,Int::ConstIntView(c),s,p,u,icl);
00255   }
00256   void
00257   cumulative(Home home, IntVar c, const IntVarArgs& s, 
00258              const IntArgs& p, const IntArgs& u, IntConLevel icl) {
00259     if (c.assigned())
00260       cumulative(home,c.val(),s,p,u,icl);
00261     else
00262       cumulative(home,Int::IntView(c),s,p,u,icl);
00263   }
00264   
00265   template<class Cap>
00266   void
00267   cumulative(Home home, Cap c, const IntVarArgs& s, const IntArgs& p, 
00268              const IntArgs& u, const BoolVarArgs& m, IntConLevel icl) {
00269     using namespace Gecode::Int;
00270     using namespace Gecode::Int::Cumulative;
00271     if ((s.size() != p.size()) || (s.size() != u.size()) ||
00272         (s.size() != m.size()))
00273       throw Int::ArgumentSizeMismatch("Int::cumulative");
00274     long long int w = 0;
00275     for (int i=p.size(); i--; ) {
00276       Limits::nonnegative(p[i],"Int::cumulative");
00277       Limits::nonnegative(u[i],"Int::cumulative");
00278       Limits::check(static_cast<long long int>(s[i].max()) + p[i],
00279                     "Int::cumulative");
00280       mul_check(p[i],u[i]);
00281       w += s[i].width();
00282     }
00283     mul_check(c.max(),w,s.size());
00284     if (home.failed()) return;
00285 
00286     bool allMandatory = true;
00287     for (int i=m.size(); i--;) {
00288       if (!m[i].one()) {
00289         allMandatory = false;
00290         break;
00291       }
00292     }
00293     if (allMandatory) {
00294       cumulative(home,c,s,p,u,icl);
00295     } else {
00296       int nonOptionals = 0;
00297       for (int i=u.size(); i--;)
00298         if (u[i]>0) nonOptionals++;
00299       TaskArray<OptFixPTask> t(home,nonOptionals);
00300       int cur = 0;
00301       for (int i=0; i<s.size(); i++)
00302         if (u[i]>0)
00303           t[cur++].init(s[i],p[i],u[i],m[i]);
00304       GECODE_ES_FAIL((OptProp<OptFixPTask,Cap>::post(home,c,t)));
00305     }
00306   }
00307 
00308   void
00309   cumulative(Home home, int c, const IntVarArgs& s, const IntArgs& p, 
00310              const IntArgs& u, const BoolVarArgs& m, IntConLevel icl) {
00311     Int::Limits::nonnegative(c,"Int::cumulative");
00312     cumulative(home,Int::ConstIntView(c),s,p,u,m,icl);
00313   }
00314   void
00315   cumulative(Home home, IntVar c, const IntVarArgs& s, const IntArgs& p, 
00316              const IntArgs& u, const BoolVarArgs& m, IntConLevel icl) {
00317     if (c.assigned())
00318       cumulative(home,c.val(),s,p,u,m,icl);
00319     else
00320       cumulative(home,Int::IntView(c),s,p,u,m,icl);
00321   }
00322 
00323   template<class Cap>
00324   void
00325   cumulative(Home home, Cap c, const IntVarArgs& s, 
00326              const IntVarArgs& p, const IntVarArgs& e,
00327              const IntArgs& u, IntConLevel icl) {
00328     using namespace Gecode::Int;
00329     using namespace Gecode::Int::Cumulative;
00330     if ((s.size() != p.size()) || (s.size() != e.size()) ||
00331         (s.size() != u.size()))
00332       throw Int::ArgumentSizeMismatch("Int::cumulative");
00333     long long int w = 0;
00334     for (int i=p.size(); i--; ) {
00335       rel(home, p[i], IRT_GQ, 0);
00336     }
00337     for (int i=p.size(); i--; ) {
00338       Limits::nonnegative(u[i],"Int::cumulative");
00339       Limits::check(static_cast<long long int>(s[i].max()) + p[i].max(),
00340                     "Int::cumulative");
00341       mul_check(p[i].max(),u[i]);
00342       w += s[i].width();
00343     }
00344     mul_check(c.max(),w,s.size());
00345     if (home.failed()) return;
00346 
00347     bool fixP = true;
00348     for (int i=p.size(); i--;) {
00349       if (!p[i].assigned()) {
00350         fixP = false;
00351         break;
00352       }
00353     }
00354     if (fixP) {
00355       IntArgs pp(p.size());
00356       for (int i=p.size(); i--;)
00357         pp[i] = p[i].val();
00358       cumulative(home,c,s,pp,u,icl);
00359     } else {
00360       int nonOptionals = 0;
00361       for (int i=u.size(); i--;)
00362         if (u[i]>0) nonOptionals++;
00363       TaskArray<ManFlexTask> t(home,nonOptionals);
00364       int cur = 0;
00365       for (int i=0; i<s.size(); i++)
00366         if (u[i]>0)
00367           t[cur++].init(s[i],p[i],e[i],u[i]);
00368       GECODE_ES_FAIL((ManProp<ManFlexTask,Cap>::post(home,c,t)));
00369     }
00370   }
00371 
00372   void
00373   cumulative(Home home, int c, const IntVarArgs& s, 
00374              const IntVarArgs& p, const IntVarArgs& e,
00375              const IntArgs& u, IntConLevel icl) {
00376     Int::Limits::nonnegative(c,"Int::cumulative");
00377     cumulative(home,Int::ConstIntView(c),s,p,e,u,icl);
00378   }
00379   void
00380   cumulative(Home home, IntVar c, const IntVarArgs& s, 
00381              const IntVarArgs& p, const IntVarArgs& e,
00382              const IntArgs& u, IntConLevel icl) {
00383     if (c.assigned())
00384       cumulative(home,c.val(),s,p,e,u,icl);
00385     else
00386       cumulative(home,Int::IntView(c),s,p,e,u,icl);
00387   }
00388 
00389   template<class Cap>
00390   void
00391   cumulative(Home home, Cap c, const IntVarArgs& s, const IntVarArgs& p,
00392              const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m, 
00393              IntConLevel icl) {
00394     using namespace Gecode::Int;
00395     using namespace Gecode::Int::Cumulative;
00396     if ((s.size() != p.size()) || (s.size() != u.size()) ||
00397         (s.size() != e.size()) || (s.size() != m.size()))
00398       throw Int::ArgumentSizeMismatch("Int::cumulative");
00399     for (int i=p.size(); i--; ) {
00400       rel(home, p[i], IRT_GQ, 0);
00401     }
00402     long long int w = 0;
00403     for (int i=p.size(); i--; ) {
00404       Limits::nonnegative(u[i],"Int::cumulative");
00405       Limits::check(static_cast<long long int>(s[i].max()) + p[i].max(),
00406                     "Int::cumulative");
00407       mul_check(p[i].max(),u[i]);
00408       w += s[i].width();
00409     }
00410     mul_check(c.max(),w,s.size());
00411     if (home.failed()) return;
00412 
00413     bool allMandatory = true;
00414     for (int i=m.size(); i--;) {
00415       if (!m[i].one()) {
00416         allMandatory = false;
00417         break;
00418       }
00419     }
00420     if (allMandatory) {
00421       cumulative(home,c,s,p,e,u,icl);
00422     } else {
00423       int nonOptionals = 0;
00424       for (int i=u.size(); i--;)
00425         if (u[i]>0) nonOptionals++;
00426       TaskArray<OptFlexTask> t(home,nonOptionals);
00427       int cur = 0;
00428       for (int i=s.size(); i--; )
00429         if (u[i]>0)
00430           t[cur++].init(s[i],p[i],e[i],u[i],m[i]);
00431       GECODE_ES_FAIL((OptProp<OptFlexTask,Cap>::post(home,c,t)));
00432     }
00433   }
00434 
00435   void
00436   cumulative(Home home, int c, const IntVarArgs& s, const IntVarArgs& p,
00437              const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m, 
00438              IntConLevel icl) {
00439     Int::Limits::nonnegative(c,"Int::cumulative");
00440     cumulative(home,Int::ConstIntView(c),s,p,e,u,m,icl);
00441   }
00442   void
00443   cumulative(Home home, IntVar c, const IntVarArgs& s, const IntVarArgs& p,
00444              const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m, 
00445              IntConLevel icl) {
00446     if (c.assigned())
00447       cumulative(home,c.val(),s,p,e,u,m,icl);
00448     else
00449       cumulative(home,Int::IntView(c),s,p,e,u,m,icl);
00450   }
00451   
00452 }
00453 
00454 // STATISTICS: int-post