main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Jan 28 2020 00:00:00 for Gecode by
doxygen
1.8.17
gecode
search
meta
sequential
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
* Last modified:
10
* $Date: 2016-04-19 17:19:45 +0200 (Tue, 19 Apr 2016) $ by $Author: schulte $
11
* $Revision: 14967 $
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 <climits>
39
40
namespace
Gecode
{
namespace
Search {
namespace
Meta {
namespace
Sequential {
41
42
43
forceinline
44
PortfolioStop::PortfolioStop
(
Stop
* so0)
45
: so(so0) {}
46
forceinline
void
47
PortfolioStop::share
(
SharedStopInfo
* ssi0) {
48
ssi = ssi0;
49
}
50
51
52
forceinline
void
53
Slave::init
(
Engine
* e,
Stop
* s) {
54
slave
= e;
stop
= s;
55
}
56
forceinline
Space
*
57
Slave::next
(
void
) {
58
return
slave
->
next
();
59
}
60
forceinline
Statistics
61
Slave::statistics
(
void
)
const
{
62
return
slave
->
statistics
();
63
}
64
forceinline
bool
65
Slave::stopped
(
void
)
const
{
66
return
slave
->
stopped
();
67
}
68
forceinline
void
69
Slave::constrain
(
const
Space
&
b
) {
70
slave
->
constrain
(
b
);
71
}
72
forceinline
73
Slave::~Slave
(
void
) {
74
delete
slave
;
75
delete
stop
;
76
}
77
78
79
template
<
bool
best>
80
forceinline
81
PBS<best>::PBS
(
Engine
** e,
Stop
** s,
unsigned
int
n
,
82
const
Statistics
& stat0,
83
const
Search::Options
&
opt
)
84
: stat(stat0),
slice
(
opt
.
slice
),
85
slaves(
heap
.alloc<
Slave
>(
n
)), n_slaves(
n
), cur(0),
86
slave_stop(false) {
87
ssi
.
done
=
false
;
88
ssi
.
l
=
opt
.slice;
89
for
(
unsigned
int
i
=
n
;
i
--; ) {
90
slaves
[
i
].
init
(e[
i
],
static_cast<
PortfolioStop
*
>
(s[
i
]));
91
static_cast<
PortfolioStop
*
>
(s[
i
])->share(&
ssi
);
92
}
93
}
94
95
template
<
bool
best>
96
Space
*
97
PBS<best>::next
(
void
) {
98
slave_stop =
false
;
99
unsigned
int
n_exhausted = 0;
100
while
(n_slaves > 0) {
101
if
(
Space
* s = slaves[cur].next()) {
102
// Constrain other slaves
103
if
(best) {
104
for
(
unsigned
int
i
=0;
i
<cur;
i
++)
105
slaves[
i
].constrain(*s);
106
for
(
unsigned
int
i
=cur+1;
i
<n_slaves;
i
++)
107
slaves[
i
].constrain(*s);
108
}
109
return
s;
110
}
111
if
(slaves[cur].stopped()) {
112
if
(ssi.done) {
113
cur++; n_exhausted++;
114
}
else
{
115
slave_stop =
true
;
116
return
NULL;
117
}
118
}
else
{
119
// This slave is done, kill it after saving the statistics
120
stat += slaves[cur].statistics();
121
slaves[cur].~Slave();
122
slaves[cur] = slaves[--n_slaves];
123
if
(n_slaves == 1)
124
// Disable stoping by seeting a high limit
125
ssi.l = ULONG_MAX;
126
}
127
if
(n_exhausted == n_slaves) {
128
n_exhausted = 0;
129
// Increment by one slice
130
ssi.l +=
slice
;
131
}
132
if
(cur == n_slaves)
133
cur = 0;
134
}
135
return
NULL;
136
}
137
138
template
<
bool
best>
139
bool
140
PBS<best>::stopped
(
void
)
const
{
141
return
slave_stop;
142
}
143
144
template
<
bool
best>
145
Statistics
146
PBS<best>::statistics
(
void
)
const
{
147
Statistics
s(stat);
148
for
(
unsigned
int
i
=n_slaves;
i
--; )
149
s += slaves[
i
].statistics();
150
return
s;
151
}
152
153
template
<
bool
best>
154
void
155
PBS<best>::constrain
(
const
Space
&
b
) {
156
if
(!best)
157
throw
NoBest
(
"PBS::constrain"
);
158
for
(
unsigned
int
i
=0;
i
<n_slaves;
i
++)
159
slaves[
i
].constrain(
b
);
160
}
161
162
template
<
bool
best>
163
PBS<best>::~PBS
(
void
) {
164
for
(
unsigned
int
i
=n_slaves;
i
--; )
165
slaves[
i
].~
Slave
();
166
// Note that n_slaves might be different now!
167
heap
.
rfree
(slaves);
168
}
169
170
}}}}
171
172
// STATISTICS: search-meta
forceinline
#define forceinline
Definition:
config.hpp:173
Gecode::Search::Meta::Sequential::PBS::slaves
Slave * slaves
Slaves.
Definition:
pbs.hh:105
Gecode::Search::Meta::Sequential::PBS::stopped
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition:
pbs.hpp:140
Gecode::Search::Engine::next
virtual Space * next(void)=0
Return next solution (NULL, if none exists or search has been stopped)
Gecode::Search::Meta::Sequential::PBS::constrain
virtual void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition:
pbs.hpp:155
Gecode::Search::Options
Search engine options
Definition:
search.hh:446
Gecode::Search::Stop
Base-class for Stop-object.
Definition:
search.hh:501
Gecode::Search::Meta::Sequential::SharedStopInfo
Shared stop information.
Definition:
pbs.hh:46
Test::Int::Basic::i
Gecode::IntArgs i(4, 1, 2, 3, 4)
Gecode::Search::Meta::Sequential::Slave::stop
Stop * stop
Stop object.
Definition:
pbs.hh:76
Gecode::Space
Computation spaces.
Definition:
core.hpp:1748
Gecode::Search::NoBest
Exception: Best solution search is not supported
Definition:
exception.hpp:64
Gecode
Gecode toplevel namespace
Gecode::Search::Meta::Sequential::Slave::next
Space * next(void)
Return next solution.
Definition:
pbs.hpp:57
Gecode::Search::Meta::Sequential::Slave::slave
Engine * slave
The slave engine.
Definition:
pbs.hh:74
Test::opt
Options opt
The options.
Definition:
test.cpp:101
Gecode::Search::Meta::Sequential::PBS::~PBS
virtual ~PBS(void)
Destructor.
Definition:
pbs.hpp:163
Gecode::Search::Meta::Sequential::Slave::constrain
void constrain(const Space &b)
Constrain with better solution b.
Definition:
pbs.hpp:69
Gecode::Search::Meta::Sequential::PortfolioStop::share
void share(SharedStopInfo *ssi)
Intialize shared stop information.
Definition:
pbs.hpp:47
b
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
Gecode::Search::Engine
Search engine implementation interface
Definition:
search.hh:601
Gecode::Search::Meta::Sequential::Slave::stopped
bool stopped(void) const
Check whether slave has been stopped.
Definition:
pbs.hpp:65
Gecode::Search::Meta::Sequential::Slave::init
void init(Engine *s, Stop *so)
Initialize with slave s and its stop object so.
Definition:
pbs.hpp:53
Gecode::Search::Meta::Sequential::SharedStopInfo::done
bool done
Whether search stopped because the slice is done.
Definition:
pbs.hh:49
Gecode::Search::Engine::statistics
virtual Statistics statistics(void) const =0
Return statistics.
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:48
Gecode::Search::Meta::Sequential::Slave
Runnable slave of a portfolio master.
Definition:
pbs.hh:71
Gecode::Search::Meta::Sequential::PBS::statistics
virtual Statistics statistics(void) const
Return statistics.
Definition:
pbs.hpp:146
Gecode::Search::Meta::Sequential::Slave::~Slave
~Slave(void)
Delete slave.
Definition:
pbs.hpp:73
Gecode::Search::Meta::Sequential::PBS::ssi
SharedStopInfo ssi
Shared slave information.
Definition:
pbs.hh:101
Gecode::Search::Meta::Sequential::PBS::next
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition:
pbs.hpp:97
Gecode::Search::Meta::Sequential::Slave::statistics
Statistics statistics(void) const
Return statistics of slave.
Definition:
pbs.hpp:61
Gecode::Search::Meta::Sequential::PBS::PBS
PBS(Engine **slaves, Stop **stops, unsigned int n, const Statistics &stat, const Search::Options &opt)
Initialize.
Definition:
pbs.hpp:81
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:124
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:238
Gecode::Heap::rfree
void rfree(void *p)
Free memory block starting at p.
Definition:
heap.hpp:375
Gecode::Search::Meta::Sequential::SharedStopInfo::l
unsigned long int l
The current failure limit, incremented for each slice.
Definition:
pbs.hh:51
Gecode::Search::Meta::Sequential::PortfolioStop::PortfolioStop
PortfolioStop(Stop *so)
Initialize.
Definition:
pbs.hpp:44
Gecode::Search::Engine::constrain
virtual void constrain(const Space &b)
Constrain future solutions to be better than b (raises exception)
Definition:
engine.cpp:43
Gecode::Search::Statistics
Search engine statistics
Definition:
search.hh:140
Gecode::Search::Meta::Sequential::PortfolioStop
Stop object used for controling slaves in a portfolio.
Definition:
pbs.hh:55