**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Lecture# Branch & Bound: Optimization

Description

This lecture covers the Branch & Bound algorithm, a divide and conquer approach to explore feasible solutions efficiently by using bounds on the optimal cost. The algorithm iteratively partitions the problem into subproblems, computes lower and upper bounds, and prunes infeasible solutions. LP-based Branch & Bound is discussed, along with examples demonstrating the algorithm's application. The lecture also delves into the Pigeonhole Problem, LP relaxation, and portfolio optimization, emphasizing the trade-off between risk and return. Additionally, it explores Nonlinear Programming, the Fermat-Weber Problem, and the Ball Circumscription Problem.

Official source

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.

Instructor

In course

Related concepts (79)

MGT-483: Optimal decision making

This course introduces the theory and applications of optimization. We develop tools and concepts of optimization and decision analysis that enable managers in manufacturing, service operations, marke

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.

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.

Combinatorial optimization

Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead.

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.

Nonlinear programming

In mathematics, nonlinear programming (NLP) is the process of solving an optimization problem where some of the constraints or the objective function are nonlinear. An optimization problem is one of calculation of the extrema (maxima, minima or stationary points) of an objective function over a set of unknown real variables and conditional to the satisfaction of a system of equalities and inequalities, collectively termed constraints. It is the sub-field of mathematical optimization that deals with problems that are not linear.

Related lectures (121)

Approximation AlgorithmsCS-450: Algorithms II

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

Optimization Problems: Path Finding and Portfolio AllocationMGT-483: Optimal decision making

Covers optimization problems in path finding and portfolio allocation.

Optimisation in Energy SystemsME-454: Modelling and optimization of energy systems

Explores optimization in energy system modeling, covering decision variables, objective functions, and different strategies with their pros and cons.

Optimization Methods: Theory DiscussionME-454: Modelling and optimization of energy systems

Explores optimization methods, including unconstrained problems, linear programming, and heuristic approaches.

Set Cover: Integrality GapCS-450: Algorithms II

Explores the integrality gap concept in set cover and multiplicative weights algorithms.