1/* BEGIN LICENSE BLOCK 2 * Version: CMPL 1.1 3 * 4 * The contents of this file are subject to the Cisco-style Mozilla Public 5 * License Version 1.1 (the "License"); you may not use this file except 6 * in compliance with the License. You may obtain a copy of the License 7 * at www.eclipse-clp.org/license. 8 * 9 * Software distributed under the License is distributed on an "AS IS" 10 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 11 * the License for the specific language governing rights and limitations 12 * under the License. 13 * 14 * The Original Code is The ECLiPSe Constraint Logic Programming System. 15 * The Initial Developer of the Original Code is Cisco Systems, Inc. 16 * Portions created by the Initial Developer are 17 * Copyright (C) 2006 Cisco Systems, Inc. All Rights Reserved. 18 * 19 * Contributor(s): Kish Shen, CrossCore Optimization. 20 * 21 * END LICENSE BLOCK */ 22 23#include <gecode/int.hh> 24#include <gecode/minimodel.hh> 25#include <gecode/search.hh> 26/* not used in Gecode >= 3.6.0 27#include <gecode/graph.hh> 28#include <gecode/scheduling.hh> 29*/ 30#include <vector> 31 32#if defined(__APPLE__) && defined(__MACH__) 33/* Mac OS X */ 34 35# define VisAtt __attribute__((visibility ("default"))) 36 37#else 38 39# define VisAtt 40 41#endif 42 43using namespace Gecode; 44 45class GecodeSpace : public Gecode::MinimizeSpace { 46public: 47 Gecode::IntVarArgs vInt; // vInt[0] not used, to match ECLiPSe 48 Gecode::BoolVarArgs vBool; // for linked booleans 49 Gecode::BoolVar booltrue; // true and false constants, for convenience 50 Gecode::BoolVar boolfalse; 51 Gecode::IntVar vCost; // objective val for min 52 53 GecodeSpace(void) : vInt(*this, 1, 0, 0), vBool(*this, 0, 0, 0), 54 booltrue(*this, 1, 1), boolfalse(*this, 0, 0), 55 vCost(*this, 0, 0), 56 first(true), 57 d_args(NULL), 58 actp(NULL), 59 valid_snapshot(false) {} 60 61 std::vector<int> dom_snapshot; 62 63 void set_snapshot() {valid_snapshot = true;} 64 void clear_snapshot() {valid_snapshot = false;} 65 bool snapshot_valid() {return valid_snapshot;} 66 67 void stop_caching() {first = false;} 68 void start_caching() {first = true;} 69 bool is_first() {return first;} 70 71 void set_d_args(double* m) {delete d_args; d_args = m;} 72 double get_d_args(int i) const { 73 return ((d_args != NULL) ? d_args[i] : 0.0); 74 } 75 76 // for using activity for var selection in C++ 77 bool init_select_activity(IntVarArgs& vars, double decay, IntBranchMerit initf) { 78 if (actp == NULL) { 79 actp = new IntActivity(*this, vars, decay, initf); 80 return true; 81 } else 82 return false; 83 } 84 double get_select_activity(int idx) { 85 return ((actp != NULL) ? (*actp)[idx] : -1); 86 } 87 88 GecodeSpace(bool share, GecodeSpace& s) : vInt(s.vInt.size()), vBool(s.vBool.size()), 89 valid_snapshot(s.valid_snapshot), 90 first(true), 91 booltrue(*this, 1, 1), boolfalse(*this, 0, 0), 92 d_args(NULL), 93 actp(NULL), 94 Gecode::MinimizeSpace(share,s) { 95// valid_snapshot = s.valid_snapshot; 96 if (snapshot_valid()) dom_snapshot = s.dom_snapshot; 97 for (int i=vInt.size(); i--;) 98 vInt[i].update(*this, share, s.vInt[i]); 99 for (int i=vBool.size(); i--;) 100 vBool[i].update(*this, share, s.vBool[i]); 101 vCost.update(*this, share, s.vCost); 102 if (s.actp != NULL) actp = new IntActivity(*(s.actp)); 103 104 } 105 106 virtual Gecode::MinimizeSpace* 107 copy(bool share) { 108 return new GecodeSpace(share,*this); 109 } 110 111 virtual Gecode::IntVar cost(void) const { 112 return vCost; 113 } 114 115 ~GecodeSpace(void) { 116 delete d_args; 117 delete actp; 118 } 119 120private: 121 bool valid_snapshot; 122 bool first; // true if not recomputing 123 double* d_args; // args for passing information for activity calls 124 Gecode::IntActivity* actp; // for using IntActivity outside search engines 125 // change to using vector to lift limit of 1 IntActivity per space 126}; 127 128enum SearchMethod {METHOD_COMPLETE, 129 METHOD_RESTART, 130 METHOD_CONTINUE_BAB, 131 METHOD_RESTART_BAB, 132 METHOD_RESTART_RBAB}; 133 134// taken from gecode/driver/script.hpp, by Christian Schulte 135class Cutoff : public Gecode::Search::Stop { 136private: 137 Search::NodeStop* ns; ///< Used node stop object 138 Search::FailStop* fs; ///< Used fail stop object 139 Search::TimeStop* ts; ///< Used time stop object 140 // Search::MemoryStop* ms; ///< Used memory stop object 141 long stop_reason; 142public: 143 /// Initialize stop object 144 Cutoff(unsigned int node, unsigned int fail, unsigned int time/*, size_t mem*/) 145 : ns((node > 0) ? new Search::NodeStop(node) : NULL), 146 fs((fail > 0) ? new Search::FailStop(fail) : NULL), 147 ts((time > 0) ? new Search::TimeStop(time) : NULL), 148 // ms((mem > 0) ? new Search::MemoryStop(mem) : NULL), 149 stop_reason(0) {} 150 /// Reason why search has been stopped 151 enum { 152 SR_NODE = 1 << 2, ///< Node limit reached 153 SR_FAIL = 1 << 3, ///< Fail limit reached 154 SR_TIME = 1 << 4 ///< Time limit reached 155 //SR_MEM = 1 << 5 ///< Memory limit reached 156 }; 157 /// Test whether search must be stopped 158 virtual bool stop(const Search::Statistics& s, const Search::Options& o) { 159 bool stopping; 160 stopping = 161 ((ns != NULL) && ns->stop(s,o)) || 162 ((fs != NULL) && fs->stop(s,o)) || 163 // ((ms != NULL) && ms->stop(s,o)) || 164 ((ts != NULL) && ts->stop(s,o)); 165 if (stopping) { 166 this->stop_reason = 167 (((ns != NULL) && ns->stop(s,o)) ? SR_NODE : 0) | 168 (((fs != NULL) && fs->stop(s,o)) ? SR_FAIL : 0) | 169 //(((ms != NULL) && ms->stop(s,o)) ? SR_MEM : 0) | 170 (((ts != NULL) && ts->stop(s,o)) ? SR_TIME : 0); 171 } 172 return stopping; 173 } 174 /// Report reason why search has been stopped 175 long reason(void) { 176 return this->stop_reason; 177 } 178 /// Reset (currently only for timer) 179 void reset(void) { 180 if (ts != NULL) ts->reset(); 181 } 182 /// Destructor 183 ~Cutoff(void) { 184 delete ns; delete fs; delete ts; //delete ms; 185 } 186}; 187 188/* based on code from Christian Schulte posted on Gecode mailing list, 189 2013-08-27 190*/ 191class GecodeEngineBase { 192public: 193 GecodeEngineBase(void) {} 194 virtual GecodeSpace* next(void) = 0; 195 virtual Search::Statistics statistics(void) const = 0; 196 virtual bool stopped(void) const = 0; 197 virtual ~GecodeEngineBase(void) {} 198}; 199 200class GecodeDFS : public GecodeEngineBase { 201protected: 202 DFS<GecodeSpace> e; 203 204public: 205 GecodeDFS(GecodeSpace* solver, const Search::Options& o) : e(solver,o) {} 206 virtual GecodeSpace* next(void) { 207 return e.next(); 208 } 209 virtual Search::Statistics statistics(void) const { 210 return e.statistics(); 211 } 212 virtual bool stopped(void) const { 213 return e.stopped(); 214 } 215 virtual ~GecodeDFS(void) {} 216}; 217 218class GecodeBAB : public GecodeEngineBase { 219protected: 220 BAB<GecodeSpace> e; 221 222public: 223 GecodeBAB(GecodeSpace* solver, const Search::Options& o) : e(solver,o) {} 224 virtual GecodeSpace* next(void) { 225 return e.next(); 226 } 227 virtual Search::Statistics statistics(void) const { 228 return e.statistics(); 229 } 230 virtual bool stopped(void) const { 231 return e.stopped(); 232 } 233 virtual ~GecodeBAB(void) {} 234}; 235 236template<template<class> class E> 237class GecodeRBS : public GecodeEngineBase { 238protected: 239 RBS<E,GecodeSpace> e; 240 241public: 242 GecodeRBS(GecodeSpace* solver, const Search::Options& o) : e(solver,o) {} 243 virtual GecodeSpace* next(void) { 244 return e.next(); 245 } 246 virtual Search::Statistics statistics(void) const { 247 return e.statistics(); 248 } 249 virtual bool stopped(void) const { 250 return e.stopped(); 251 } 252 virtual ~GecodeRBS(void) {} 253}; 254 255 256class GecodeSearch { 257private: 258 GecodeEngineBase* sengine; 259public: 260 SearchMethod method; 261 Cutoff* stopp; 262 263 GecodeSearch(GecodeSpace* solver, Search::Options o, unsigned extra, 264 Cutoff* cutoffp, 265 const SearchMethod& m) : stopp(cutoffp), method(m) { 266 switch (m) { 267 case METHOD_COMPLETE: 268 sengine = new GecodeDFS(solver,o); 269 break; 270 case METHOD_CONTINUE_BAB: 271 solver->vCost = solver->vInt[extra]; 272 sengine = new GecodeBAB(solver,o); 273 break; 274 case METHOD_RESTART_BAB: 275 solver->vCost = solver->vInt[extra]; 276 o.cutoff = Search::Cutoff::constant(ULONG_MAX); 277 sengine = new GecodeRBS<BAB>(solver, o); 278 break; 279 case METHOD_RESTART_RBAB: 280 // cutoff and nogoods limit set already for o 281 solver->vCost = solver->vInt[extra]; 282 sengine = new GecodeRBS<BAB>(solver, o); 283 break; 284 case METHOD_RESTART: 285 sengine = new GecodeRBS<DFS>(solver, o); 286 break; 287 /* 288 default: 289 printf("Error\n"); 290 break;*/ 291 } 292 } 293 294 GecodeSpace* next(void) { 295 // return static_cast<Gecodeace*>(sengine->next()); 296 return sengine->next(); 297 } 298 299 Search::Statistics statistics(void) const { 300 return sengine->statistics(); 301 } 302 303 bool stopped(void) const { 304 return sengine->stopped(); 305 } 306 307 ~GecodeSearch(void) { 308 delete sengine; 309 delete stopp; 310 } 311}; 312 313class LDSBSymsStore { 314public: 315 316 std::queue<SymmetryHandle>* symsp; // symmetries 317 std::queue<IntVar*>* intsp; // dummy IntVars representing integers 318 319 LDSBSymsStore(void) : symsp(new std::queue<SymmetryHandle>()), 320 intsp(new std::queue<IntVar*>()) {} 321 322 ~LDSBSymsStore(void) { 323 delete symsp; 324 delete intsp; 325 } 326}; 327 328 329class VarSelectH { 330public : 331 int* idxs; 332 bool act_inited; 333 334 VarSelectH(void) : idxs(NULL), act_inited(false) {} 335 336 ~VarSelectH(void) { 337 delete idxs; 338 } 339 340}; 341 342class Ec2gcException {}; 343 344