branch_and_bound/bnb_aware_containers.rs
1use crate::Subproblem;
2
3/// A container for subproblem objects, which is used
4/// to store unvisited nodes of the subproblem tree.
5///
6/// A container provides an interface to push and pop
7/// items and:
8/// 1. Defines order in which elements will be popped;
9/// 2. May implement additional features, such as early stopping,
10/// deciding not to push/return some elements based on the value
11/// of the incumbent, etc.
12pub trait BnbAwareContainer<S: Subproblem> {
13 /// Add `item` to the container.
14 ///
15 /// `score` is the objective score of the current incumbent (if any).
16 /// The container may decide not to add an item if it's known to be
17 /// worse than the incumbent ("eager" evaluation strategy).
18 fn push_with_incumbent(&mut self, item: S, score: Option<&S::Score>);
19
20 /// Get an item from the container.
21 /// `score` is the objective score of the current incumbent (if any).
22 /// The container may decide to skip items that are known to be
23 /// worse than the incumbent ("lazy" evaluation strategy).
24 ///
25 /// Returns `None` iff the container is exhausted (i.e., there's no more
26 /// feasible subproblems to process).
27 ///
28 /// After `.pop_with_incumbent` returns `None`, the object should not
29 /// be used anymore: calling either `.push_with_incumbent` or
30 /// `.pop_with_incumbent` will have unspecified results.
31 fn pop_with_incumbent(&mut self, score: Option<&S::Score>) -> Option<S>;
32}
33
34/// Wrapper around `binary_heap_plus::BinaryHeap`.
35/// Used for best-first search and custom-order search.
36pub(super) struct BinaryHeapExt<Node, Cmp> {
37 /// The node container
38 pub heap: binary_heap_plus::BinaryHeap<Node, Cmp>,
39 /// If `true`, the heap behaves as if in best-first search:
40 /// if the candidate `.bound()` is less than or equal to
41 /// the incumbent's objective score, no more elements will
42 /// be popped, so the algorithm will terminate early.
43 pub stop_early: bool,
44}
45
46// TODO: it seems like it makes more sense to also create (private)
47// wrapper types for `Vec` and `VecDeque` and implement `BnbAwareContainer`
48// for them rather than the standard containers. I see two reasons for that:
49//
50// 1. This would provide better encapsulation: I see the implementations
51// of standard search orders as a private implementation detail, however,
52// a user can now call `solve_with_container` on a vector and it will
53// work according to an algorithm that we internally implement.
54//
55// 2. This way, it would take less effort for a lazy user to customize
56// an algorithm: they could just implement `BnbAwareContainer` on a
57// standard type like `Vec` and have it work, without having to create
58// a wrapper type (currently, that's not possible because
59// `BnbAwareContainer`) is already implemented for `Vec`.
60
61/// This implementation for `Vec` is an implementation of the extra-eager strategy:
62/// it checks against the incumbent both when pushing and when popping.
63/// I suppose, it's not efficient!
64/// TODO: analyze this on examples and provide more flexible options.
65impl<S: Subproblem> BnbAwareContainer<S> for Vec<S> {
66 fn push_with_incumbent(&mut self, item: S, score: Option<&S::Score>) {
67 if score.is_none() || score.unwrap() < &item.bound() {
68 self.push(item)
69 }
70 }
71
72 fn pop_with_incumbent(&mut self, score: Option<&S::Score>) -> Option<S> {
73 while let Some(item) = self.pop() {
74 if score.is_none() || score.unwrap() < &item.bound() {
75 return Some(item);
76 }
77 }
78 None
79 }
80}
81
82/// This implementation for `VecDeque` is an implementation of the extra-eager
83/// strategy: it checks against the incumbent both when pushing and when
84/// popping.
85/// I suppose, it's not efficient!
86/// TODO: analyze this on examples and provide more flexible options.
87impl<S: Subproblem> BnbAwareContainer<S> for std::collections::VecDeque<S> {
88 fn push_with_incumbent(&mut self, item: S, score: Option<&S::Score>) {
89 if score.is_none() || score.unwrap() < &item.bound() {
90 self.push_front(item)
91 }
92 }
93
94 fn pop_with_incumbent(&mut self, score: Option<&S::Score>) -> Option<S> {
95 while let Some(item) = self.pop_back() {
96 if score.is_none() || score.unwrap() < &item.bound() {
97 return Some(item);
98 }
99 }
100 None
101 }
102}
103
104/// This implementation for `BinaryHeapExt` is an implementation of the extra-eager
105/// strategy: it checks against the incumbent both when pushing and when
106/// popping.
107/// We can't remove the lazy evaluation part here (because then BeFS would
108/// make no sense: we want it to terminate early) but the eager part may
109/// be removed, which might make it more efficient.
110/// TODO: analyze this on examples and provide more flexible options.
111impl<S: Subproblem, Cmp: compare::Compare<S>> BnbAwareContainer<S> for BinaryHeapExt<S, Cmp> {
112 fn push_with_incumbent(&mut self, item: S, score: Option<&<S as Subproblem>::Score>) {
113 if score.is_none() || score.unwrap() < &item.bound() {
114 self.heap.push(item);
115 }
116 }
117
118 fn pop_with_incumbent(&mut self, score: Option<&<S as Subproblem>::Score>) -> Option<S> {
119 // If the first (i.e., best) item is definitely worse than the current best solution,
120 // there's no point in looking any further: the rest of candidates are worse anyway
121 while let Some(item) = self.heap.pop() {
122 if score.is_none() || score.unwrap() < &item.bound() {
123 return Some(item);
124 }
125
126 // If this candidate is not good enough and `self.stop_early`,
127 // assuming no candidate will be good enough.
128 if self.stop_early {
129 break;
130 }
131 }
132
133 None
134 }
135}