Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Branch and Bound: Formal Description

In course

MATH-504: Integer optimisation

The course aims to introduce the basic concepts and results of integer optimization with special emphasis on algorithmic problems on lattices that have proved to be important in theoretical computer science and cryptography during the past 30 years. ...

Description

This lecture covers the Branch and Bound algorithm, focusing on the formal description and implementation steps. It explains how to initiate and iterate the algorithm, finding optimal integer solutions within a bounded polyhedron. The instructor demonstrates how Branch and Bound efficiently explores the solution space, leading to the discovery of approximate integer solutions.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Official source

Related concepts (22)

Branch and bound

Branch and bound (BB, B&B, or BnB) is a method for solving optimization problems by breaking them down into smaller sub-problems and using a bounding function to eliminate sub-problems that cannot contain the optimal solution. It is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root.

Feasible region

In mathematical optimization, a feasible region, feasible set, search space, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, potentially including inequalities, equalities, and integer constraints. This is the initial set of candidate solutions to the problem, before the set of candidates has been narrowed down.

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning), achieving automation eventually.

Integer programming

An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints (other than the integer constraints) are linear. Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems.

Polyhedron

In geometry, a polyhedron (: polyhedra or polyhedrons; ) is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices. A convex polyhedron is a polyhedron that bounds a convex set. Every convex polyhedron can be constructed as the convex hull of its vertices, and for every finite set of points, not all on the same plane, the convex hull is a convex polyhedron. Cubes and pyramids are examples of convex polyhedra. A polyhedron is a 3-dimensional example of a polytope, a more general concept in any number of dimensions.

Related lectures (31)

Approximation Algorithms

Covers approximation algorithms for optimization problems, LP relaxation, and randomized rounding techniques.

Optimization: Classical Problems

Covers classical optimization problems, brute force algorithms, and integer linear optimization.

Algorithms & Growth of Functions

Covers optimization algorithms, stable matching, and Big-O notation for algorithm efficiency.

Exact methods: Branch and Bound MOOC: Optimization: principles and algorithms - Network and discrete optimization

Explores the Branch and Bound algorithm in discrete optimization, efficiently finding optimal solutions by calculating lower bounds on subsets.