Generated on Tue Jan 28 2020 00:00:00 for Gecode by doxygen 1.8.17
cutoff.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Guido Tack <tack@gecode.org>
5  *
6  * Contributing authors:
7  * Christian Schulte <schulte@gecode.org>
8  *
9  * Copyright:
10  * Christian Schulte, 2013
11  * Guido Tack, 2013
12  *
13  * Last modified:
14  * $Date: 2016-04-19 17:19:45 +0200 (Tue, 19 Apr 2016) $ by $Author: schulte $
15  * $Revision: 14967 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #include <algorithm>
43 #include <gecode/search.hh>
44 
45 namespace Gecode { namespace Search {
46 
47  unsigned long int
49  return c;
50  }
51  unsigned long int
53  return c;
54  }
55 
56 
57  unsigned long int
59  return n;
60  }
61  unsigned long int
63  n += scale;
64  return n;
65  }
66 
67 
68  unsigned long int
70  1,1,2,1,1,2,4,1,1,2,1,1,2,4,8,1,1,2,1,1,2,4,1,1,2,1,1,2,4,8,16,
71  1,1,2,1,1,2,4,1,1,2,1,1,2,4,8,1,1,2,1,1,2,4,1,1,2,1,1,2,4,8,16,32
72  };
73  unsigned long int
75  return scale*luby(i);
76  }
77  unsigned long int
79  return scale*luby(i++);
80  }
81 
82 
83  unsigned long int
85  return static_cast<unsigned long int>(scale * n);
86  }
87  unsigned long int
89  n *= base;
90  return static_cast<unsigned long int>(scale * n);
91  }
92 
93 
94  unsigned long int
96  cur = min+step*rnd(n);
97  return cur;
98  }
99  unsigned long int
101  return cur;
102  }
103 
104 
105  unsigned long int
107  if (n > 0) {
108  return (*c1)();
109  } else {
110  return (*c2)();
111  }
112  }
113  unsigned long int
115  if (n > 0) {
116  n--;
117  return ++(*c1);
118  } else {
119  return ++(*c2);
120  }
121  }
122 
123 
124  unsigned long int
126  return (*c1)();
127  }
128  unsigned long int
130  (void) ++(*c1);
131  std::swap(c1,c2);
132  return (*c1)();
133  }
134 
135 
136  unsigned long int
138  return cutoff;
139  }
140  unsigned long int
142  i++;
143  if (i == n) {
144  cutoff = (*c)();
145  i = 0;
146  }
147  return cutoff;
148  }
149 
150 
151  Cutoff*
152  Cutoff::constant(unsigned long int scale) {
153  return new CutoffConstant(scale);
154  }
155  Cutoff*
156  Cutoff::linear(unsigned long int scale) {
157  return new CutoffLinear(scale);
158  }
159  Cutoff*
160  Cutoff::luby(unsigned long int scale) {
161  return new CutoffLuby(scale);
162  }
163  Cutoff*
164  Cutoff::geometric(unsigned long int base, double scale) {
165  return new CutoffGeometric(base,scale);
166  }
167  Cutoff*
168  Cutoff::rnd(unsigned int seed,
169  unsigned long int min,
170  unsigned long int max,
171  unsigned long int n) {
172  return new CutoffRandom(seed,min,max,n);
173  }
174  Cutoff*
175  Cutoff::append(Cutoff* c1, unsigned long int n, Cutoff* c2) {
176  return new CutoffAppend(c1,n,c2);
177  }
178  Cutoff*
180  return new CutoffMerge(c1,c2);
181  }
182  Cutoff*
183  Cutoff::repeat(Cutoff* c, unsigned long int n) {
184  return new CutoffRepeat(c,n);
185  }
186 
187 }}
188 
189 // STATISTICS: search-other
unsigned long int n
Next number in sequence.
Definition: search.hh:247
static unsigned long int luby(unsigned long int i)
Compute Luby number for step i.
Definition: cutoff.hpp:72
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:48
Cutoff generator for linear sequence.
Definition: search.hh:242
unsigned long int i
Iteration number.
Definition: search.hh:264
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:125
static unsigned long int start[n_start]
Precomputed luby-values.
Definition: search.hh:270
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:53
static Cutoff * constant(unsigned long int scale=Config::slice)
Create generator for constant sequence with constant s.
Definition: cutoff.cpp:152
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:74
double scale
Scale factor.
Definition: search.hh:293
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:78
static const unsigned long int n_start
Number of pre-computed luby values.
Definition: search.hh:268
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:84
static Cutoff * append(Cutoff *c1, unsigned long int n, Cutoff *c2)
Append cutoff values from c2 after n values from c1.
Definition: cutoff.cpp:175
Cutoff generator that repeats a cutoff from another cutoff generator.
Definition: search.hh:380
unsigned int cutoff
Definition: search.hh:385
unsigned long int n
Definition: search.hh:389
static Cutoff * geometric(unsigned long int scale=Config::slice, double base=Config::base)
Definition: cutoff.cpp:164
Gecode toplevel namespace
Cutoff * c2
Second cutoff generator.
Definition: search.hh:364
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:114
double base
Base.
Definition: search.hh:295
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:137
unsigned long int step
Step size.
Definition: search.hh:318
unsigned long int n
How many number to take from the first.
Definition: search.hh:343
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:129
Cutoff * c1
First cutoff generator.
Definition: search.hh:362
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Definition: irt.hpp:41
unsigned long int n
Random values.
Definition: search.hh:316
double n
Current cutoff value.
Definition: search.hh:291
unsigned long int scale
Scale factor.
Definition: search.hh:266
unsigned long int c
Constant.
Definition: search.hh:228
const double base
Base for geometric restart sequence.
Definition: search.hh:122
unsigned long int cur
Current value.
Definition: search.hh:320
static Cutoff * repeat(Cutoff *c, unsigned long int n)
Create generator that repeats n times each cutoff value from c.
Definition: cutoff.cpp:183
Cutoff generator appending two cutoff generators.
Definition: search.hh:336
Cutoff * c1
First cutoff generators.
Definition: search.hh:339
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:52
static Cutoff * merge(Cutoff *c1, Cutoff *c2)
Merge cutoff values from c1 with values from c2.
Definition: cutoff.cpp:179
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:95
Cutoff generator for the Luby sequence.
Definition: search.hh:261
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:62
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:106
Base class for cutoff generators for restart-based meta engine.
Definition: search.hh:172
Support::RandomGenerator rnd
Random number generator.
Definition: search.hh:312
Cutoff generator merging two cutoff generators.
Definition: search.hh:359
static Cutoff * linear(unsigned long int scale=Config::slice)
Create generator for linear sequence scaled by scale.
Definition: cutoff.cpp:156
Cutoff generator for the geometric sequence.
Definition: search.hh:288
static Cutoff * rnd(unsigned int seed, unsigned long int min, unsigned long int max, unsigned long int n)
Definition: cutoff.cpp:168
Cutoff generator for constant sequence.
Definition: search.hh:225
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:100
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:58
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
Gecode::FloatVal c(-8, 8)
unsigned long int i
Definition: search.hh:387
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Cutoff * c2
Second cutoff generators.
Definition: search.hh:341
unsigned long int scale
Scale factor.
Definition: search.hh:245
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:88
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:141
static Cutoff * luby(unsigned long int scale=Config::slice)
Create generator for luby sequence with scale-factor scale.
Definition: cutoff.cpp:160
Cutoff generator for the random sequence.
Definition: search.hh:309
unsigned long int min
Minimum cutoff value.
Definition: search.hh:314