Back to SYMPHONY Home Page
Because of the clear partitioning of work that occurs when the branching operation generates new subproblems, branch and bound algorithms lend themselves particularly well to parallelization. As a result, there is already a significant body of research on performing branch and bound in parallel environments. For a survey of parallel branch and bound algorithms, see the article by Gendron and Crainic [10].
We first define some terms. A processor, or serial processor, refers to a single serial computing device. A parallel processor or parallel machine consists of multiple serial processors which are connected by efficient communication pathways. There are two types of parallel processors, synchronous and asynchronous. In a synchronous model of computation, the individual processors use a common central clock and hence can synchronize easily. We consider an asynchronous model, in which the individual processors run independently and can only synchronize with each other through explicit communication. The memory of the parallel machine can be either shared or distributed. In shared memory, all processors read from and write to a common memory space. We will use a distributed memory model in which each processor only has access to its own memory space. A process will refer to a single computer program executing commands serially on a single processor. A process can be started directly by the user or by another process. In the second case, we say the first process spawns the second process. The method by which processes communicate with each other is called the communication protocol. We use a message passing protocol in which the processes communicate by explicitly sending messages to each other. A message has a data array, a message tag, a sender, and one or more receivers associated with it. When one process sends a message to another, the second process must explicitly receive that message and know the structure of the message by looking at the message tag.
In parallel branch and cut, there are two major sources of parallelism. First, it is clear that any number of subproblems on the current candidate list can be processed simultaneously. Once a subproblem has been added to the list, it can be properly processed before, during, or after the processing of any other subproblem. This is not to say that processing a particular node at a different point in the algorithm won't produce different results--it most certainly will--but the algorithm will terminate correctly in any case.
The second major source of parallelism is to parallelize the processing of individual subproblems. By allowing separation to be performed in parallel with the solution of the linear programs, we can theoretically process a node in little more than the amount of time it takes to solve the sequence of LP relaxations. Most parallel implementations (including ours) employ a master-slave model, in which there is a central manager responsible for partitioning the work and parceling it out to the various slave processes, which perform the actual computation. The computation divides naturally into five different process types, which interact with each other through message-passing. In the next few sections, we introduce each of these five classes of processes and summarize their basic functions. In Sections 4 and 5, we will discuss the implementation of each process in more detail.