Crate bnb

Branch & Bound Template

This crate provides a general template for Branch & Bound algorithms.

Example

This is a rather long example. It models the Knapsack-Problem and solves it using the following BranchAndBound algorithm.

A solution is a tuple (or struct) (J,i) where J is a set of indices from 1..i which represent all the already chosen items. We bound a solution by computing its fractional optimal value using the last i+1..n items and the already chosen ones.

Note that we keep an immutable reference to the problem instance in the solution itself to allow to dynamic access to the values. Furthermore that this example is highly unoptimized.

use bnb::{BranchingOperator, BoundingOperator, BranchAndBound, IterativeAlgorithm};

#[derive(Clone, Debug)]
struct KnapsackInstance {
    num_items: usize,
    weights: Vec<f64>,
    values: Vec<f64>,
    weight_limit: f64,
}

#[derive(Clone, Debug)]
struct KnapsackSolution<'a> {
    instance: &'a KnapsackInstance,
    chosen: Vec<bool>,
    index: usize,
    total_weight: f64,
}

impl<'a> KnapsackSolution<'a> {
    pub fn new(ins: &'a KnapsackInstance) -> Self {
        Self {
            instance: ins,
            chosen: vec![],
            index: 0,
            total_weight: 0.0,
        }
    }
}

impl<'a> BranchingOperator for KnapsackSolution<'a> {
    fn branch(&self) -> Vec<Self> {
        if self.index == self.instance.num_items {
            return vec![];
        }

        let mut next_not_chosen: Vec<bool> = self.chosen.clone();
        next_not_chosen.push(false);
        let mut branches = vec![KnapsackSolution {
            instance: &self.instance,
            chosen: next_not_chosen,
            index: self.index + 1,
            total_weight: self.total_weight,
        }];

        if self.total_weight + self.instance.weights[self.index] <= self.instance.weight_limit {
            let mut next_chosen: Vec<bool> = self.chosen.clone();
            next_chosen.push(true);
            branches.push(KnapsackSolution {
                instance: &self.instance,
                chosen: next_chosen,
                index: self.index + 1,
                total_weight: self.total_weight + self.instance.weights[self.index],
            });
        }

        branches
    }
}

impl<'a> BoundingOperator<f64> for KnapsackSolution<'a> {
    fn bound(&self) -> f64 {
        let mut bound: f64 = 0.0;
        for (i, b) in self.chosen.iter().enumerate() {
            if *b {
                bound += self.instance.values[i];
            }
        }

        let mut remaining_weight = self.instance.weight_limit - self.total_weight;
        let mut sorted_indices: Vec<(usize, f64)> = (self.index..self.instance.num_items)
            .into_iter()
            .map(|i| (i, self.instance.values[i] / self.instance.weights[i]))
            .collect();
        sorted_indices.sort_by(|(_, a), (_, b)| a.partial_cmp(b).unwrap());
        loop {
            if let Some((i, _)) = sorted_indices.pop() {
                if remaining_weight - self.instance.weights[i] < 0.0 {
                     let ratio = remaining_weight as f64 / self.instance.weights[i];
                    bound += ratio * self.instance.values[i];
                    break;
                } else {
                    remaining_weight -= self.instance.weights[i];
                    bound += self.instance.values[i];
                }
            } else {
                break;
            }
        }

        bound
    }

    fn solution(&self) -> Option<f64> {
        if self.index < self.instance.num_items {
            return None;
        }

        let mut total_value: f64 = 0.0;
        for (i, b) in self.chosen.iter().enumerate() {
            if *b {
                total_value += self.instance.values[i];
            }
        }
        Some(total_value)
    }
}

fn main() {
    let ins: KnapsackInstance = KnapsackInstance {
        num_items: 8,
        weights: vec![0.1, 0.4, 0.3, 0.7, 0.9, 0.2, 0.5, 0.6],
        values: vec![2.0, 3.1, 2.4, 0.9, 5.1, 0.8, 0.2, 4.0],
        weight_limit: 1.7,
    };

    // Run Branch & Bound using DFS
    let mut bnb = BranchAndBound::new(KnapsackSolution::new(&ins))
                    .maximize()
                    .use_dfs();
     
    // Run the algorithm
    bnb.run_to_completion();

    // The solution should exist
    let sol = bnb.best_known_solution().unwrap();

    // Optimal value achieved us 12.3
    assert_eq!(sol.0, 12.3);

    // Items 1,2,3,6,8 were chosen
    assert_eq!(sol.1.chosen, vec![true, true, true, false, false, true, false, true]);
    assert_eq!(sol.1.index, 8);

    // The total weight of chosen items is 1.6
    assert_eq!(sol.1.total_weight, 1.6);

    // The algorithm took 21 iterations (77 for BestFirstSearch and 125 for BFS in this instance)
    assert_eq!(bnb.num_iterations(), 21);

}

Modules

• seq
  Node Sequencing

Structs

• BBMax
  Placeholder struct to identify maximization problems.
• BBMin
  Placeholder struct to identify minimization problems.
• BranchAndBound
  Branch & Bound

Traits

• BoundingOperator
  Bounds a set of solutions with a theoretical optimal value achievable by these solutions
• BranchingOperator
  Branch a set of solutions into (distinct) subsets of solutions
• IterativeAlgorithm
  Trait defining an iterative algorithm to allow step for step execution of the BranchAndBound algorithm.
• MinOrMax
  Trait defining whether a problem is a minimization problem or a maximization problem.