CS 6260PARALLEL COMPUTATIONPARALLEL ALGORITHMS IN COMBINATORIALOPTIMIZATION PROBLEMSProfessor:Elise De DonckerPresented By:Lina Hussein1TOPICS COVERED ARE: Backtracking Branch and bound Divide and conquerGreedy Methods Greedy Methods  Short paths algorithms2BRANCH AND BOUND Branch and bound (BB) is a general algorithm forfinding optimal solutions of various optimizationproblems, especially in discrete and combinatorialoptimization. It consists of a systematic enumerationof all candidate solutions, where large subsets offruitlesscandidatesarediscardedenmasse(allfruitlesscandidatesarediscardedenmasse(alltogether), by using upper and lower estimated boundsof 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 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 (orsome) solutions to some computational problem, thatincrementally builds candidates to the solutions, andabandons each partial candidate ("backtracks") assoon as it determines that it cannot possibly becompleted to a valid solution.. The Algorithm systematically searches for a solutionto a problem among all available options. It does so byassuming that the solutions are represented by vectors(v1, ..., vi) of values and by traversing in a depth firstmanner the domains of the vectors until the solutionsare found.5BACKTRACKING A systematic way to iterate through all the possibleconfigurations 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 addinganother element at the end. If so, we should count (or print,…) it.Ifnot,checkwhetherpossibleextensionexits.Ifnot,checkwhetherpossibleextensionexits. If so, recur and continue If not, delete vkand try another possibility.ALGORITHM try(v1,...,vi)IF (v1,...,vi) is a solution THEN RETURN (v1,...,vi)FOR each v DOIF (v1,...,vi,v) is acceptable vector THEN sol = try(v1,...,vi,v) IF sol != () THEN RETURN solENDENDRETURN ()6PRUNING SEARCH If Siis the domain of vi, then S1× ... × Smis thesolution space of the problem. The validitycriteria used in checking for acceptable vectorsdetermines what portion of that space needs to besearched, and so it also determines the resourcesrequired by the algorithm. To make a backtracking program efficient enough tosolveinterestingproblems,wemustprunethesolveinterestingproblems,wemustprunethesearch space by terminating for every search paththe instant that is clear not to lead to a solution.7S1S2 S2V1...V2.............................................................BACKTRACKING The traversal of the solution space can be representedby a depth-first traversal of a tree. The tree itself israrely entirely stored by the algorithm in discourse;instead just a path toward a root is stored, to enablethe backtracking. When you move forward on an x =1 branch, add to a variable that keeps track of the sum of the subset 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= 0x=1x= 0x2=1x2= 0x2=1x2= 0x2=1x2= 09BACKTRACKING DEPTH-FIRST SEARCHx1=1x1= 0x=1x= 0x2=1x2= 0x2=1x2= 0x2=1x2= 010BACKTRACKING DEPTH-FIRST SEARCHx1=1x1= 0x=1x= 0x2=1x2= 0x2=1x2= 0x2=1x2= 011BACKTRACKING DEPTH-FIRST SEARCHx1=1x1= 0x=1x= 0x2=1x2= 0x2=1x2= 0x2=1x2= 012BACKTRACKING DEPTH-FIRST SEARCHx1=1x1= 0x=1x= 0x2=1x2= 0x2=1x2= 0x2=1x2= 013BACKTRACKING DEPTH-FIRST SEARCHx1=1x1= 0x=1x= 0x2=1x2= 0x2=1x2= 0x2=1x2= 014EXAMPLE Example of the use Branch and Bound & backtracking is Puzzles!1 2 3 45 6 7 891011121324561314121110 For such problems, solutions are at different levels of the treehttp://www.hbmeyer.de/backtrack/backtren.htm15910111213 14 15561511109 78TOPICS COVERED ARE: Branch and bound Backtracking Divide and conquer Greedy Methods Short paths algorithmsShort paths algorithms16DIVIDE AND CONQUER divide and conquer (D&C) is an important algorithmdesign paradigm based on multi-branched recursion.The algorithm works by recursively breaking down aproblem into two or more sub-problems of the same (orrelated) type, until these become simple enough to besolveddirectly.Thesolutionstothesub-problemsaresolveddirectly.Thesolutionstothesub-problemsarethen combined to give a solution to the originalproblem. This technique is the basis of efficient algorithms forall kinds of problems, such as sorting (e.g., quick sort,merge sort).17ADVANTAGES Solving difficult problems: Divide and conquer is a powerful tool for solvingconceptually difficult problems, such as the classic Tower ofHanoi puzzle: it break the problem into sub-problems, thensolve the trivial cases and combine sub-problems to theoriginal problem. Roundoff controlIncomputationswithroundedarithmetic,e.g.withfloatingIncomputationswithroundedarithmetic,e.g.withfloatingpoint numbers, a D&C algorithm may yield more accurateresults than any equivalent iterative method. Example, one can add N numbers either by a simple loopthat adds each datum to a single variable, or by a D&Calgorithm that breaks the data set into two halves,recursively computes the sum of each half, and then addsthe two sums. While the second method performs the samenumber of additions as the first, and pays the overhead ofthe recursive calls, it is usually more accurate.18IN PARALLELISM... Divide and conquer algorithms are naturallyadapted for execution in