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};

#[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)
    }
}


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

MinOrMax

Trait defining whether a problem is a minimization problem or a maximization problem.