main page
modules
namespaces
classes
files
Gecode home
Generated on Mon Jul 27 2020 00:00:00 for Gecode by
doxygen
1.8.18
gecode
search
seq
pbs.hpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Christian Schulte <schulte@gecode.org>
5
*
6
* Copyright:
7
* Christian Schulte, 2015
8
*
9
* This file is part of Gecode, the generic constraint
10
* development environment:
11
* http://www.gecode.org
12
*
13
* Permission is hereby granted, free of charge, to any person obtaining
14
* a copy of this software and associated documentation files (the
15
* "Software"), to deal in the Software without restriction, including
16
* without limitation the rights to use, copy, modify, merge, publish,
17
* distribute, sublicense, and/or sell copies of the Software, and to
18
* permit persons to whom the Software is furnished to do so, subject to
19
* the following conditions:
20
*
21
* The above copyright notice and this permission notice shall be
22
* included in all copies or substantial portions of the Software.
23
*
24
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31
*
32
*/
33
34
#include <climits>
35
36
namespace
Gecode
{
namespace
Search {
namespace
Seq {
37
38
39
forceinline
40
PortfolioStop::PortfolioStop
(
Stop
* so0)
41
: so(so0) {}
42
forceinline
void
43
PortfolioStop::share
(
SharedStopInfo
* ssi0) {
44
ssi = ssi0;
45
}
46
47
48
forceinline
void
49
Slave::init
(
Engine
* e,
Stop
* s) {
50
slave
= e;
stop
= s;
51
}
52
forceinline
Space
*
53
Slave::next
(
void
) {
54
return
slave
->
next
();
55
}
56
forceinline
Statistics
57
Slave::statistics
(
void
)
const
{
58
return
slave
->
statistics
();
59
}
60
forceinline
bool
61
Slave::stopped
(
void
)
const
{
62
return
slave
->
stopped
();
63
}
64
forceinline
void
65
Slave::constrain
(
const
Space
&
b
) {
66
slave
->
constrain
(
b
);
67
}
68
forceinline
69
Slave::~Slave
(
void
) {
70
delete
slave
;
71
delete
stop
;
72
}
73
74
75
template
<
bool
best>
76
forceinline
77
PBS<best>::PBS
(
Engine
** e,
Stop
** s,
unsigned
int
n
,
78
const
Statistics
& stat0,
79
const
Search::Options
&
opt
)
80
: stat(stat0),
slice
(
opt
.
slice
),
81
slaves(
heap
.alloc<
Slave
>(
n
)), n_slaves(
n
), cur(0),
82
slave_stop(false) {
83
ssi
.
done
=
false
;
84
ssi
.
l
=
opt
.slice;
85
86
for
(
unsigned
int
i
=0U;
i
<
n
;
i
++) {
87
slaves
[
i
].
init
(e[
i
],
static_cast<
PortfolioStop
*
>
(s[
i
]));
88
static_cast<
PortfolioStop
*
>
(s[
i
])->share(&
ssi
);
89
}
90
}
91
92
template
<
bool
best>
93
Space
*
94
PBS<best>::next
(
void
) {
95
slave_stop =
false
;
96
unsigned
int
n_exhausted = 0;
97
while
(n_slaves > 0) {
98
if
(
Space
* s = slaves[cur].next()) {
99
// Constrain other slaves
100
if
(best) {
101
for
(
unsigned
int
i
=0U;
i
<cur;
i
++)
102
slaves[
i
].constrain(*s);
103
for
(
unsigned
int
i
=cur+1;
i
<n_slaves;
i
++)
104
slaves[
i
].constrain(*s);
105
}
106
return
s;
107
}
108
if
(slaves[cur].stopped()) {
109
if
(ssi.done) {
110
cur++; n_exhausted++;
111
}
else
{
112
slave_stop =
true
;
113
return
NULL;
114
}
115
}
else
{
116
// This slave is done, kill it after saving the statistics
117
stat += slaves[cur].statistics();
118
slaves[cur].~Slave();
119
slaves[cur] = slaves[--n_slaves];
120
if
(n_slaves == 1)
121
// Disable stoping by seeting a high limit
122
ssi.l = ULONG_MAX;
123
}
124
if
(n_exhausted == n_slaves) {
125
n_exhausted = 0;
126
// Increment by one slice
127
ssi.l +=
slice
;
128
}
129
if
(cur == n_slaves)
130
cur = 0;
131
}
132
return
NULL;
133
}
134
135
template
<
bool
best>
136
bool
137
PBS<best>::stopped
(
void
)
const
{
138
return
slave_stop;
139
}
140
141
template
<
bool
best>
142
Statistics
143
PBS<best>::statistics
(
void
)
const
{
144
Statistics
s(stat);
145
for
(
unsigned
int
i
=0U;
i
<n_slaves;
i
++)
146
s += slaves[
i
].statistics();
147
return
s;
148
}
149
150
template
<
bool
best>
151
void
152
PBS<best>::constrain
(
const
Space
&
b
) {
153
if
(!best)
154
throw
NoBest
(
"PBS::constrain"
);
155
for
(
unsigned
int
i
=0U;
i
<n_slaves;
i
++)
156
slaves[
i
].constrain(
b
);
157
}
158
159
template
<
bool
best>
160
PBS<best>::~PBS
(
void
) {
161
for
(
unsigned
int
i
=0U;
i
<n_slaves;
i
++)
162
slaves[
i
].~
Slave
();
163
// Note that n_slaves might be different now!
164
heap
.
rfree
(slaves);
165
}
166
167
}}}
168
169
// STATISTICS: search-seq
Gecode::Search::Seq::SharedStopInfo::l
unsigned long int l
The current failure limit, incremented for each slice.
Definition:
pbs.hh:47
Gecode::Search::Engine::next
virtual Space * next(void)=0
Return next solution (NULL, if none exists or search has been stopped)
Gecode::Search::Seq::SharedStopInfo
Shared stop information.
Definition:
pbs.hh:42
Gecode::Search::Options
Search engine options
Definition:
search.hh:746
Gecode::Search::Stop
Base-class for Stop-object.
Definition:
search.hh:799
Gecode::Search::Seq::PBS::slaves
Slave * slaves
Slaves.
Definition:
pbs.hh:101
Gecode::Search::Seq::Slave::constrain
void constrain(const Space &b)
Constrain with better solution b.
Definition:
pbs.hpp:65
Gecode::Search::Seq::PBS::~PBS
virtual ~PBS(void)
Destructor.
Definition:
pbs.hpp:160
Gecode::Space
Computation spaces.
Definition:
core.hpp:1742
Gecode::Search::Seq::Slave::stopped
bool stopped(void) const
Check whether slave has been stopped.
Definition:
pbs.hpp:61
Gecode::Search::NoBest
Exception: Best solution search is not supported
Definition:
exception.hpp:60
Gecode::Search::Seq::Slave::~Slave
~Slave(void)
Delete slave.
Definition:
pbs.hpp:69
Gecode::Search::Seq::Slave::slave
Engine * slave
The slave engine.
Definition:
pbs.hh:70
Gecode
Gecode toplevel namespace
Test::opt
Options opt
The options.
Definition:
test.cpp:97
Gecode::Search::Seq::Slave::init
void init(Engine *s, Stop *so)
Initialize with slave s and its stop object so.
Definition:
pbs.hpp:49
Gecode::Search::Seq::PBS::constrain
virtual void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition:
pbs.hpp:152
Gecode::Search::Engine
Search engine implementation interface
Definition:
search.hh:899
Gecode::Search::Seq::PBS::next
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition:
pbs.hpp:94
b
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Gecode::Search::Seq::Slave::stop
Stop * stop
Stop object.
Definition:
pbs.hh:72
Gecode::Search::Seq::PortfolioStop
Stop object used for controling slaves in a portfolio.
Definition:
pbs.hh:51
Gecode::Search::Engine::statistics
virtual Statistics statistics(void) const =0
Return statistics.
Gecode::Search::Seq::Slave::statistics
Statistics statistics(void) const
Return statistics of slave.
Definition:
pbs.hpp:57
Gecode::Search::Engine::stopped
virtual bool stopped(void) const =0
Check whether engine has been stopped.
Gecode::heap
Heap heap
The single global heap.
Definition:
heap.cpp:44
Gecode::Search::Seq::PortfolioStop::share
void share(SharedStopInfo *ssi)
Intialize shared stop information.
Definition:
pbs.hpp:43
Gecode::Search::Seq::PBS::PBS
PBS(Engine **slaves, Stop **stops, unsigned int n, const Statistics &stat, const Search::Options &opt)
Initialize.
Definition:
pbs.hpp:77
Gecode::Search::Seq::PortfolioStop::PortfolioStop
PortfolioStop(Stop *so)
Initialize.
Definition:
pbs.hpp:40
Gecode::Search::Seq::Slave::next
Space * next(void)
Return next solution.
Definition:
pbs.hpp:53
Gecode::Search::Seq::SharedStopInfo::done
bool done
Whether search stopped because the slice is done.
Definition:
pbs.hh:45
forceinline
#define forceinline
Definition:
config.hpp:185
Gecode::Search::Seq::PBS::stopped
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition:
pbs.hpp:137
Gecode::Search::Config::slice
const unsigned int slice
Size of a slice in a portfolio and scale factor for restarts(in number of failures)
Definition:
search.hh:128
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:234
Gecode::Heap::rfree
void rfree(void *p)
Free memory block starting at p.
Definition:
heap.hpp:371
Gecode::Search::Seq::PBS::ssi
SharedStopInfo ssi
Shared slave information.
Definition:
pbs.hh:97
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::Search::Seq::PBS::statistics
virtual Statistics statistics(void) const
Return statistics.
Definition:
pbs.hpp:143
Gecode::Search::Engine::constrain
virtual void constrain(const Space &b)
Constrain future solutions to be better than b (raises exception)
Definition:
engine.cpp:39
Gecode::Search::Statistics
Search engine statistics
Definition:
search.hh:147
Gecode::Search::Seq::Slave
Runnable slave of a portfolio master.
Definition:
pbs.hh:67