A Janet Branch & Bound Framework

Introduction

A branch-and-bound algorithm seeks an optimum solution from among a set of feasible solutions. The set of feasible solutions are not given. They can be generated from the problem description. However, doing so usually is computationally infeasible: The number of feasible solutions typically grows exponentially as a function of the size of the problem input. (Please see Papadimitriou at al. for a general discussion of the branch and bound method of combinatorial optimization.) For example, the set of feasible tours in a Traveling Salesman Problem (TSP) of a complete graph with 23 nodes is 22! or around 1.6 X 10¹⁵ tours. The space of feasible solutions is progressively partitioned (branching), forming a search tree. Each node has a partial feasible solution. The node in the search tree represents the set of feasible solutions that are extensions of its partial solution. As branching continues (progresses down the problem tree), each search node has a more complete partial solution, and thus represents a smaller set of feasible solutions. For example, when casting the TSP as a branch-and-bound problem, a search node has a partial tour, and represents the set of all tours containing that partial tour. As one progresses down the search tree, the each node represents a larger partial tour. As the size of a partial tour increases, the number of full tours containing the partial tour clearly decreases.

In traversing the search tree, we may come to a node that represents a set of feasible solutions, all of which are provably more costly than a feasible solution already found. When this occurs, we prune (aka kill) this search node: We discontinue further exploration of this set of feasible solutions. This is the bound part of the branch and bound method of combinatorial optimization. In the example of the TSP problem, the cost of any feasible tour that has a given partial tour can be bounded from below by the cost of the partial tour: the sum of the edge weights for the edges in the partial tour. (Stronger, albeit more computationally complex, lower bounds are known.)

Here is a sequential algorithm for branch and bound, taken from Papadimitriou et al.

{
    activeSet = { originalTask };
    u = infinity; // u = the cost of the best solution known
    currenBest = null;
    while ( ! activeSet.isEmpty() )
    {
        k = remove some element of the activeSet;
        children = generate k's children; // sub-nodes of k
        for each element of children
        {
            if ( element's lower bound <= u )
            {
                if ( element is a complete solution )
                {
                    u = element's cost;
                    currentBest = element;
                }
                else
                {
                    add element to activeSet;
                }
            }
        }
    }
}

We design tasks to correspond to nodes in the search tree: Each task gives rise to a set of smaller subtasks, until it represents a node in the search tree that is small enough to be explored by a single host. We refer to such a task as atomic; it does not produce subtasks.

Explicit prefetch

One could programmatically define atomic tasks as those whose corresponding search sub-trees are of a fixed height, k, possibly a function of the problem search tree's height. In the TSP case, such an atomic task represents no more than k! feasible tours. For example, in an 18-node input graph, if k = 11, there is 17!/11! or about 9 million atomic tasks, each of which represents 11! or about 40 million tours! Although an atomic task is computed on a single host, the number of tours that actually need to be explored depends on how much of the task's corresponding search sub-tree can be pruned (aka killed), which depends on the problem instance. Consequently, the number of tours to be examined within an atomic task, in this example, can vary from 0 to about 40 million! Having atomic tasks whose computational load is so variable makes high speedups problematic, when deploying on a large number of hosts.

We cannot have k be a function of the number of hosts available within the hosting service provider; in adaptively parallel computing, this number varies at execution time. Global properties of a truly distributed system are not accessible in real time. Besides, even if we know how many hosts are available at any instant in time, we do not know the statistics about how long a host will remain associated with the HSP. So, we do not know how big of a task we may safely give it. Neither can we reduce the maximum variation in the atomic task's computation load by simply reducing k; this substantially increases the number of tasks. The overhead of managing a large number of tasks becomes prohibitive. For example, reducing k from 11 to 5 in an 18-node graph increases the number of tasks from 40 million to almost 14 billion! (Please see Neary et al. for a fuller discussion of this problem and its solution.)

We thus are motivated to vary the atomic threshold at execution time. Accordingly, our branch and bound task does not extend Atomic (implicit task prefetching). Instead, we defer until execution time the decision as to whether or not a task is atomic. When atomicity is established, the branch and bound task invokes the Environment method fetchTask, which initiates a non-blocking task request on the host's taskserver (to overlap the computation of this atomic task with the fetching of the next task). When the task is not atomic, Janet automaticlly caches one of its constructed subtasks.

The Shared object

Sometimes you want all tasks to have access to a common set of data that tasks can modify during the course of the computation. In computations distributed over the Internet in which performance is a prime goal, it would be inappropriate to provide shared objects in the conventional sense. Janet however provides a weaker form of sharing that is compatible with high performance: An Object that is shared among all a computation's tasks, and whose value, when changed by any task, is propagated with best effort to all other tasks. This limited sharing is of limited value. However, branch and bound search is an important combinatorial optimization technique that can make good use of this kind of sharing.

The cost of the best known solution at any point in time is shared among the tasks. In branch and bound, this value is used to decide if a particular subtree of the search tree can be pruned (bounded). Thus, sharing the cost of the best known solution enhances the pruning ability of concurrently executing tasks that are exploring disjoint parts of the search tree. Indeed, this improvement in pruning is essential to the efficiency of parallel branch and bound.

When a branch and bound task finds a complete solution whose cost is less than the current best, we propagate the new cost throughout the hosting service provider. To do this, we encapsulate the best known cost as the branch and bound computation's shared object. Please see IntUpperBound below.

The classes comprising the framework

The Janet branch and bound framework is based on 2 assumptions:

The branch and bound problem is formulated as a minimization problem. Maximization problems typically can be reformulated as minimization problems.
The cost can be represented as in int.

Should these 2 assumptions prove troublesome, I will generalize this framework.

The actual classes that comprise the framework are given below:

BranchAndBound: This is a Task class, which resides in the janet.applications.branchandbound package, whose objects represent a search node. A BranchAndBound Task either:
IntUpperBound: A Shared object that represents the minimum cost among all known complete solutions. This class is in the janet.services.shared package. It implements the Shared interface (for details about this interface, please see the API), which defines the shared object. In this case, the shared object is an Integer that holds the current upper bound on the cost of a minimal solution. Consequently, IntUpperBoundu is newer than IntUpperBound v when u < v.
MinSolution

This task is included in the janet.services.tasks package. It is a composition class whose execute method:

receives an array of Solution objects, some of which may be null;
returns the one whose cost is minimum, provided it is less than or equal to the known best solution. Equality is included to ensure that the best solution is reported: It is not enough just to know the cost of the minimum solution.
From the standpoint of the Janet system (not a consideration for application programming), the compose tasks form a tree that performs a gather operation, which, in this case, is a min operation on the cost of the Solution objects it receives. Each task in this gather tree is assigned to some taskserver, distributing the gather operation throughout the HSP. (Yes, this task is executed on a TaskServer, not a Host - see a new Section describing Task classes that are executed on the TaskServer.)
It needs no constructor.

Q: A LinkedList of Solution objects.
Solution: A solution interface that is implemented for each class of problem (e.g., TSP).

The Traveling salesman problem (TSP), given later in the tutorial, illustrates the use of this framework.

Postscript

Although not an aspect of Janet programming, it is worth noting that, in the Janet branch and bound framework, termination detection is as distributed as the non-uniform exploration of the search tree.