Recursive branch and bound Knapsack solution [closed]

Question

I've got the imperative styled solution working perfectly. What I'm wondering is how to make a recursive branch and bound.

This is my code below. Evaluate function returns the optimistic estimate, the largest possible value for the set of items which fit into the knapsack (linear relaxation).

For some inputs this outputs an optimal solution, for some it comes really close, for every input it is extremely fast, so it doesn't seem that it hangs anywhere in the search space. So, maybe I'm not branching where I have to or I did something wrong. I'm sure optVal is optimal.

def branch(items: List[Item], taken: List[Item], capacity: Int, eval: Long): (List[Item], Boolean) = items match {
  case x :: xs if x.weight <= capacity => {

    val (bestLeft, opt) = branch(xs, x :: taken, capacity - x.weight, eval)
    if (opt) (bestLeft, opt) // if solution is optimal get out of the tree
    else {
      val evalWithout = evaluate(taken.reverse_:::(xs))

      if (evalWithout < optVal) (bestLeft, opt)
      else branch(xs, taken, capacity, evalWithout)
    }
  }
  case x :: xs => branch(xs, taken, capacity, evaluate(taken.reverse_:::(xs)))

  case Nil => if ((taken map (_.value) sum) == optVal) (taken, true) else (taken, false)
}

Answer 1

Here is a 'wanna-be functional' solution in java which might help you (it has gone through a set of test cases so I believe it works correctly)

private double bestBound;

public Knapsack.KnapsackResult solve() {
    Cons<Knapsack.Item> list = Cons.from(items);
    bestBound = 0.0;

    double bound = calcBound(list, capacity, 0.0);
    Solution res = dfs(list, 0, capacity, bound, null);

    return buildSolution(res);
}

public Solution dfs(Cons<Knapsack.Item> list, int value, int weight, double bound,
        Cons<Knapsack.Item> taken) {
    if (bound < bestBound) {
        return null;
    }
    if (list == null) {
        bestBound = bound;
        return new Solution(bound, taken);
    }
    Knapsack.Item item = list.head();
    if (item.weight > weight) {
        return notTaking(list, value, weight, taken);
    }

    // taking the item
    Solution left = dfs(list.tail(), value + item.value, weight - item.weight, 
        bound, Cons.cons(item, taken));

    // not taking the item
    Solution right = notTaking(list, value, weight, taken);

    if (left == null) {
        return right;
    }
    if (right == null) {
        return left;
    }
    if (right.bound > left.bound) {
        return right;
    } else {
        return left;
    }
}

private Solution notTaking(Cons<Knapsack.Item> list, int value, int weight, 
        Cons<Knapsack.Item> taken) {
    Cons<Knapsack.Item> tail = list.tail();
    Cons<Knapsack.Item> without;
    if (taken != null) {
        without = taken.reverse().append(tail);
    } else {
        without = tail;
    }
    double newBound = calcBound(without, capacity, 0.0);
    if (newBound <= bestBound) {
        return null;
    }
    return dfs(tail, value, weight, newBound, taken);
}

public static double calcBound(Cons<Knapsack.Item> list, int k, double acc) {
    if (list == null) {
        return acc;
    }

    Knapsack.Item head = list.head();
    if (head.weight <= k) {
        return calcBound(list.tail(), k - head.weight, acc + head.value);
    } else {
        return acc + head.relativeValue() * k;
    }
}

Here I used cons for lists - so it's the same as lists in Scala. There's only one "global" variable - bestBound - which, I know, not very functional, but it was just simpler than passing it around.