Branch & Bound Algorithm: LP Based Approach

In course

Description

This lecture covers the Branch & Bound algorithm, focusing on the LP-based approach. It explains the steps involved, such as branching, pruning, and bounding, to find the optimal solution efficiently. The instructor discusses examples and applications, including the Pigeonhole Problem and Directed TSP Lower Bound.

Instructor

Official source

https://mediaspace.epfl.ch/media/0_tcjpga47

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related lectures (38)

Related concepts (41)

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.

Branch and cut

Branch and cut is a method of combinatorial optimization for solving integer linear programs (ILPs), that is, linear programming (LP) problems where some or all the unknowns are restricted to integer values. Branch and cut involves running a branch and bound algorithm and using cutting planes to tighten the linear programming relaxations. Note that if cuts are only used to tighten the initial LP relaxation, the algorithm is called cut and branch. This description assumes the ILP is a maximization problem.

Linear programming

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization). More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints.

Intertemporal portfolio choice

Intertemporal portfolio choice is the process of allocating one's investable wealth to various assets, especially financial assets, repeatedly over time, in such a way as to optimize some criterion. The set of asset proportions at any time defines a portfolio. Since the returns on almost all assets are not fully predictable, the criterion has to take financial risk into account. Typically the criterion is the expected value of some concave function of the value of the portfolio after a certain number of time periods—that is, the expected utility of final wealth.

Bounding volume

In computer graphics and computational geometry, a bounding volume for a set of objects is a closed volume that completely contains the union of the objects in the set. Bounding volumes are used to improve the efficiency of geometrical operations by using simple volumes to contain more complex objects. Normally, simpler volumes have simpler ways to test for overlap. A bounding volume for a set of objects is also a bounding volume for the single object consisting of their union, and the other way around.