Scribd Logo
Upload

Welcome to Scribd!

  • 9 views

    Branch and Bound

    Uploaded by

    veekaprogramming
    This document summarizes the branch and bound algorithm and how it can be applied to the problem of graph bisection. It describes how branch and bound implicitly enumerates solutions by dividing the problem into subproblems, solving them recursively, and selecting the best solution. For graph bisection, each node in the branch and bound tree represents a partial assignment of vertices to two cells, and lower bounds are used to prune nodes that cannot lead to better solutions than the current best in order to limit the search space.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Branch and Bound

    Uploaded by

    veekaprogramming
    9 views3 pages
    This document summarizes the branch and bound algorithm and how it can be applied to the problem of graph bisection. It describes how branch and bound implicitly enumerates solutions by dividing the problem into subproblems, solving them recursively, and selecting the best solution. For graph bisection, each node in the branch and bound tree represents a partial assignment of vertices to two cells, and lower bounds are used to prune nodes that cannot lead to better solutions than the current best in order to limit the search space.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document summarizes the branch and bound algorithm and how it can be applied to the problem of graph bisection. It describes how branch and bound implicitly enumerates solutions by dividing the problem into subproblems, solving them recursively, and selecting the best solution. For graph bisection, each node in the branch and bound tree represents a partial assignment of vertices to two cells, and lower bounds are used to prune nodes that cannot lead to better solutions than the current best in order to limit the search space.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    9 views3 pages

    Branch and Bound

    Uploaded by

    veekaprogramming
    This document summarizes the branch and bound algorithm and how it can be applied to the problem of graph bisection. It describes how branch and bound implicitly enumerates solutions by dividing the problem into subproblems, solving them recursively, and selecting the best solution. For graph bisection, each node in the branch and bound tree represents a partial assignment of vertices to two cells, and lower bounds are used to prune nodes that cannot lead to better solutions than the current best in order to limit the search space.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 3

    ELEC 379 Algorithms with Eng.

    Applications Branch and Bound


    Dr. Naraig Manjikian, P.Eng.

    Branch and Bound


    (with Graph Bisection
    as Application)
    conceptual description based on Section 2 (‘Preliminaries’) of
    Delling/Goldberg/Razenshteyn/Werneck,
    “Exact Combinatorial Branch-and-Bound for Graph Bisection,”
    presented at DIMACS 2012 conference

    with additional aspects by Dr. N. Manjikian

    Graph Representation
    • G = (V,E) – graph consisting of a set of vertices V and a set of edges E
    • Vertices and edges may have different weights (or same value of 1)
    • Seek a partition of G into a set of cells
    • Each cell is a subset of V; the cells are disjoint and their union is V
    • The cost of the partition is the sum of weights for those edges
    whose endpoint vertices are in different cells (i.e., edges that are cut)
    • A bisection of G is the special case of partitioning into two cells
    • A balanced bisection has the same sum of vertex weights in both cells
    • Seek a minimum-cost balanced bisection of G
    2

    Dept. of Elec./Comp. Eng.


    Queen's University
    ELEC 379 Algorithms with Eng. Applications Branch and Bound
    Dr. Naraig Manjikian, P.Eng.

    Branch and Bound Technique


    • Branch and bound implicitly enumerates paths towards solution by:
    • dividing problem into two or more slightly simpler subproblems,
    • solving them recursively, then
    • selecting the best solution found
    • The paths towards the solution can be represented in a tree format
    • Nodes in tree are subproblems; they are linked to a parent problem
    • Any leaf node reflects a complete feasible solution (with its cost),
    or an early stopping point for that path if a condition is not satisfied,
    such as failing to maintain the balance between cells of the partition

    Branch and Bound Technique


    • If we construct/traverse entire tree, search space can be quite large
    • Instead, we maintain an upper bound U on the cost of best solution
    • Revise U as better (lower-cost) solutions encountered during search
    • For each node, determine lower bound L for any subproblem solution
    • If L  U, then no better solution exists on this path, so prune the node
    • Otherwise, continue search with two or more new subproblems
    • Thus, the algorithm branches to create new nodes in the search tree,
    but uses bounds to limit the scope of search to better solution paths

    Dept. of Elec./Comp. Eng.


    Queen's University
    ELEC 379 Algorithms with Eng. Applications Branch and Bound
    Dr. Naraig Manjikian, P.Eng.

    B&B Tree Nodes for Graph Bisection


    • For graph bisection, each node is a partial assignment (A,B) where
    A and B are disjoint subsets of V containing vertices assigned so far
    • Each node represents all possible valid bisections (A,B) that are
    extensions of (A,B) obtained by assigning more vertices to A and B
    • Root node has one initial vertex assigned, i.e., (A,B) = ({v}, )
    • Processing of any node starts with determining lower bound L(A,B)
    for cost of any extension (A,B) of (A,B), if subproblems are explored
    • Lower bounds must be accurate, though not necessarily exact
    • We must not mistakenly prune a viable and potentially better path,
    but we may explore more suboptimal portions of search space
    5

    Example Lower-Bound Functions for Cost


    • Simplest: assume constant lower bound of zero cost
    • Accurate: any solution will always have same or higher cost than zero
    • Certainly not exact: all possible solutions permitted; no pruning

    • Better: as each vertex assigned to A or B, update partial cost for node


    based on edges cut between that vertex and other assigned vertices
    • Accurate: partial cost can never exceed actual final cost for a solution
    • More exact: partial cost of a node may exceed current upper bound,
    so that node can be pruned, thereby reducing the search space
    6

    Dept. of Elec./Comp. Eng.


    Queen's University

    You might also like