Branch and Bound

Algorithm Series 2

Branch and Bound

What is branch and bound?
Branch-and-bound consists of a systematic enumeration of all candidate solutions, where large subsets of fruitless candidates are discarded en masse, by using upper and lower estimated bounds of the quantity being optimized.

The key idea of the BB algorithm is: if the lower bound for some tree node (set of candidates) A is greater than the upper bound for some other node B, then A may be safely discarded from the search. This step is called pruning.

How?
Branch-and-bound is composed of two main actions:
The first step is the branching. This is where we define the tree structure from the set of candidates in a recursive manner.
The second action is called bounding since this procedure calculates the upper and lower bounds of each node from the tree.

Furthermore, there's the additional pruning step that we can add. It means that if the lower bound for some node of the tree is greater than the upper bound of some other node of the tree, then the first node of the tree can be "discarded" from the search. A variable always holds the value of the global minimum upper bound.

A branch and bound algorithm is based on an advanced breadth-first search. The said BFS is done with a priority queue instead of the traditional list.

Main steps is to branch and prune, then enqueue/and dequeue.

Normally branch and bound algorithm is implemented with breadth-first search and FIFO queue or priority queue.

Both the backtracking and divide and conquer traverse the tree of problem space in its depth, though they take opposite routes. The greedy strategy picks a single route and forgets about the rest. Dynamic programming approaches this in a sort of breadth-first search variation (BFS).

Examples
KnapSack
Knapsack Backtracking Solutions with/without bounding functions
KnapSack_Back.java        0/1 knapsack implemented in Java
IntKS_Back.java           Integer knapsack implemented in Java

0/1 KnapSack
cw(i) = sum(j=1..i)w[j]*x[j]
Constraint function
C(i) = cw(i-1) + w[i] if C(i) > W then discard its subtree
Bound function
B(i) = C(i) + r(i)
r(i) = sum(j=i+1..n)v[j]
if B(i) <=bestw, then discard its subtree

Put special node to the queue (-1) to indicate we have done finishes this layer of the tree.

Max loading
Similar as 0/1 KnapSack

Travelling salesman problem
cw(i) = sum(j=2..i)w[x[j-1],x[j]]
Bound function
B(i) = cw(i-1) + w[x[j-1],x[j]] if B(i) >= bestw, then discard its subtree

Flow shop[to-do]
N queen [FIFO BB]
运动员最佳匹配

Resources:
Post a Comment

Labels

Java (159) Lucene-Solr (112) Interview (61) All (58) J2SE (53) Algorithm (45) Soft Skills (38) Eclipse (33) Code Example (31) Linux (25) JavaScript (23) Spring (22) Windows (22) Web Development (20) Tools (19) Nutch2 (18) Bugs (17) Debug (16) Defects (14) Text Mining (14) J2EE (13) Network (13) Troubleshooting (13) PowerShell (11) Chrome (9) Design (9) How to (9) Learning code (9) Performance (9) Problem Solving (9) UIMA (9) html (9) Http Client (8) Maven (8) Security (8) bat (8) blogger (8) Big Data (7) Continuous Integration (7) Google (7) Guava (7) JSON (7) Shell (7) ANT (6) Coding Skills (6) Database (6) Lesson Learned (6) Programmer Skills (6) Scala (6) Tips (6) css (6) Algorithm Series (5) Cache (5) Dynamic Languages (5) IDE (5) System Design (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) Miscs (4) OpenNLP (4) Project Managment (4) Spark (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Bit Operation (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Firefox (2) Google Drive (2) Gson (2) How to Interview (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Python (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts