Generated on Sun Feb 17 15:24:29 2019 for Gecode by doxygen 1.6.3

pbs.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2015
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
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 <climits>
00035 
00036 namespace Gecode { namespace Search { namespace Seq {
00037 
00038 
00039   forceinline
00040   PortfolioStop::PortfolioStop(Stop* so0)
00041     : so(so0) {}
00042   forceinline void
00043   PortfolioStop::share(SharedStopInfo* ssi0) {
00044     ssi = ssi0;
00045   }
00046 
00047 
00048   forceinline void
00049   Slave::init(Engine* e, Stop* s) {
00050     slave = e; stop = s;
00051   }
00052   forceinline Space*
00053   Slave::next(void) {
00054     return slave->next();
00055   }
00056   forceinline Statistics
00057   Slave::statistics(void) const {
00058     return slave->statistics();
00059   }
00060   forceinline bool
00061   Slave::stopped(void) const {
00062     return slave->stopped();
00063   }
00064   forceinline void
00065   Slave::constrain(const Space& b) {
00066     slave->constrain(b);
00067   }
00068   forceinline
00069   Slave::~Slave(void) {
00070     delete slave;
00071     delete stop;
00072   }
00073 
00074 
00075   template<bool best>
00076   forceinline
00077   PBS<best>::PBS(Engine** e, Stop** s, unsigned int n,
00078                  const Statistics& stat0,
00079                  const Search::Options& opt)
00080     : stat(stat0), slice(opt.slice),
00081       slaves(heap.alloc<Slave>(n)), n_slaves(n), cur(0),
00082       slave_stop(false) {
00083     ssi.done = false;
00084     ssi.l = opt.slice;
00085 
00086     for (unsigned int i=0U; i<n; i++) {
00087       slaves[i].init(e[i],static_cast<PortfolioStop*>(s[i]));
00088       static_cast<PortfolioStop*>(s[i])->share(&ssi);
00089     }
00090   }
00091 
00092   template<bool best>
00093   Space*
00094   PBS<best>::next(void) {
00095     slave_stop = false;
00096     unsigned int n_exhausted = 0;
00097     while (n_slaves > 0) {
00098       if (Space* s = slaves[cur].next()) {
00099         // Constrain other slaves
00100         if (best) {
00101           for (unsigned int i=0U; i<cur; i++)
00102             slaves[i].constrain(*s);
00103           for (unsigned int i=cur+1; i<n_slaves; i++)
00104             slaves[i].constrain(*s);
00105         }
00106         return s;
00107       }
00108       if (slaves[cur].stopped()) {
00109         if (ssi.done) {
00110           cur++; n_exhausted++;
00111         } else {
00112           slave_stop = true;
00113           return NULL;
00114         }
00115       } else {
00116         // This slave is done, kill it after saving the statistics
00117         stat += slaves[cur].statistics();
00118         slaves[cur].~Slave();
00119         slaves[cur] = slaves[--n_slaves];
00120         if (n_slaves == 1)
00121           // Disable stoping by seeting a high limit
00122           ssi.l = ULONG_MAX;
00123       }
00124       if (n_exhausted == n_slaves) {
00125         n_exhausted = 0;
00126         // Increment by one slice
00127         ssi.l += slice;
00128       }
00129       if (cur == n_slaves)
00130         cur = 0;
00131     }
00132     return NULL;
00133   }
00134 
00135   template<bool best>
00136   bool
00137   PBS<best>::stopped(void) const {
00138     return slave_stop;
00139   }
00140 
00141   template<bool best>
00142   Statistics
00143   PBS<best>::statistics(void) const {
00144     Statistics s(stat);
00145     for (unsigned int i=0U; i<n_slaves; i++)
00146       s += slaves[i].statistics();
00147     return s;
00148   }
00149 
00150   template<bool best>
00151   void
00152   PBS<best>::constrain(const Space& b) {
00153     if (!best)
00154       throw NoBest("PBS::constrain");
00155     for (unsigned int i=0U; i<n_slaves; i++)
00156       slaves[i].constrain(b);
00157   }
00158 
00159   template<bool best>
00160   PBS<best>::~PBS(void) {
00161     for (unsigned int i=0U; i<n_slaves; i++)
00162       slaves[i].~Slave();
00163     // Note that n_slaves might be different now!
00164     heap.rfree(slaves);
00165   }
00166 
00167 }}}
00168 
00169 // STATISTICS: search-seq