BRANCH AND BOUND

Information about BRANCH AND BOUND

Published on March 5, 2009

Author: ankush85

Source: authorstream.com

Content

BRANCH AND BOUND : 1 BRANCH AND BOUND Branch and bound is a state space search method in which all the children of a node are generated before expanding any of its children. BRANCH AND BOUND (Contd..) : 2 BRANCH AND BOUND (Contd..) 1 1 1 3 4 5 2 3 4 5 2 3 4 5 6 7 8 9 8 9 6 7 Live Nodes 2,3,4,5 FIFO Branch & Bound LIFO Branch & (Breadth First Search ) Bound (D-Search) LC- SEARCH : 3 LC- SEARCH In FIFO and LIFO Branch & Bound, the selection rule for the next E-node is rigid. The expansion of all live-nodes is required before the node leading to an answer node. The search for an answer node can be speeded up by using a ranking function c(.) for live nodes. LC- SEARCH (Contd..) : 4 LC- SEARCH (Contd..) c(x) is the estimated additional computational effort or the additional cost needed to reach an answer node from the live node X. The cost (of node X) could be (i) the number of nodes in the subtree that need to be generated before an answer node is generated or (ii) the number of levels the nearest answer node is from X. LC- SEARCH (Contd..) : 5 LC- SEARCH (Contd..) If cost measure (i) is used then the search would always generate the minimum number of nodes every branch and bound algorithm must generate. If cost measure (ii) is used, then the only nodes to become E-nodes are the nodes on the path from the root to the nearest answer node. C (x) is defined as below c(x)=f(h(x))+g(x) LC- SEARCH (Contd..) : 6 LC- SEARCH (Contd..) h(x) is the cost of reaching x from the root and f(.) is any non decreasing function. g (x) is the estimated additional effort or cost needed to reach an answer node from X. A search strategy that uses a cost function c(x) = f(h(x)) + g (x) to select the next E-node, would always choose for its next E-node, a live node with least c(.). Hence such a strategy is called Least cost search or LC-Search LC- SEARCH (Contd..) : 7 LC- SEARCH (Contd..) BFS and DFS are special cases of LC-Search LC search with g (x)=0 and f(h(x)) = level of x is BFS LC search with f(h(x)) =0 and g (x) >= g (y) whenever y is a child of x is DFS. LC-Search with bounding functions is LC branch and bound search. LC- SEARCH (Contd..) : 8 LC- SEARCH (Contd..) The Actual cost of X is denoted with c(X). Thus c(X) is an estimation of C(X). An LC-search expands the node with minimum cost c(X) . But it is not necessary that LC-search always finds an answer node with minimum cost. For two nodes X and Y with c(X) <c(y), it may be possible that c(X)>c(Y). Even if c(X)<c(Y) it may also be possible that a minimum cost answer node may not be found. LC- SEARCH - Algorithm : 9 LC- SEARCH - Algorithm // LC –search to find an answer node // procedure LC(T, c) if T is an answer node then output, return; endif E?T // E-node // Initialize the list of live nodes to empty loop for each child X of E do if X is an answer node then LC- SEARCH – Algorithm (Contd..) : 10 LC- SEARCH – Algorithm (Contd..) output the path from X to T return endif Call ADD(X) // X is a new live node // PARENT(X)? E // Pointer for path to root // repeat if there are no more live nodes then print (“no answer node”) stop endif call LEAST(E) // E is a pointer to current E-node // repeat end LC LC search for minimum cost answer node : 11 LC search for minimum cost answer node // LC search for minimum cost answer node // procedure LC1(T, c) E?T // First E-node // Initialize the list of live nodes to empty loop if E is an answer node then output path from E to T return endif LC search for minimum cost answer node (Contd..) : 12 LC search for minimum cost answer node (Contd..) for each child X of E do call ADD(X); PARENT(X)?E repeat if there are no more live nodes then print (“no answer node”) stop endif call least(E) repeat end LC1 LC search observation : 13 LC search observation In LC- Search to find an answer node, observe that the moment an answer node is found, control is returned; otherwise the nodes are stored and the least cost one is tested if it is an answer node In LC- Search to find a minimum cost answer node, observe that all the children are stored first and then tested for Least (E) BOUNDING : 14 BOUNDING Thus a minimum cost answer node is found if all live nodes are examined and terminated only when no more live nodes are available BOUNDING Three strategies FIFO,LIFO and LC are available to find minimum cost answer node. A cost function c(x) such that c(x) = c(x) is used to provide lower bounds on solutions BOUNDING (Contd..) : 15 BOUNDING (Contd..) If U is an upper bound ,on the cost of a minimum cost solution, then all live nodes with c(x)>U may be killed as c(x)= c(x) >U . In case an answer node with cost U has already been reached, then all live nodes with c(x) = U may be killed. The starting value for U may be obtained by some heuristic or may be set to 8. BOUNDING (Contd..) : 16 BOUNDING (Contd..) Each time a new answer node is found the value of U may be updated. A small positive constant ? is introduced such that for any two feasible nodes X and Y with U (X) <U(Y), then U(X) < U(X) + ? < U (Y). This ? is needed to distinguish between the case when a solution with cost U(X) has been found and the case when such a solution has not been found. BOUNDING (Contd..) : 17 BOUNDING (Contd..) When such a solution is not found the upper bound U is updated to min { U, U(X) + ? } and the live nodes Y with c(y) = U may be killed. This does not kill the node that promised to lead to a solution with value = U. Application of Branch and Bound : 18 Application of Branch and Bound Branch and bound algorithms can be applied to optimization problems. We only deal with minimization problems, because a maximization problem is easily converted into a minimization problem by changing the sign of the objective function. Application of Branch and Bound contd.. : 19 Application of Branch and Bound contd.. Searching for an optimal solution is equivalent to searching for a least cost answer node. The c(.) function will estimate the objective function value and not the cost of reaching an answer node. Any node representing a feasible solution will be an answer node. Answer nodes and solution nodes are indistinguishable. Implementing FIFO Branch and bound (FIFOBB) and LC branch and bound (LCBB) : 20 Implementing FIFO Branch and bound (FIFOBB) and LC branch and bound (LCBB) In FIFOBB, live nodes are stored in a queue and deleted from a queue. In LCBB live nodes are added to a min-heap and deleted from a min-heap. ZERO-ONE KNAPSACK PROBLEM : 21 ZERO-ONE KNAPSACK PROBLEM The modified knapsack problem is n minimize -?pixi i = 1 n subject to ?wixi = m i=1 xi = 0 or xi = 1 1=i=n ZERO-ONE KNAPSACK PROBLEM (Contd..) : 22 ZERO-ONE KNAPSACK PROBLEM (Contd..) The cost function c(x) is defined as follows for every feasible node (answer node), we define c(x)= -?pixi 1=i=n c(x)= 8 for infeasible leaf nodes For non leaf nodes, c(x) is recursively defined to be min{ c(LCHILD(X)), c(RCHILD(X))} c(x) and u(x) are defined such that c(x) =c(x) =u(x) for every node x. ZERO-ONE KNAPSACK PROBLEM Algorithm : 23 ZERO-ONE KNAPSACK PROBLEM Algorithm c(x)= -Bound (q, ?wixi, j-1, M) =c(X) 1=i=n Procedure Bound(p,w,k,M) // P current profit total, W current weight // // k index of the last removed item // // M is the knapsack size, the result is a new profit // global n, P(1:n),W(1:n) integer k, i, real b, c, p, w, M b?p; c?w ZERO-ONE KNAPSACK PROBLEM Algorithm(Contd..) : 24 ZERO-ONE KNAPSACK PROBLEM Algorithm(Contd..) for i?k+1 to n do c?c+w(i). if c < M then b?b+p(i) else return (b+(1-((C-M)/W(i))) P(i))) endif repeat return(b) end BOUND c(x) is the lower bound for c(X) procedure to find upper bound : 25 procedure to find upper bound U(x) = UBOUND (-?pixi , ?wixi , j-1, M) 1=i<j 1=i<j X is the node where x1,…… xj-1 are known procedure to find upper bound (Contd..) : 26 procedure to find upper bound (Contd..) Procedure UBOUND(p, w, k, m) // p current total profit, W current weight total, K index of last // // removed item, M the knapsack size. The result is a new profit // global n, p(1: n), W(1:n) integer k, I, real b, c, p, w, M b? p ; c?w for i?k+1 to n do if c + w(i) =M then c? c + w(i) ; b? b + p(i) endif repeat return (b) end UBOUND procedure to find lower bound - Example : 27 procedure to find lower bound - Example Example : Let the knapsack instance be n=4 : (p1, p2, p3, p4 ) = (10, 10 12, 18); (w1, w2, w3, w4) = (2, 4, 6, 9), M = 15 For the root i.e. node 1 c(1) = -38 because Bound (0, 0, 0, 15) is called Initially b? 0 ; c? 0 for I? 1 to 4 do i ? 1 c? 0+2 = 2 ; 2 < 15 so b? 0+ 10 ; i?2 , c? 2+4 = 6 < 15 so b? 10 + 10 =20 i?3 ; c? 6+6 =12<15 so b? 20+12=32; I?4, c?12+9=21>15 so b? 32 + (1-(6/9))x18) = 38 as negative procedure to find upper bound – Example : 28 procedure to find upper bound – Example Let us compute u(1) UBOUND (0,0,0,15) is called, Initially b?0; c?0 for i? 1 to 4 do i?1; c?0+2<15 so b?0 +10; i ? 2 c?2+4<15 so b?10+10=20; i?3 c?6+6=12<15 so b?20+12 = 32; i?4 c?21>M so return b = 32with negative sign ?U(1) = -32 Solution of Knapsack problem : 29 Solution of Knapsack problem Since node 1 is not a solution node, ans = 0 and U =u(1) + ? (u =8 initially) U= -32 + ? Node 1 is expanded to give two children nodes 2 and 3. Node 2 is corresponding to x1 =1 and node 3 is for x1=0 Let us compute c(2) , Û(2) and c(3), Û(3) values. For c(2) BOUND(-10,2,1,15) is called and for Û(2) UBOUND (-10,2,1,15) is called. Solution of Knapsack problem (contd..) : 30 Solution of Knapsack problem (contd..) We observe that c (2) =-38 and u(2) =-32. For c(3) BOUND (0,0,1,15) Is called and for u(3), UBOUND (0,0,1,15) is called. We observe that c(3)= -32 and u(3) = -22. As min (-38, -32) = -38,node 2 is expanded next. As min (-38, -36) = -38,node 4 is expanded next. c(x) for nodes 6 & 7 is same. Solution of Knapsack problem (contd..) : 31 Solution of Knapsack problem (contd..) c (X) = -38 U(X) = -32 xi=1 xi= 0 1 -38 -32 -32 2 3 -22 -38 -36 -32 4 5 -32 -38 7 -38 -32 6 -38 -38 -20 -38 8 9 -20 Solution of Knapsack problem (contd..) : 32 Solution of Knapsack problem (contd..) Let us assume node 7 is expanded. As u(7) + ? = -38 + ? < U=-32+ ? ,so U is updated to u(7)+ ? = -38 + ? Node 8 is a solution node,so u is updated to min{u(8), u(8)+ ? } = -38 c(9) = -20 >U so it is killed. For nodes 6 and 8(which are live nodes c (E) = U so search terminates with node 8 the answer node. Least cost is –38 and the path is 8, 7, 4, 2,1. Solution of Knapsack problem (contd..) : 33 Solution of Knapsack problem (contd..) To find values of xi’s, a bit field, TAG is associated with each node. TAG(2) = TAG(4) = TAG (6)= TAG(8)=1 and TAG(3)= TAG(5)= TAG(7)= TAG(9) = 0. Hence xi =1, x2 =1, x3= 0, x4= 0.

Related presentations


Other presentations created by ankush85

Nanotechnology
03. 04. 2009
0 views

Nanotechnology

Human Resource Management System
06. 03. 2009
0 views

Human Resource Management System

Nanotechnology
27. 03. 2009
0 views

Nanotechnology

INTRODUCTION TO NANOTECHNOLOGY
20. 11. 2009
0 views

INTRODUCTION TO NANOTECHNOLOGY

Nanotechnology in Sports
22. 11. 2009
0 views

Nanotechnology in Sports

Computer Architecture
14. 07. 2009
0 views

Computer Architecture

HR
18. 03. 2009
0 views

HR

Hospital Management System
08. 04. 2009
0 views

Hospital Management System

Welcome to Visual Basic
06. 03. 2009
0 views

Welcome to Visual Basic

HTML
20. 04. 2009
0 views

HTML

Computer Languages
03. 06. 2013
0 views

Computer Languages

Taking Care of Computer
03. 06. 2013
0 views

Taking Care of Computer

Understanding Camera
16. 10. 2012
0 views

Understanding Camera

Photography Technical Terms
25. 09. 2012
0 views

Photography Technical Terms

Basics of Photography
25. 09. 2012
0 views

Basics of Photography

AIR MUSCLES
03. 01. 2012
0 views

AIR MUSCLES

Molecular Nanotechnology
24. 11. 2009
0 views

Molecular Nanotechnology

Nanotech Innovation
22. 11. 2009
0 views

Nanotech Innovation

FINANCIAL  MARKET
16. 05. 2009
0 views

FINANCIAL MARKET

Operating System
19. 04. 2009
0 views

Operating System

Management Control
10. 07. 2009
0 views

Management Control

Accounting Principles
01. 07. 2009
0 views

Accounting Principles

Balance Sheet
21. 07. 2009
0 views

Balance Sheet

Balance Sheet Auditing
01. 07. 2009
0 views

Balance Sheet Auditing

THE  THREE  BRANCHES  OF GOVERNMENT
13. 06. 2009
0 views

THE THREE BRANCHES OF GOVERNMENT

Structure of Atom
11. 05. 2009
0 views

Structure of Atom

Compression Techniques
05. 03. 2009
0 views

Compression Techniques

DYNAMIC PROGRAMMING
06. 03. 2009
0 views

DYNAMIC PROGRAMMING

Quantum Mechanics
25. 08. 2009
0 views

Quantum Mechanics

Marketing Plan
19. 06. 2009
0 views

Marketing Plan

Book Keeping
24. 06. 2009
0 views

Book Keeping

DFDS
02. 10. 2008
0 views

DFDS

Semiconductors
25. 04. 2009
0 views

Semiconductors

Organic  Chemistry
28. 04. 2009
0 views

Organic Chemistry

Atoms Molecules and Ions
17. 06. 2009
0 views

Atoms Molecules and Ions

Covalent Bond
25. 04. 2009
0 views

Covalent Bond

Cost Accounting Standards
25. 06. 2009
0 views

Cost Accounting Standards

Crisis Management
19. 06. 2009
0 views

Crisis Management

Marketing
18. 03. 2009
0 views

Marketing

Business Strategy
27. 04. 2009
0 views

Business Strategy

Time Management
23. 03. 2009
0 views

Time Management

Networking Protocols
23. 05. 2009
0 views

Networking Protocols

Network Layer
23. 05. 2009
0 views

Network Layer

Final Accounts
24. 06. 2009
0 views

Final Accounts

ARTIFICIAL  INTELLIGENCE
03. 04. 2009
0 views

ARTIFICIAL INTELLIGENCE

Play with C
08. 04. 2009
0 views

Play with C

Software Development Cycle
23. 03. 2009
0 views

Software Development Cycle

THE GREEDY METHOD
06. 03. 2009
0 views

THE GREEDY METHOD

JOB SEQUENCING
06. 03. 2009
0 views

JOB SEQUENCING

Electricity and Magnetism
29. 04. 2009
0 views

Electricity and Magnetism

Optical Fiber
24. 05. 2009
0 views

Optical Fiber

Quality Assurance
06. 03. 2009
0 views

Quality Assurance

Object-oriented Design
11. 04. 2009
0 views

Object-oriented Design

A.R. Rahman
08. 03. 2009
0 views

A.R. Rahman

Hollywood Female Celebrities
13. 03. 2009
0 views

Hollywood Female Celebrities

Flow nets
04. 09. 2009
0 views

Flow nets

Energy and Nanotechnology
22. 11. 2009
0 views

Energy and Nanotechnology

LOGIC  DESIGN
06. 03. 2009
0 views

LOGIC DESIGN

VB-IDE
06. 03. 2009
0 views

VB-IDE

DLF IPL FINAL
25. 05. 2009
0 views

DLF IPL FINAL

MINIMUM SPANNING TREES
06. 03. 2009
0 views

MINIMUM SPANNING TREES

CPU Scheduling
05. 03. 2009
0 views

CPU Scheduling

Virtual Memory
05. 03. 2009
0 views

Virtual Memory

POK
09. 05. 2009
0 views

POK

2D Transformations
05. 03. 2009
0 views

2D Transformations

Greedy Algorithms
05. 03. 2009
0 views

Greedy Algorithms

BACKTRACKING
05. 03. 2009
0 views

BACKTRACKING

DIVIDE And CONQUER
06. 03. 2009
0 views

DIVIDE And CONQUER

ELEMENTARY DATA STRUCTURES
06. 03. 2009
0 views

ELEMENTARY DATA STRUCTURES

JPEG Compression
06. 03. 2009
0 views

JPEG Compression

Mpeg-compression
06. 03. 2009
0 views

Mpeg-compression

NP - HARD
06. 03. 2009
0 views

NP - HARD

TRAVELLING SALESPERSON PROBLEM
06. 03. 2009
0 views

TRAVELLING SALESPERSON PROBLEM

VBA Introduction
06. 03. 2009
0 views

VBA Introduction

Introduction to Java
09. 03. 2009
0 views

Introduction to Java

Java  Basics
09. 03. 2009
0 views

Java Basics

Heuristic Search
13. 03. 2009
0 views

Heuristic Search

HSM
19. 03. 2009
0 views

HSM

Tata's  Nano  Car
25. 03. 2009
0 views

Tata's Nano Car

Air Cranes
08. 04. 2009
0 views

Air Cranes

Newborn Care
10. 04. 2009
0 views

Newborn Care

Photosynthesis Process
10. 04. 2009
0 views

Photosynthesis Process

ActionScript
13. 04. 2009
0 views

ActionScript

Xml
15. 04. 2009
0 views

Xml

Snakes mis use
17. 04. 2009
0 views

Snakes mis use

Php Web Development
21. 04. 2009
0 views

Php Web Development

Cricket Intro
21. 04. 2009
0 views

Cricket Intro

Cricket Umpiring and Rules
21. 04. 2009
0 views

Cricket Umpiring and Rules

Arm and Forearm
23. 04. 2009
0 views

Arm and Forearm

Elements Ions Isotopes
25. 04. 2009
0 views

Elements Ions Isotopes

Chemical Bond
25. 04. 2009
0 views

Chemical Bond

Discovering Newtons Laws
29. 04. 2009
0 views

Discovering Newtons Laws

FreeFall
29. 04. 2009
0 views

FreeFall

Digital photography
26. 04. 2009
0 views

Digital photography

Health Effects of Alcohol
26. 04. 2009
0 views

Health Effects of Alcohol

Poetry Terminology
27. 04. 2009
0 views

Poetry Terminology

Indian Force
05. 05. 2009
0 views

Indian Force

Machine Intelligence
14. 05. 2009
0 views

Machine Intelligence

Data Link Layer
16. 05. 2009
0 views

Data Link Layer

Database Development Cycle
15. 05. 2009
0 views

Database Development Cycle

Queue
15. 05. 2009
0 views

Queue

Presentaion Skills
23. 04. 2009
0 views

Presentaion Skills

Network Layers
23. 05. 2009
0 views

Network Layers

Narmada Dam, India
23. 05. 2009
0 views

Narmada Dam, India

User Datagram Protocol
24. 05. 2009
0 views

User Datagram Protocol

Linear Momentum
28. 05. 2009
0 views

Linear Momentum

Stack and Queue
04. 06. 2009
0 views

Stack and Queue

Information Management
19. 06. 2009
0 views

Information Management

Role of Senior Management
19. 06. 2009
0 views

Role of Senior Management

Wake Up India
07. 06. 2009
0 views

Wake Up India

Adobe Flex 3.0
13. 06. 2009
0 views

Adobe Flex 3.0

Adobe Flex Presentation
13. 06. 2009
0 views

Adobe Flex Presentation

Introduction to Adobe Flex
13. 06. 2009
0 views

Introduction to Adobe Flex

Adobe Flash Media Server
13. 06. 2009
0 views

Adobe Flash Media Server

Dreamweaver
13. 06. 2009
0 views

Dreamweaver

Adobe Flash
13. 06. 2009
0 views

Adobe Flash

Flash CS4 Professional
13. 06. 2009
0 views

Flash CS4 Professional

Adobe Flash Lite
13. 06. 2009
0 views

Adobe Flash Lite

Digital Camera
13. 06. 2009
0 views

Digital Camera

Mozilla_Firefox
15. 06. 2009
0 views

Mozilla_Firefox

Managerial Accounting
27. 06. 2009
0 views

Managerial Accounting

Accounting  Information  System
01. 07. 2009
0 views

Accounting Information System

RETAILING AND MARKETING
06. 07. 2009
0 views

RETAILING AND MARKETING

ACCOUNTING IN BUSINESS
05. 07. 2009
0 views

ACCOUNTING IN BUSINESS

STRATEGIC RETAIL MANAGEMENT
05. 07. 2009
0 views

STRATEGIC RETAIL MANAGEMENT

Reiki
01. 08. 2009
0 views

Reiki

Using Buttons in PowerPoint
26. 04. 2009
0 views

Using Buttons in PowerPoint

Nanotechnology  for  Students
21. 08. 2009
0 views

Nanotechnology for Students

NANOSCIENCE
25. 08. 2009
0 views

NANOSCIENCE

Fundamentals of Nanoscience
27. 08. 2009
0 views

Fundamentals of Nanoscience

Nanoscience in Nature
27. 08. 2009
0 views

Nanoscience in Nature

Applied Mechanics
04. 09. 2009
0 views

Applied Mechanics

Accounts Payable Training
27. 06. 2009
0 views

Accounts Payable Training