New version page

WMU CS 6260 - PARALLEL ALGORITHMS IN COMBINATORIAL OPTIMIZATION PROBLEMS

Upgrade to remove ads

This preview shows page 1-2-3-21-22-23-43-44-45 out of 45 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

CS 6260 Parallel Computation Parallel Algorithms In Combinatorial Optimization ProblemsTopics covered are:Branch and boundSlide 4BacktrackingSlide 6Pruning SearchSlide 8Backtracking Depth-First SearchSlide 10Slide 11Slide 12Slide 13Slide 14ExampleSlide 16Divide and conquerAdvantagesIn Parallelism...Slide 20Greedy MethodsExamplesknapsackThe Original Knapsack Problem (1)The Original Knapsack Problem (2)0/1 Knapsack Problem (1)0/1 Knapsack Problem (2)Greedy Attempts for 0/1 KnapsackThe Shortest Path ProblemTypes of The Shortest Path ProblemSingle-Source Single-Destination Shorted pathGreedy Single-Source All-Destinations Shortest Path (1)Greedy Single-Source All-Destinations Shortest Path (2)Greedy Single Source All Destinations: Example (1)Greedy Single Source All Destinations : Example (2)Greedy Single Source All Destinations : Example (3)Greedy Single Source All Destinations : Example (4)Greedy Single Source All Destinations : Example (5)Greedy Single Source All Destinations : Example (6)Slide 40Slide 41Use of Algorithms in ParallelUse of algorithms in parallelQ & A Branch and Bound Vs. Backtracking?ReferencesCS 6260PARALLEL COMPUTATIONPARALLEL ALGORITHMS IN COMBINATORIAL OPTIMIZATION PROBLEMSProfessor:Elise De DonckerPresented By:Lina Hussein1TOPICS COVERED ARE:BacktrackingBranch and boundDivide and conquerGreedy Methods Short paths algorithms2BRANCH AND BOUNDBranch and bound (BB) is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. It consists of a systematic enumeration of all candidate solutions, where large subsets of fruitless candidates are discarded en masse (all together), by using upper and lower estimated bounds of the quantity being optimized.3BRANCH AND BOUNDIf we picture the subproblems graphically, then we form a search tree.Each subproblem is linked to its parent and eventually to its children.Eliminating a problem from further consideration is called pruning or fathoming.The act of bounding and then branching is called processing.A subproblem that has not yet been considered is called a candidate for processing.The set of candidates for processing is called the candidate list.Going back on the path from a node to its root is called backtracking.4BACKTRACKINGBacktracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate ("backtracks") as soon as it determines that it cannot possibly be completed to a valid solution..The Algorithm systematically searches for a solution to a problem among all available options. It does so by assuming that the solutions are represented by vectors (v1, ..., vi) of values and by traversing in a depth first manner the domains of the vectors until the solutions are found. 5BACKTRACKINGA systematic way to iterate through all the possible configurations of a search space.Solution: a vector v = (v1,v2,…,vi)At each step, we start from a given partial solution, say, v=(v1,v2,…,vk), and try to extend it by adding another element at the end.If so, we should count (or print,…) it.If not, check whether possible extension exits.If so, recur and continueIf not, delete vk and try another possibility.ALGORITHM try(v1,...,vi) IF(v1,...,vi)isasolutionTHENRETURN(v1,...,vi) FOReachvDO IF(v1,...,vi,v)isacceptablevectorTHENsol=try(v1,...,vi,v) IFsol!=()THENRETURNsol  END END RETURN() 6PRUNING SEARCH If Si is the domain of vi, then S1 × ... × Sm is the solution space of the problem. The validity criteria used in checking for acceptable vectors determines what portion of that space needs to be searched, and so it also determines the resources required by the algorithm. To make a backtracking program efficient enough to solve interesting problems, we must prune the search space by terminating for every search path the instant that is clear not to lead to a solution.7S1 S2 S2V1...V2.............................................................BACKTRACKINGThe traversal of the solution space can be represented by a depth-first traversal of a tree. The tree itself is rarely entirely stored by the algorithm in discourse; instead just a path toward a root is stored, to enable the backtracking. When you move forward on an x =1 branch, add to a variable that keeps track of the sum of the subset represented by the node. When you move back on an x = 1 branch, subtract. Moving in either direction along an x = 0 branch requires no add/subtract. When you reach a node with the desired sum, terminate. When you reach a node whose sum exceeds the desired sum, backtrack; do not move into this nodes subtrees. When you make a right child move see if the desired sum is attainable by adding in all remaining integers; for this keep another variable that gives you the sum of the remaining integers.8BACKTRACKING DEPTH-FIRST SEARCHx1=1x1= 0x2=1 x2= 0x2=1x2= 09BACKTRACKING DEPTH-FIRST SEARCHx1=1x1= 0x2=1 x2= 0x2=1x2= 010BACKTRACKING DEPTH-FIRST SEARCHx1=1x1= 0x2=1 x2= 0x2=1x2= 011BACKTRACKING DEPTH-FIRST SEARCHx1=1x1= 0x2=1 x2= 0x2=1x2= 012BACKTRACKING DEPTH-FIRST SEARCHx1=1x1= 0x2=1 x2= 0x2=1x2= 013BACKTRACKING DEPTH-FIRST SEARCHx1=1x1= 0x2=1 x2= 0x2=1x2= 014EXAMPLEExample of the use Branch and Bound & backtracking is Puzzles!For such problems, solutions are at different levels of the treehttp://www.hbmeyer.de/backtrack/backtren.htm151 2 3 45 6 7 89 10 11 1213 14 151324561314151211 109 78TOPICS COVERED ARE:Branch and boundBacktrackingDivide and conquerGreedy Methods Short paths algorithms16DIVIDE AND CONQUERdivide and conquer (D&C) is an important algorithm design paradigm based on multi-branched recursion. The algorithm works by recursively breaking down a problem into two or more sub-problems of the same (or related) type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.This technique


View Full Document
Download PARALLEL ALGORITHMS IN COMBINATORIAL OPTIMIZATION PROBLEMS
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view PARALLEL ALGORITHMS IN COMBINATORIAL OPTIMIZATION PROBLEMS and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view PARALLEL ALGORITHMS IN COMBINATORIAL OPTIMIZATION PROBLEMS 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?