branch_and_bound/
lib.rs

1pub mod candidate;
2
3use self::candidate::OrderedCandidate;
4use std::collections::binary_heap::BinaryHeap;
5
6/*
7 * There are three similar concepts: Node, Subproblem, and Candidate.
8 *
9 * `Node` is a type defined by user that must implement `Subproblem`.
10 *
11 * `Subproblem` (trait) acts as a search space: a `Subproblem` can
12 * either break down further into subproblems, or indicate a solution
13 * (the value of the objective function). We can also estimate an upper
14 * boundary of the solution in the search space.
15 *
16 * `OrderedCandidate` (trait) wraps a `Node` to add order (a particular order
17 * depends on the implementation of the trait).
18 */
19
20/// Represents the set of subproblems of an intermediate problem
21/// or the value of the objective function of a feasible solution (leaf node).
22pub enum SubproblemResolution<Node: ?Sized, Score> {
23    /// Subproblems of an intermediate problem
24    Branched(Box<dyn Iterator<Item = Node>>),
25    /// The value of the objective function of a feasible solution
26    Solved(Score),
27}
28// TODO: Consider an alternative implementation by making the iterator
29// type a generic variable rather than a `dyn`
30
31/// Represents a problem (subproblem) to be solved with branch-and-bound
32pub trait Subproblem {
33    type Score: Ord;
34
35    /// Evaluates a problem space.
36    ///
37    /// If the space is to be broken further into subproblems, returns
38    /// a sequence of subproblems (may be empty, which discards
39    /// the current subspace).
40    ///
41    /// If the space consists of just one feasible solution to be solved
42    /// directly, returns the score, which is the value of the objective
43    /// function at the solution.
44    fn branch_or_evaluate(&self) -> SubproblemResolution<Self, Self::Score>;
45
46    /// Value of the boundary function at the problem space.
47    fn bound(&self) -> Self::Score;
48}
49
50/// Solves the optimization problem specified by `initial`.
51///
52/// Use this function to walk the subproblem tree in a custom order,
53/// determined by the `OrderedCandidateT` generic type parameter.
54///
55/// If you want one of the default orders, use the `solve` function
56/// instead.
57pub fn ordered_solve<Node, OrderedCandidateT>(initial: Node) -> Option<Node>
58where
59    Node: Subproblem + 'static,
60    OrderedCandidateT: OrderedCandidate<Node = Node>,
61{
62    // Best candidate: its objective score and the node itself
63    let mut best: Option<(OrderedCandidateT::Score, Node)> = None;
64
65    let mut queue = BinaryHeap::new();
66    queue.push(OrderedCandidateT::new(initial));
67
68    while let Some(candidate) = queue.pop() {
69        // TODO: how to implement early break for a polymorphic `Candidate`?
70        /*
71        if let Some((score, _incumbent)) = &best {
72            if &candidate.bound() < score {
73                // When a candidate's _bound_ is worse than the incumbent's
74                // objective score, we don't need to search any further.
75                break;
76                // TODO: we can only break as easily in the BeFS case
77            }
78        }
79        */
80
81        match candidate.branch_or_evaluate() {
82            // Intermediate subproblem
83            SubproblemResolution::Branched(subproblems) => {
84                for node in subproblems {
85                    queue.push(node);
86                }
87            }
88
89            // Leaf node
90            SubproblemResolution::Solved(candidate_score) => {
91                best = match best {
92                    None => Some((candidate_score, candidate.into_node())),
93                    Some((incumbent_score, incumbent)) => {
94                        if incumbent_score < candidate_score {
95                            // Replace the old (boundary) score with the objective score
96                            Some((candidate_score, candidate.into_node()))
97                        } else {
98                            Some((incumbent_score, incumbent))
99                        }
100                    }
101                }
102            }
103        }
104    }
105
106    best.map(|(_, incumbent)| incumbent)
107}
108
109pub enum SearchOrder {
110    BestFirst,
111    // TODO: implement depth-first-search
112    //DepthFirst,
113    BreadthFirst,
114}
115
116/// Solves the optimization problem specified by `initial`.
117///
118/// Walks the subproblem tree in one of the default orders, as determined
119/// by `order`. To walk the tree in a custom order, use the `ordered_solve`
120/// function instead.
121#[inline]
122pub fn solve<Node: Subproblem + 'static>(initial: Node, order: SearchOrder) -> Option<Node> {
123    use candidate::{BoundOrderedCandidate, DepthOrderedCandidate};
124    use SearchOrder::*;
125
126    match order {
127        BestFirst => ordered_solve::<_, BoundOrderedCandidate<_, _>>(initial),
128        BreadthFirst => ordered_solve::<_, DepthOrderedCandidate<_, _>>(initial),
129        /*
130        DepthFirstSearch => ordered_solve::<_, DepthOrderedCandidate<std::cmp::Reverse<Node>, _>>(
131            std::cmp::Reverse(initial),
132        )
133        .map(|rev| rev.0),
134        */
135    }
136}
branch_and_bound/lib.rs

branch_and_bound/
lib.rs
