1 #ifndef BUILD_RBASE_HPPAC
2 #define BUILD_RBASE_HPPAC
3
4 #include "rbase.hpp"
5 #include "problem.hpp"
6 #include "search/search_options.hpp"
7
8 // The purpose of an RBase Generator is that it will backtrack,
9 // so we can explore different options. Once we have finalised
10 // our RBase, we fix it.
11 class BacktrackingRBase
12 {
13 RevertingStack<int> branchcell;
14 RevertingStack<int> branchvalue;
15
16
17 BacktrackingRBase(const BacktrackingRBase&);
18 public:
BacktrackingRBase(MemoryBacktracker * mb)19 BacktrackingRBase(MemoryBacktracker* mb)
20 : branchcell(mb->makeRevertingStack<int>()),
21 branchvalue(mb->makeRevertingStack<int>())
22 {}
23
24
addBranch(int cell,int value)25 void addBranch(int cell, int value)
26 {
27 branchcell.push_back(cell);
28 branchvalue.push_back(value);
29 }
30
size() const31 int size() const
32 { return branchcell.size(); }
33
34
35
fixRBase(PartitionStack * ps,const vec1<TraceList> & trace)36 RBase* fixRBase(PartitionStack* ps, const vec1<TraceList>& trace)
37 {
38 RBase* rb = new RBase();
39 rb->branchcell = branchcell.get();
40 rb->branchvalue = branchvalue.get();
41 rb->initial_permstack = ps->clone();
42 rb->trace = trace;
43 //vec1<int> ordering(ps->domainSize(), -1);
44 //for(int i : range1(ps->domainSize()))
45 // ordering[*(ps->cellStartPtr(i))] = i;
46 rb->value_ordering = ps->fixed_values(); //ordering;
47 rb->inv_value_ordering = invertVecAsPermutation(rb->value_ordering);
48 D_ASSERT(ps->fixed_values().size() == ps->domainSize());
49 return rb;
50 }
51 };
52
choose_branch_cell(PartitionStack * ps,ConstraintStore * cstore,RBaseSearchHeuristic sh)53 int choose_branch_cell(PartitionStack* ps, ConstraintStore* cstore,
54 RBaseSearchHeuristic sh)
55 {
56 int branch_cell = 1;
57 switch(sh)
58 {
59 case RBaseBranch_First:
60 {
61 while(branch_cell <= ps->cellCount() &&
62 ps->cellSize(branch_cell) == 1)
63 branch_cell++;
64 if(branch_cell <= ps->cellCount())
65 return branch_cell;
66 else
67 return -1;
68 }
69 case RBaseBranch_Random:
70 {
71 // This does not choose evenly between all non-unit cells, as we jump to a random point
72 // and search from there.
73 int branch_start = 1 + (random() % ps->cellCount());
74 branch_cell = branch_start;
75 while(branch_cell <= ps->cellCount() &&
76 ps->cellSize(branch_cell) == 1)
77 branch_cell++;
78
79 if(branch_cell <= ps->cellCount())
80 return branch_cell;
81
82 branch_cell = 1;
83 while(branch_cell < branch_start &&
84 ps->cellSize(branch_cell) == 1)
85 branch_cell++;
86
87 if(branch_cell < branch_start)
88 return branch_cell;
89 else
90 return -1;
91 }
92 // Super note: We do 'fall through' on this case into RBaseBranch_Smallest!
93 case RBaseBranch_ConstraintAdvise:
94 {
95 ConstraintStore::get_type container = cstore->get();
96 for(int i : range1(container->size()))
97 {
98 int val = ((*container)[i])->advise_branch();
99 if(val != -1)
100 return val;
101 }
102 } // NOTE: There is no 'break' or 'return' here on purpose
103 case RBaseBranch_Smallest:
104 {
105 int best_cell = -1;
106 int best_size = -1;
107 while(branch_cell <= ps->cellCount())
108 {
109 if(ps->cellSize(branch_cell) != 1)
110 {
111 if(best_size == -1 || ps->cellSize(branch_cell) < best_size)
112 {
113 best_size = ps->cellSize(branch_cell);
114 best_cell = branch_cell;
115 }
116 }
117 branch_cell++;
118 }
119
120 return best_cell;
121 }
122 case RBaseBranch_RandomSmallest:
123 {
124 // First find the smallest value.
125 vec1<int> best_cells;
126 int best_size = -1;
127 while(branch_cell <= ps->cellCount())
128 {
129 if(ps->cellSize(branch_cell) != 1)
130 {
131 if(best_size == -1 || ps->cellSize(branch_cell) < best_size)
132 {
133 best_size = ps->cellSize(branch_cell);
134 best_cells.clear();
135 best_cells.push_back(branch_cell);
136 }
137 else if(ps->cellSize(branch_cell) == best_size)
138 {
139 best_cells.push_back(branch_cell);
140 }
141 }
142 branch_cell++;
143 }
144 if(best_cells.empty())
145 return -1;
146 else
147 return best_cells[(random() % best_cells.size())+1];
148 }
149 case RBaseBranch_Largest:
150 {
151 int best_cell = -1;
152 int best_size = -1;
153 while(branch_cell <= ps->cellCount())
154 {
155 if(ps->cellSize(branch_cell) != 1)
156 {
157 if(ps->cellSize(branch_cell) > best_size)
158 {
159 best_size = ps->cellSize(branch_cell);
160 best_cell = branch_cell;
161 }
162 }
163 branch_cell++;
164 }
165
166 return best_cell;
167 }
168 case RBaseBranch_Smallest2:
169 {
170 int best_cell = -1;
171 int best_size = -1;
172 int second_best_cell = -1;
173 int second_best_size = -1;
174 while(branch_cell <= ps->cellCount())
175 {
176 int size = ps->cellSize(branch_cell);
177 if(size != 1)
178 {
179 if(best_size == -1 || size < best_size)
180 {
181 best_size = size;
182 best_cell = branch_cell;
183 }
184 if(size > best_size && (second_best_size == -1 || second_best_size > size))
185 {
186 second_best_size = size;
187 second_best_cell = branch_cell;
188 }
189 }
190 branch_cell++;
191 }
192
193 if(second_best_cell != -1)
194 return second_best_cell;
195 else
196 return best_cell;
197 }
198
199 default:
200 abort();
201 }
202 }
203
204 template<typename It>
choose_value(It begin,It end,RBaseSearchHeuristic sh)205 It choose_value(It begin, It end, RBaseSearchHeuristic sh)
206 {
207 switch(sh)
208 {
209 case RBaseBranch_First:
210 return begin;
211 case RBaseBranch_Largest:
212 return std::max_element(begin, end);
213 case RBaseBranch_Smallest:
214 return std::min_element(begin, end);
215 case RBaseBranch_Smallest2:
216 throw std::runtime_error("Smallest2 not implemented as rBase value heuristic");
217 case RBaseBranch_Random:
218 return random() % (end - begin) + begin;
219 case RBaseBranch_RandomSmallest:
220 throw std::runtime_error("RandomSmallest is not valid for rBase value heuristic");
221 default:
222 abort();
223 }
224 }
225
buildRBase(Problem * p,RBaseSearchHeuristic cellHeuristic,RBaseSearchHeuristic valueHeuristic)226 RBase* buildRBase(Problem* p, RBaseSearchHeuristic cellHeuristic, RBaseSearchHeuristic valueHeuristic)
227 {
228 int depth = p->full_search_memory_backtracker.getDepth();
229
230 BacktrackingRBase revrbase(&p->full_search_memory_backtracker);
231 D_ASSERT(p->con_store.initCalled());
232 int branch_cell = 1;
233
234 while(branch_cell != -1)
235 {
236 p->con_queue.invokeQueue();
237 p->full_search_memory_backtracker.pushWorld();
238 p->rbase_generation_memory_backtracker.pushWorld();
239 branch_cell = choose_branch_cell(&p->p_stack,
240 &p->con_store, cellHeuristic);
241 if(branch_cell != -1)
242 {
243 // put a well-defined value at the start of the partition, for ease of duplication
244 PartitionStack::cellit min_pos = choose_value(p->p_stack.cellStartPtr(branch_cell), p->p_stack.cellEndPtr(branch_cell), valueHeuristic);
245 // (the +1 at the end is because we 1-index arrays)
246 p->p_stack.swapPositions(p->p_stack.cellStartPos(branch_cell), min_pos - p->p_stack.valStart()+1);
247
248 int cell_start = p->p_stack.cellStartPos(branch_cell);
249 info_out(1, "RBase Level " << revrbase.size()+1 << " : " << p->p_stack.val(cell_start) << ", location " << cell_start << ", in cell " << branch_cell << ", size " << p->p_stack.cellSize(branch_cell));
250 Stats::container().rBase_fixed_points.push_back(std::make_pair(branch_cell, p->p_stack.cellSize(branch_cell)));
251 info_out(1, "RBase Cell starts: " << p->p_stack.cellStarts() << ", lengths: " << p->p_stack.cellSizes());
252 revrbase.addBranch(branch_cell, p->p_stack.val(cell_start));
253 p->p_stack.split(branch_cell, cell_start + 1);
254 }
255 }
256 info_out(1, "Finished RBase building");
257
258 D_ASSERT(p->p_stack.cellCount() == p->p_stack.domainSize());
259
260 RBase* rb = revrbase.fixRBase(&p->p_stack, p->tracer_generator.getTrace());
261 p->con_queue.RBaseFinished(rb);
262 p->full_search_memory_backtracker.popWorldToDepth(depth);
263 return rb;
264 }
265
266
267
268 #endif
269