BranchAndBoundKnapsackSolver.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace Algorithms.Knapsack;

/// <summary>
///     Branch and bound Knapsack solver.
/// </summary>
/// <typeparam name="T">Type of items in knapsack.</typeparam>
public class BranchAndBoundKnapsackSolver<T>
{
    /// <summary>
    ///     Returns the knapsack containing the items that maximize value while not exceeding weight capacity.
    ///     Construct a tree structure with total number of items + 1 levels, each node have two child nodes,
    ///     starting with a dummy item root, each following levels are associated with 1 items, construct the
    ///     tree in breadth first order to identify the optimal item set.
    /// </summary>
    /// <param name="items">All items to choose from.</param>
    /// <param name="capacity">The maximum weight capacity of the knapsack to be filled.</param>
    /// <param name="weightSelector">
    ///     A function that returns the value of the specified item
    ///     from the <paramref name="items">items</paramref> list.
    /// </param>
    /// <param name="valueSelector">
    ///     A function that returns the weight of the specified item
    ///     from the <paramref name="items">items</paramref> list.
    /// </param>
    /// <returns>
    ///     The array of items that provides the maximum value of the
    ///     knapsack without exceeding the specified weight <paramref name="capacity">capacity</paramref>.
    /// </returns>
    public T[] Solve(T[] items, int capacity, Func<T, int> weightSelector, Func<T, double> valueSelector)
    {
        // This is required for greedy approach in upper bound calculation to work.
        items = items.OrderBy(i => valueSelector(i) / weightSelector(i)).ToArray();

        // nodesQueue --> used to construct tree in breadth first order
        Queue<BranchAndBoundNode> nodesQueue = new();

        // maxCumulativeValue --> maximum value while not exceeding weight capacity.
        var maxCumulativeValue = 0.0;

        // starting node, associated with a temporary created dummy item
        BranchAndBoundNode root = new(level: -1, taken: false);

        // lastNodeOfOptimalPat --> last item in the optimal item sets identified by this algorithm
        BranchAndBoundNode lastNodeOfOptimalPath = root;

        nodesQueue.Enqueue(root);

        while (nodesQueue.Count != 0)
        {
            // parent --> parent node which represents the previous item, may or may not be taken into the knapsack
            BranchAndBoundNode parent = nodesQueue.Dequeue();

            // IF it is the last level, branching cannot be performed
            if (parent.Level == items.Length - 1)
            {
                continue;
            }

            // create a child node where the associated item is taken into the knapsack
            var left = new BranchAndBoundNode(parent.Level + 1, true, parent);

            // create a child node where the associated item is not taken into the knapsack
            var right = new BranchAndBoundNode(parent.Level + 1, false, parent);

            // Since the associated item on current level is taken for the first node,
            // set the cumulative weight of first node to cumulative weight of parent node + weight of the associated item,
            // set the cumulative value of first node to cumulative value of parent node + value of current level's item.
            left.CumulativeWeight = parent.CumulativeWeight + weightSelector(items[left.Level]);
            left.CumulativeValue = parent.CumulativeValue + valueSelector(items[left.Level]);
            right.CumulativeWeight = parent.CumulativeWeight;
            right.CumulativeValue = parent.CumulativeValue;

            // IF cumulative weight is smaller than the weight capacity of the knapsack AND
            // current cumulative value is larger then the current maxCumulativeValue, update the maxCumulativeValue
            if (left.CumulativeWeight <= capacity && left.CumulativeValue > maxCumulativeValue)
            {
                maxCumulativeValue = left.CumulativeValue;
                lastNodeOfOptimalPath = left;
            }

            left.UpperBound = ComputeUpperBound(left, items, capacity, weightSelector, valueSelector);
            right.UpperBound = ComputeUpperBound(right, items, capacity, weightSelector, valueSelector);

            // IF upperBound of this node is larger than maxCumulativeValue,
            // the current path is still possible to reach or surpass the maximum value,
            // add current node to nodesQueue so that nodes below it can be further explored
            if (left.UpperBound > maxCumulativeValue && left.CumulativeWeight < capacity)
            {
                nodesQueue.Enqueue(left);
            }

            // Cumulative weight is the same as for parent node and < capacity
            if (right.UpperBound > maxCumulativeValue)
            {
                nodesQueue.Enqueue(right);
            }
        }

        return GetItemsFromPath(items, lastNodeOfOptimalPath);
    }

    // determine items taken based on the path
    private static T[] GetItemsFromPath(T[] items, BranchAndBoundNode lastNodeOfPath)
    {
        List<T> takenItems = new();

        // only bogus initial node has no parent
        for (var current = lastNodeOfPath; current.Parent is not null; current = current.Parent)
        {
            if(current.IsTaken)
            {
                takenItems.Add(items[current.Level]);
            }
        }

        return takenItems.ToArray();
    }

    /// <summary>
    ///     Returns the upper bound value of a given node.
    /// </summary>
    /// <param name="aNode">The given node.</param>
    /// <param name="items">All items to choose from.</param>
    /// <param name="capacity">The maximum weight capacity of the knapsack to be filled.</param>
    /// <param name="weightSelector">
    ///     A function that returns the value of the specified item
    ///     from the <paramref name="items">items</paramref> list.
    /// </param>
    /// <param name="valueSelector">
    ///     A function that returns the weight of the specified item
    ///     from the <paramref name="items">items</paramref> list.
    /// </param>
    /// <returns>
    ///     upper bound value of the given <paramref name="aNode">node</paramref>.
    /// </returns>
    private static double ComputeUpperBound(BranchAndBoundNode aNode, T[] items, int capacity, Func<T, int> weightSelector, Func<T, double> valueSelector)
    {
        var upperBound = aNode.CumulativeValue;
        var availableWeight = capacity - aNode.CumulativeWeight;
        var nextLevel = aNode.Level + 1;

        while (availableWeight > 0 && nextLevel < items.Length)
        {
            if (weightSelector(items[nextLevel]) <= availableWeight)
            {
                upperBound += valueSelector(items[nextLevel]);
                availableWeight -= weightSelector(items[nextLevel]);
            }
            else
            {
                upperBound += valueSelector(items[nextLevel]) / weightSelector(items[nextLevel]) * availableWeight;
                availableWeight = 0;
            }

            nextLevel++;
        }

        return upperBound;
    }
}