Misplaced Pages

#954045

32-490: PM2 is an open-source distributed multithreaded programming environment designed to support efficiently distributed programs with a highly irregular behavior (e.g. branch and bound search, computation on sparse matrices , etc.) on distributed architectures. It is distributed under the GPL . PM2 adheres to the SPMD ( Single Program Multiple Data ) programming model, in a way very similar to

64-403: A priority queue that sorts nodes on their lower bound. Examples of best-first search algorithms with this premise are Dijkstra's algorithm and its descendant A* search . The depth-first variant is recommended when no good heuristic is available for producing an initial solution, because it quickly produces full solutions, and therefore upper bounds. A C++ -like pseudocode implementation of

96-427: A base of various heuristics . For example, one may wish to stop branching when the gap between the upper and lower bounds becomes smaller than a certain threshold. This is used when the solution is "good enough for practical purposes" and can greatly reduce the computations required. This type of solution is particularly applicable when the cost function used is noisy or is the result of statistical estimates and so

128-470: A bounding function bound , that computes lower bounds of f on nodes of the search tree, as well as a problem-specific branching rule. As such, the generic algorithm presented here is a higher-order function . Several different queue data structures can be used. This FIFO queue -based implementation yields a breadth-first search . A stack (LIFO queue) will yield a depth-first algorithm. A best-first branch and bound algorithm can be obtained by using

160-555: A central role in the life of Marcel Proust . PM2 features an additional functionality to provide threads with a uniform access to data, whatever their physical location. It is called DSM-PM2. PM2 runs on most Unix platforms. PM2 is developed at LaBRI (Laboratoire Bordelais de Recherche en Informatique), a research laboratory located in Bordeaux, France, jointly supported by the INRIA, the CNRS, and

192-448: A computational problem H is called NP-hard if, for every problem L which can be solved in non-deterministic polynomial-time , there is a polynomial-time reduction from L to H . That is, assuming a solution for H takes 1 unit time, H ' s solution can be used to solve L in polynomial time. As a consequence, finding a polynomial time algorithm to solve a single NP-hard problem would give polynomial time algorithms for all

224-421: A different level. All NP-complete problems are also NP-hard (see List of NP-complete problems ). For example, the optimization problem of finding the least-cost cyclic route through all nodes of a weighted graph—commonly known as the travelling salesman problem —is NP-hard. The subset sum problem is another example: given a set of integers, does any non-empty subset of them add up to zero? That

256-423: A representation is called an instance of the problem. Denote the set of candidate solutions of an instance I by S I . The instance representation has to come with three operations: Using these operations, a B&B algorithm performs a top-down recursive search through the tree of instances formed by the branch operation. Upon visiting an instance I , it checks whether bound( I ) is equal or greater than

288-595: A value of 276.667. We test the other endpoints by sweeping the line over the region and find this is the maximum over the reals. We choose the variable with the maximum fractional part, in this case x 2 {\displaystyle x_{2}} becomes the parameter for the branch and bound method. We branch to x 2 ≤ 26 {\displaystyle x_{2}\leq 26} and obtain 276 @ ⟨ 24 , 26 ⟩ {\displaystyle \langle 24,26\rangle } . We have reached an integer solution so we move to

320-453: Is NP-hard when for every problem L in NP, there is a polynomial-time many-one reduction from L to H . Another definition is to require that there be a polynomial-time reduction from an NP-complete problem G to H . As any problem L in NP reduces in polynomial time to G , L reduces in turn to H in polynomial time so this new definition implies the previous one. It does not restrict

352-452: Is a convex hull region so the solution lies on one of the vertices of the region. We can find the intersection using row reduction, which is [ 70 / 3 80 / 3 ] {\displaystyle {\begin{bmatrix}70/3\\80/3\end{bmatrix}}} , or [ 23.333 26.667 ] {\displaystyle {\begin{bmatrix}23.333\\26.667\end{bmatrix}}} with

SECTION 10

#1732855537955

384-495: Is a decision problem and happens to be NP-complete. There are decision problems that are NP-hard but not NP-complete such as the halting problem . That is the problem which asks "given a program and its input, will it run forever?" That is a yes / no question and so is a decision problem. It is easy to prove that the halting problem is NP-hard but not NP-complete. For example, the Boolean satisfiability problem can be reduced to

416-452: Is a method for solving optimization problems by breaking them down into smaller sub-problems and using a bounding function to eliminate sub-problems that cannot contain the optimal solution. It is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization . A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search :

448-515: Is called the search space, or feasible region . The rest of this section assumes that minimization of f ( x ) is desired; this assumption comes without loss of generality , since one can find the maximum value of f ( x ) by finding the minimum of g ( x ) = − f ( x ) . A B&B algorithm operates according to two principles: Turning these principles into a concrete algorithm for a specific optimization problem requires some kind of data structure that represents sets of candidate solutions. Such

480-1021: Is not known precisely but rather only known to lie within a range of values with a specific probability . Nau et al. present a generalization of branch and bound that also subsumes the A* , B* and alpha-beta search algorithms. Branch and bound can be used to solve this problem Maximize Z = 5 x 1 + 6 x 2 {\displaystyle Z=5x_{1}+6x_{2}} with these constraints x 1 + x 2 ≤ 50 {\displaystyle x_{1}+x_{2}\leq 50} 4 x 1 + 7 x 2 ≤ 280 {\displaystyle 4x_{1}+7x_{2}\leq 280} x 1 , x 2 ≥ 0 {\displaystyle x_{1},x_{2}\geq 0} x 1 {\displaystyle x_{1}} and x 2 {\displaystyle x_{2}} are integers. The first step

512-569: Is primarily designed for medium-size clusters of commodity processing nodes interconnected by high-performance networks, but nothing prevents the use on massively parallel MIMD machines at one end of the spectrum, or as a support for metacomputing over the Internet on the other end. It supports heterogeneous networking configurations, such as sets of interconnected clusters. Distinguishing features of PM2 include its priority driven scheduling policy, its thread migration mechanisms and its ability to ease

544-490: Is to relax the integer constraint. We have two extreme points for the first equation that form a line: [ x 1 x 2 ] = [ 50 0 ] {\displaystyle {\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}={\begin{bmatrix}50\\0\end{bmatrix}}} and [ 0 50 ] {\displaystyle {\begin{bmatrix}0\\50\end{bmatrix}}} . We can form

576-455: The PVM and MPI communication libraries. The user writes a single program text, a copy of which is launched by a specific load command on each processing node of the current configuration. It is up to the programmer to include branching so as to differentiate between the processing nodes. This way it allows a network of heterogeneous machines to be used as a single distributed parallel processor. It

608-491: The C++ programming language. When x {\displaystyle \mathbf {x} } is a vector of R n {\displaystyle \mathbb {R} ^{n}} , branch and bound algorithms can be combined with interval analysis and contractor techniques in order to provide guaranteed enclosures of the global minimum. This approach is used for a number of NP-hard problems: Branch-and-bound may also be

640-647: The University of Bordeaux. Before that, PM2 was developed at LIP (Laboratoire de l'Informatique du Parallélisme), a research laboratory located at the ENS Lyon (Ecole Normale Supérieure de Lyon), France, jointly supported by the INRIA, the CNRS and the University Claude Bernard Lyon. PM2 was originally designed by Raymond Namyst and Jean-François Méhaut at LIFL, University of Lille, France. Branch and bound Branch and bound ( BB , B&B , or BnB )

672-408: The above is: In the above pseudocode, the functions heuristic_solve and populate_candidates called as subroutines must be provided as applicable to the problem. The functions f ( objective_function ) and bound ( lower_bound_function ) are treated as function objects as written, and could correspond to lambda expressions , function pointers and other types of callable objects in

SECTION 20

#1732855537955

704-513: The best one found so far by the algorithm. The algorithm depends on efficient estimation of the lower and upper bounds of regions/branches of the search space. If no bounds are available, the algorithm degenerates to an exhaustive search. The method was first proposed by Ailsa Land and Alison Doig whilst carrying out research at the London School of Economics sponsored by British Petroleum in 1960 for discrete programming , and has become

736-568: The class NP-hard to decision problems, and it also includes search problems or optimization problems . If P ≠ NP, then NP-hard problems could not be solved in polynomial time. Some NP-hard optimization problems can be polynomial-time approximated up to some constant approximation ratio (in particular, those in APX ) or even up to any approximation ratio (those in PTAS or FPTAS ). There are many classes of approximability, each one enabling approximation up to

768-432: The current upper bound; if so, I may be safely discarded from the search and the recursion stops. This pruning step is usually implemented by maintaining a global variable that records the minimum upper bound seen among all instances examined so far. The following is the skeleton of a generic branch and bound algorithm for minimizing an arbitrary objective function f . To obtain an actual algorithm from this, one requires

800-433: The development of various load balancing policies. It can manage several hundreds of threads on each available physical processor. The PM2 interface provides functionalities for the management of this high degree of parallelism and for dynamic load balancing. The thread management subsystem of PM2 is called Marcel (named after Marcel Proust ) and its communication subsystem Madeleine , a French sweet that supposedly played

832-554: The halting problem by transforming it to the description of a Turing machine that tries all truth value assignments and when it finds one that satisfies the formula it halts and otherwise it goes into an infinite loop. It is also easy to see that the halting problem is not in NP since all problems in NP are decidable in a finite number of operations, but the halting problem, in general, is undecidable . There are also NP-hard problems that are neither NP-complete nor Undecidable . For instance,

864-429: The most commonly used tool for solving NP-hard optimization problems. The name "branch and bound" first occurred in the work of Little et al. on the traveling salesman problem . The goal of a branch-and-bound algorithm is to find a value x that maximizes or minimizes the value of a real-valued function f ( x ) , called an objective function, among some set S of admissible, or candidate solutions . The set S

896-431: The other branch x 1 ≥ 23 {\displaystyle x_{1}\geq 23} and there are no feasible solutions. Therefore, the maximum is 276 with x 1 ⟼ 24 {\displaystyle x_{1}\longmapsto 24} and x 2 ⟼ 26 {\displaystyle x_{2}\longmapsto 26} . NP-hard In computational complexity theory ,

928-564: The other branch x 2 ≥ 27 {\displaystyle x_{2}\geq 27} . We obtain 275.75 @ ⟨ 22.75 , 27 ⟩ {\displaystyle \langle 22.75,27\rangle } . We have a decimal so we branch x 1 {\displaystyle x_{1}} to x 1 ≤ 22 {\displaystyle x_{1}\leq 22} and we find 274.571 @ ⟨ 22 , 27.4286 ⟩ {\displaystyle \langle 22,27.4286\rangle } . We try

960-562: The problems in the complexity class NP . As it is suspected, but unproven, that P≠NP , it is unlikely that any polynomial-time algorithms for NP-hard problems exist. A simple example of an NP-hard problem is the subset sum problem . Informally, if H is NP-hard, then it is at least as difficult to solve as the problems in NP . However, the opposite direction is not true: some problems are undecidable , and therefore even more difficult to solve than all problems in NP, but they are probably not NP-hard (unless P=NP). A decision problem H

992-441: The second line with the vector points [ 0 40 ] {\displaystyle {\begin{bmatrix}0\\40\end{bmatrix}}} and [ 70 0 ] {\displaystyle {\begin{bmatrix}70\\0\end{bmatrix}}} . The third point is [ 0 0 ] {\displaystyle {\begin{bmatrix}0\\0\end{bmatrix}}} . This

PM2 - Misplaced Pages Continue

1024-402: The set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than

#954045