Reference example: comparing Depth-First and Best-First strategies in Branch-and-Bound on a 0/1 knapsack problem. More...

#include <cstddef>
#include <iostream>
#include <string>
#include <Branch_And_Bound.H>
#include <tpl_array.H>

Include dependency graph for branch_and_bound_df_vs_bf_example.cc:

Classes
struct	Item

struct	KnapsackState

class	KnapsackDomain

struct	KnapsackDomain::Move

Functions
static void	run_strategy (const Array< Item > &items, double capacity, ExplorationPolicy::Strategy strategy, const std::string &label)

int	main ()

Detailed Description

Reference example: comparing Depth-First and Best-First strategies in Branch-and-Bound on a 0/1 knapsack problem.

The 0/1 knapsack problem assigns a binary decision (include / exclude) to each item. Branch-and-Bound prunes subtrees whose optimistic upper bound cannot beat the current incumbent.

Depth-First (the default) quickly finds a first feasible solution and tightens the bound early, but may explore many nodes before proving optimality.

Best-First expands nodes in decreasing order of their optimistic bound, so it tends to reach the optimum with fewer expansions — at the cost of maintaining a priority queue.

This example runs both strategies on the same instance and prints the results side-by-side.

Build and run: