Generated on Wed Jan 1 2020 10:37:59 for Gecode by doxygen 1.8.16
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  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <algorithm>
39 #include <gecode/search.hh>
40 
41 namespace Gecode { namespace Search {
42 
43  unsigned long int
45  return c;
46  }
47  unsigned long int
49  return c;
50  }
51 
52 
53  unsigned long int
55  return n;
56  }
57  unsigned long int
59  n += scale;
60  return n;
61  }
62 
63 
64  unsigned long int
66  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,
67  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
68  };
69  unsigned long int
71  return scale*luby(i);
72  }
73  unsigned long int
75  return scale*luby(i++);
76  }
77 
78 
79  unsigned long int
81  return static_cast<unsigned long int>(scale * n);
82  }
83  unsigned long int
85  n *= base;
86  return static_cast<unsigned long int>(scale * n);
87  }
88 
89 
90  unsigned long int
92  cur = min+step*rnd(n);
93  return cur;
94  }
95  unsigned long int
97  return cur;
98  }
99 
100 
101  unsigned long int
103  if (n > 0) {
104  return (*c1)();
105  } else {
106  return (*c2)();
107  }
108  }
109  unsigned long int
111  if (n > 0) {
112  n--;
113  return ++(*c1);
114  } else {
115  return ++(*c2);
116  }
117  }
118 
119 
120  unsigned long int
122  return (*c1)();
123  }
124  unsigned long int
126  (void) ++(*c1);
127  std::swap(c1,c2);
128  return (*c1)();
129  }
130 
131 
132  unsigned long int
134  return cutoff;
135  }
136  unsigned long int
138  i++;
139  if (i == n) {
140  cutoff = (*c)();
141  i = 0;
142  }
143  return cutoff;
144  }
145 
146 
147  Cutoff*
148  Cutoff::constant(unsigned long int scale) {
149  return new CutoffConstant(scale);
150  }
151  Cutoff*
152  Cutoff::linear(unsigned long int scale) {
153  return new CutoffLinear(scale);
154  }
155  Cutoff*
156  Cutoff::luby(unsigned long int scale) {
157  return new CutoffLuby(scale);
158  }
159  Cutoff*
160  Cutoff::geometric(unsigned long int base, double scale) {
161  return new CutoffGeometric(base,scale);
162  }
163  Cutoff*
164  Cutoff::rnd(unsigned int seed,
165  unsigned long int min,
166  unsigned long int max,
167  unsigned long int n) {
168  return new CutoffRandom(seed,min,max,n);
169  }
170  Cutoff*
171  Cutoff::append(Cutoff* c1, unsigned long int n, Cutoff* c2) {
172  return new CutoffAppend(c1,n,c2);
173  }
174  Cutoff*
176  return new CutoffMerge(c1,c2);
177  }
178  Cutoff*
179  Cutoff::repeat(Cutoff* c, unsigned long int n) {
180  return new CutoffRepeat(c,n);
181  }
182 
183 }}
184 
185 // STATISTICS: search-other
unsigned long int n
Next number in sequence.
Definition: search.hh:547
static unsigned long int luby(unsigned long int i)
Compute Luby number for step i.
Definition: cutoff.hpp:68
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:44
Cutoff generator for linear sequence.
Definition: search.hh:542
unsigned long int i
Iteration number.
Definition: search.hh:564
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:121
static unsigned long int start[n_start]
Precomputed luby-values.
Definition: search.hh:570
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
static Cutoff * constant(unsigned long int scale=Config::slice)
Create generator for constant sequence with constant s.
Definition: cutoff.cpp:148
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:70
double scale
Scale factor.
Definition: search.hh:593
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:74
static const unsigned long int n_start
Number of pre-computed luby values.
Definition: search.hh:568
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:80
static Cutoff * append(Cutoff *c1, unsigned long int n, Cutoff *c2)
Append cutoff values from c2 after n values from c1.
Definition: cutoff.cpp:171
Cutoff generator that repeats a cutoff from another cutoff generator.
Definition: search.hh:680
unsigned int cutoff
Definition: search.hh:685
unsigned long int n
Definition: search.hh:689
static Cutoff * geometric(unsigned long int scale=Config::slice, double base=Config::base)
Definition: cutoff.cpp:160
Gecode toplevel namespace
Cutoff * c2
Second cutoff generator.
Definition: search.hh:664
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:110
double base
Base.
Definition: search.hh:595
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:133
unsigned long int step
Step size.
Definition: search.hh:618
unsigned long int n
How many number to take from the first.
Definition: search.hh:643
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:125
Cutoff * c1
First cutoff generator.
Definition: search.hh:662
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Definition: irt.hpp:37
unsigned long int n
Random values.
Definition: search.hh:616
double n
Current cutoff value.
Definition: search.hh:591
unsigned long int scale
Scale factor.
Definition: search.hh:566
unsigned long int c
Constant.
Definition: search.hh:528
const double base
Base for geometric restart sequence.
Definition: search.hh:126
unsigned long int cur
Current value.
Definition: search.hh:620
static Cutoff * repeat(Cutoff *c, unsigned long int n)
Create generator that repeats n times each cutoff value from c.
Definition: cutoff.cpp:179
Cutoff generator appending two cutoff generators.
Definition: search.hh:636
Cutoff * c1
First cutoff generators.
Definition: search.hh:639
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:48
static Cutoff * merge(Cutoff *c1, Cutoff *c2)
Merge cutoff values from c1 with values from c2.
Definition: cutoff.cpp:175
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:91
Cutoff generator for the Luby sequence.
Definition: search.hh:561
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:58
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:102
Base class for cutoff generators for restart-based meta engine.
Definition: search.hh:472
Support::RandomGenerator rnd
Random number generator.
Definition: search.hh:612
Cutoff generator merging two cutoff generators.
Definition: search.hh:659
static Cutoff * linear(unsigned long int scale=Config::slice)
Create generator for linear sequence scaled by scale.
Definition: cutoff.cpp:152
Cutoff generator for the geometric sequence.
Definition: search.hh:588
static Cutoff * rnd(unsigned int seed, unsigned long int min, unsigned long int max, unsigned long int n)
Definition: cutoff.cpp:164
Cutoff generator for constant sequence.
Definition: search.hh:525
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:96
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:54
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
Gecode::FloatVal c(-8, 8)
unsigned long int i
Definition: search.hh:687
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Cutoff * c2
Second cutoff generators.
Definition: search.hh:641
unsigned long int scale
Scale factor.
Definition: search.hh:545
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:84
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:137
static Cutoff * luby(unsigned long int scale=Config::slice)
Create generator for luby sequence with scale-factor scale.
Definition: cutoff.cpp:156
Cutoff generator for the random sequence.
Definition: search.hh:609
unsigned long int min
Minimum cutoff value.
Definition: search.hh:614