Generated on for Gecode by doxygen 1.18.0
heuristic.hh
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
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#ifndef GECODE_SEARCH_HEURISTIC_HH
35#define GECODE_SEARCH_HEURISTIC_HH
36
37#include <gecode/search.hh>
38#include <algorithm>
39#include <climits>
40#include <memory>
41#include <optional>
42
43#ifdef GECODE_HAS_EXPERIMENTAL
44namespace Gecode { namespace Search {
45
47 forceinline bool
48 better(HeuristicGuidance::Sense s, std::int64_t a, std::int64_t b) {
49 return (s == HeuristicGuidance::MINIMIZE) ? (a < b) : (a > b);
50 }
51
53 class Entry {
54 public:
58 std::int64_t bound, rank;
60 std::size_t key;
62 unsigned long int depth;
64 unsigned long long int order;
66 unsigned long long int revision;
67 };
68
70 class Priority {
71 public:
77 bool operator ()(const Entry& a, const Entry& b) const {
78 if (!rank_only && (a.bound != b.bound))
79 return better(sense,a.bound,b.bound);
80 if (a.rank != b.rank)
81 return a.rank < b.rank;
82 return a.order < b.order;
83 }
84 };
85
87 class Incumbent {
88 public:
92 std::unique_ptr<Space> space;
94 std::int64_t bound;
96 unsigned long long int revision;
100
101 bool improves(std::int64_t b) const {
102 return !space || better(sense,b,bound);
103 }
104
105 void update(Space* s, std::int64_t b) {
106 space.reset(s); bound = b; revision++;
107 }
108
109 void reset(void) {
110 space.reset(); revision = 0;
111 }
112 };
113
115 class Entries : public Support::DynamicStack<Entry,Heap> {
116 public:
120 void clear(void) {
121 while (!empty())
122 delete pop().space;
123 }
124
125 ~Entries(void) { clear(); }
127 void sort(const Priority& p) {
128 if (entries() > 1)
129 std::sort(&(*this)[0],&(*this)[0]+entries(),
130 [&](const Entry& a, const Entry& b) { return p(b,a); });
131 }
132 };
133
135 class Queue {
136 protected:
141 public:
143 Queue(const Priority& p0) : p(p0) {}
145 bool empty(void) const { return entries.empty(); }
147 void push(const Entry& e) {
148 entries.push(e);
149 Entry* f = &entries[0];
150 std::push_heap(f,f+entries.entries(),
151 [this](const Entry& a, const Entry& b) { return p(b,a); });
152 }
153
154 Entry pop(void) {
155 Entry* f = &entries[0];
156 std::pop_heap(f,f+entries.entries(),
157 [this](const Entry& a, const Entry& b) { return p(b,a); });
158 return entries.pop();
159 }
160
161 void clear(void) { entries.clear(); }
162 };
163
172 class Beam {
173 public:
175 enum Offer {
178 };
179 private:
181 class Slot {
182 public:
184 Entry e;
186 int pos;
188 int next, prev;
189 };
193 int n_slot, free;
197 int n;
201 int n_bucket;
203 Priority p;
205 unsigned long int _width;
207 std::optional<std::int64_t> discarded;
208
210 int index(std::size_t k) const {
211 return static_cast<int>((k ^ (k >> 16)) & (n_bucket-1));
212 }
214 void link(int s) {
215 int b = index(slot[s].e.key);
216 slot[s].prev = -1; slot[s].next = bucket[b];
217 if (bucket[b] >= 0)
218 slot[bucket[b]].prev = s;
219 bucket[b] = s;
220 }
222 void unlink(int s) {
223 Slot& x = slot[s];
224 if (x.prev >= 0)
225 slot[x.prev].next = x.next;
226 else
227 bucket[index(x.e.key)] = x.next;
228 if (x.next >= 0)
229 slot[x.next].prev = x.prev;
230 }
232 bool above(int a, int b) const {
233 return p(slot[b].e,slot[a].e);
234 }
236 void place(int i, int s) {
237 pq[i] = s; slot[s].pos = i;
238 }
240 void repair(int i) {
241 int s = pq[i];
242 while ((i > 0) && above(s,pq[(i-1)/2])) {
243 place(i,pq[(i-1)/2]); i = (i-1)/2;
244 }
245 while (2*i+1 < n) {
246 int c = 2*i+1;
247 if ((c+1 < n) && above(pq[c+1],pq[c]))
248 c++;
249 if (!above(pq[c],s))
250 break;
251 place(i,pq[c]); i = c;
252 }
253 place(i,s);
254 }
256 void add(const Entry& e) {
257 int s;
258 if (free >= 0) {
259 s = free; free = slot[s].next;
260 } else {
261 s = n_slot++;
262 }
263 slot[s].e = e;
264 if (n_bucket > 0) {
265 if (n >= n_bucket) {
266 n_bucket *= 2;
267 for (int b=0; b<n_bucket; b++)
268 bucket[b] = -1;
269 for (int i=0; i<n; i++)
270 link(pq[i]);
271 }
272 link(s);
273 }
274 place(n++,s);
275 repair(n-1);
276 }
278 void remove(int s) {
279 int i = slot[s].pos;
280 delete slot[s].e.space;
281 if (n_bucket > 0)
282 unlink(s);
283 slot[s].pos = -1; slot[s].next = free; free = s;
284 if (i < --n) {
285 place(i,pq[n]); repair(i);
286 }
287 }
289 bool comparable(const Entry& e, int s) const {
290 return (slot[s].pos >= 0) && ((n_bucket == 0) || (slot[s].e.key == e.key));
291 }
293 int chain_first(const Entry& e) const {
294 return (n_bucket > 0) ? bucket[index(e.key)] : 0;
295 }
297 int chain_next(int s) const {
298 if (n_bucket > 0)
299 return slot[s].next;
300 return (s+1 < n_slot) ? s+1 : -1;
301 }
302 public:
304 Beam(const Priority& p0, bool keyed)
305 : slot(heap), n_slot(0), free(-1), pq(heap), n(0), bucket(heap),
306 n_bucket(keyed ? 16 : 0), p(p0), _width(1) {
307 for (int b=0; b<n_bucket; b++)
308 bucket[b] = -1;
309 }
310
311 ~Beam(void) { clear(); }
313 int size(void) const { return n; }
315 bool empty(void) const { return n == 0; }
317 bool improving(const Incumbent& i) const {
318 return discarded && i.improves(*discarded);
319 }
320
321 bool widen(unsigned long int m) {
322 if ((_width > ULONG_MAX/2) || ((m > 0UL) && (2*_width > m)))
323 return false;
324 _width *= 2; discarded.reset();
325 return true;
326 }
327
335 Offer offer(const Entry& e, const HeuristicGuidance& g, bool room) {
336 if (g.dominates && (n > 0)) {
337 for (int s=chain_first(e); s>=0; s=chain_next(s))
338 if (comparable(e,s) && g.dominates(*slot[s].e.space,*e.space)) {
339 delete e.space;
340 return TAKEN;
341 }
342 bool victim = false;
343 for (int s=chain_first(e); s>=0; ) {
344 int t = chain_next(s);
345 if (comparable(e,s) && g.dominates(*e.space,*slot[s].e.space)) {
346 remove(s); victim = true;
347 }
348 s = t;
349 }
350 if (victim) {
351 add(e);
352 return TAKEN;
353 }
354 }
355 if (static_cast<unsigned long int>(n) == _width) {
356 const Entry& worst = slot[pq[0]].e;
357 bool replace = p(e,worst);
358 std::int64_t b = replace ? worst.bound : e.bound;
359 if (!discarded || better(p.sense,b,*discarded))
360 discarded = b;
361 if (replace) {
362 remove(pq[0]); add(e);
363 } else {
364 delete e.space;
365 }
366 return TAKEN;
367 }
368 if (!room)
369 return FULL;
370 add(e);
371 return TAKEN;
372 }
373
374 void release(Entries& l) {
375 for (int i=0; i<n; i++)
376 l.push(slot[pq[i]].e);
377 n = 0; n_slot = 0; free = -1;
378 for (int b=0; b<n_bucket; b++)
379 bucket[b] = -1;
380 }
381
382 void clear(void) {
383 for (int i=0; i<n; i++)
384 delete slot[pq[i]].e.space;
385 n = 0; n_slot = 0; free = -1;
386 for (int b=0; b<n_bucket; b++)
387 bucket[b] = -1;
388 _width = 1; discarded.reset();
389 }
390 };
391
392}}
393#endif
394
395#endif
396
397// STATISTICS: search-other
Heap memory management class
Definition heap.hpp:66
Beam(const Priority &p0, bool keyed)
Initialize with priority p, using keys for dominance if keyed.
Definition heuristic.hh:304
Offer offer(const Entry &e, const HeuristicGuidance &g, bool room)
Offer entry e.
Definition heuristic.hh:335
void clear(void)
Delete all entries and reset width.
Definition heuristic.hh:382
void release(Entries &l)
Move all entries to l.
Definition heuristic.hh:374
bool improving(const Incumbent &i) const
Whether discarded entries could improve an incumbent i.
Definition heuristic.hh:317
bool empty(void) const
Whether there are no entries.
Definition heuristic.hh:315
Offer
Result of offering an entry.
Definition heuristic.hh:175
@ TAKEN
The entry has been added or deleted.
Definition heuristic.hh:176
@ FULL
The entry needs a new slot but there is no room.
Definition heuristic.hh:177
bool widen(unsigned long int m)
Double the width up to m (zero for no limit), false if not possible.
Definition heuristic.hh:321
~Beam(void)
Delete all entries.
Definition heuristic.hh:311
int size(void) const
Return the number of entries.
Definition heuristic.hh:313
Stack of entries owning their spaces.
Definition heuristic.hh:115
void sort(const Priority &p)
Sort such that the preferred entry is on top.
Definition heuristic.hh:127
Entries(void)
Initialize.
Definition heuristic.hh:118
~Entries(void)
Release memory.
Definition heuristic.hh:125
void clear(void)
Delete all entries.
Definition heuristic.hh:120
Open node of a heuristic search engine.
Definition heuristic.hh:53
Space * space
The stable space (owned by the container holding the entry).
Definition heuristic.hh:56
std::size_t key
Dominance key of the space.
Definition heuristic.hh:60
std::int64_t rank
Definition heuristic.hh:58
unsigned long long int revision
Incumbent revision the space has been constrained with.
Definition heuristic.hh:66
unsigned long long int order
Creation order, for breaking ties.
Definition heuristic.hh:64
unsigned long int depth
Depth of the node.
Definition heuristic.hh:62
std::int64_t bound
Bound and rank of the space.
Definition heuristic.hh:58
Guidance for heuristic search engines (experimental).
Definition search.hh:1259
Sense
Objective direction.
Definition search.hh:1262
std::function< bool(const Space &, const Space &)> dominates
Whether the first space dominates the second (optional).
Definition search.hh:1272
Best solution found so far.
Definition heuristic.hh:87
void reset(void)
Remove incumbent.
Definition heuristic.hh:109
std::int64_t bound
Its objective value.
Definition heuristic.hh:94
std::unique_ptr< Space > space
The solution (if any).
Definition heuristic.hh:92
bool improves(std::int64_t b) const
Whether a node with bound b can improve the incumbent.
Definition heuristic.hh:101
unsigned long long int revision
Incremented for every new incumbent.
Definition heuristic.hh:96
void update(Space *s, std::int64_t b)
Make s with objective value b the incumbent.
Definition heuristic.hh:105
HeuristicGuidance::Sense sense
Objective direction.
Definition heuristic.hh:90
Incumbent(HeuristicGuidance::Sense s)
Initialize without incumbent.
Definition heuristic.hh:98
Order of open nodes: whether a is preferred to b.
Definition heuristic.hh:70
HeuristicGuidance::Sense sense
Objective direction.
Definition heuristic.hh:73
bool operator()(const Entry &a, const Entry &b) const
Test whether a is preferred to b.
Definition heuristic.hh:77
bool rank_only
Whether to order by rank only (CABS with rank).
Definition heuristic.hh:75
Queue(const Priority &p0)
Initialize with priority p.
Definition heuristic.hh:143
bool empty(void) const
Whether the queue is empty.
Definition heuristic.hh:145
void push(const Entry &e)
Add entry e.
Definition heuristic.hh:147
void clear(void)
Delete all entries.
Definition heuristic.hh:161
Entries entries
The entries as a binary heap with the preferred entry first.
Definition heuristic.hh:138
Priority p
The priority.
Definition heuristic.hh:140
Entry pop(void)
Remove and return the preferred entry.
Definition heuristic.hh:154
Computation spaces.
Definition core.hpp:1787
Array with arbitrary number of elements.
Stack with arbitrary number of elements.
void push(const T &x)
Push element x on top of stack.
Heap heap
The single global heap.
Search engines
bool better(HeuristicGuidance::Sense s, std::int64_t a, std::int64_t b)
Whether bound a is better than bound b for objective direction s.
Definition heuristic.hh:48
Support algorithms and datastructures
Gecode toplevel namespace