Package topics.branchandbound

package topics.branchandbound

Branch-and-Bound algorithms — intelligent search for combinatorial optimisation.

Branch and Bound systematically enumerates candidate solutions by partitioning the search space into sub-problems (branching) while using upper/lower bounds to discard sub-problems that cannot yield a solution better than the current best (bounding). It guarantees optimality while avoiding full enumeration.

Core Steps

1. Branch: partition the current node into child nodes.
2. Bound: compute a bound on the optimal value reachable from each child.
3. Prune: discard any child whose bound is worse than the best solution found so far.
4. Select: choose the next node to expand (best-first, depth-first, etc.).

Comparison with Related Techniques

• Backtracking — explores all valid solutions; no cost bounds.
• Dynamic Programming — solves overlapping sub-problems; polynomial time.
• Branch & Bound — optimal solution via bounding; variable time.

Classes in This Package

• AgentsTasks — optimal assignment of agents to tasks
• EightPuzzle — 8-puzzle solver
• RectanglesPlacement — optimal rectangle packing
• RectanglesPlacementThreads — multi-threaded variant

Related Packages

Package	Description
topics.branchandbound.times	Execution-time benchmarks for branch-and-bound algorithms.
topics.branchandbound.util	Utility classes shared by branch-and-bound implementations.

Classes

Class	Description
AgentsTasks	BRANCH AND BOUND PROBLEM: THE PROBLEM OF ASSIGNING N TASK TO AGENTS
EightPuzzle	BRANCH AND BOUND PROBLEM: THE PUZZLE
RectanglesPlacement	BRANCH AND BOUND PROBLEM: OPTIMAL PLACEMENT OF RECTANGLES
RectanglesPlacementThreads	BRANCH AND BOUND PROBLEM: OPTIMAL PLACEMENT OF RECTANGLES