Branch and Bound API

The outline of this short handbook:

  1. Overview

  2. The API Architecture

  3. The API Description

  4. An Example: FlowShop

  5. Future Work

44.1. Overview

The Branch and Bound (BnB) consists to an algorithmic technique for exploring a solution tree from which returns the optimal solution.

The main goal of this BnB API is to provide a set of tools for helping the developpers to parallelize his BnB problem implementation.

The main features are:

  • Hidding computation distribution.

  • Dynamic task splitting.

  • Automatic solution gathering.

  • Task communications for broadcasting best current solution.

  • Different behaviors for task allocation, provided by the API or yourself.

  • Open API for extensions.

44.2. The Model Architecture

The next figure show the architecture of the API:

The API architecture.

Figure 44.1. The API architecture.


The API active objects are:

  • Manager : the main point of the API. It is the master for deploying and managing Workers. Also, it attributes Tasks to free workers. The Tasks are provided the Task Queue.

  • Task Queue : provides Task in a specific order to the Manager.

  • Worker : broadcasts solution to all Task, and provides the API environment to the Tasks.

  • Task : the user code to compute.

All Workers have a group reference on all the others. The next figure show step by step how a Task can share a new better solution with all:

Broadcasting a new solution.

Figure 44.2. Broadcasting a new solution.


Finally, the methods order execution:

  1. rootTask.initLowerBound(); // compute a first lower bound

  2. rootTask.initUpperBound(); // compute a first upper bound

  3. Vector splitted = rootTask.split(); // generate a set of tasks

  4. for i in splitted do in parallel

    splitted[i].initLowerBound();

    splitted[i].initUpperBound();

    Result ri = splitted.execute()

  5. Result final = rootTask.gather(Result[] ri); // gathering all result

Keep in mind that is only 'initLower/UpperBound' and 'split' methods are called on the root task. The 'execute' method is called on the root task's splitted task.

44.3. The API Details

44.3.1. The Task Description

The Task object is located in this followed package:

org.objectweb.proactive.extra.branchnbound.core

All methods are described bellow:

44.3.1.1. public Result execute()

It is the place where the user has to put his code for solving a part and/or the totality of his BnB problem. There are 2 main usages of it. The first one consists to divide the task and returning no result. The second is to try to improve the best solution.

44.3.1.2. public Vector split()

This is for helping the user when he wants to divide a task. In a future work we have planned to use this method in an automatic way.

44.3.1.3. public void initLowerBound()

Initialize a lower bound local to the task.

44.3.1.4. public void initUpperBound()

Initialize a upper bound local to the task.

44.3.1.5. public Result gather(Result[] results)

The default behavior is to return the smallest Result gave by the compareTo method. That's why it is also recommended to override the compareTo(Object) method.

Some class variables are provided by the API to help the user for keeping a code clear. See next their descriptions:

protected Result initLowerBound; // to store the lower bound
protected Result initUpperBound; // to store the upper bound
protected Object bestKnownSolution; // setted automaticaly by the API with the best current
 solution
protected Worker worker; // to interact with the API (see after)

From the Task, specialy within the execute() method, the user has to interact with the API for sending sub-tasks, which result from a split call, to the task queue, or broadcasting to other tasks a new better solution, etc.

The way to do that is to use the class variable: worker .

  • Broadcasting a new better solution to all the other class:

    this.worker.setBestCurrentResult(newBetterSolution);
    
  • Sending a set of sub-tasks for computing:

    this.worker.sendSubTasksToTheManager(subTaskList);
    
  • For a smarter split, checking that the task queue needs more tasks:

    BooleanWrapper workersAvailable = this.worker.isHungry();
    

44.3.2. The Task Queue Description

This manages the task allocation. The main functions are: providing tasks in a sepcial order, and keeping results back.

For the moment, there are 2 different queue types provided by the API:

  • BasicQueueImpl : provides tasks in FIFO order.

  • LargerQueueImpl : provides tasks in a larger order, as Breadth First Search algorithm.

By extending the TaskQueue you can use a specialized task allocator for your need.

44.3.3. The ProActiveBranchNBound Description

Finally, it is the main entry point for starting, and controlling your computation.

Task task = new YourTask(someArguments);
Manager manager =  ProActiveBranchNBound.newBnB(task,
                        nodes,
                        LargerQueueImpl.class.getName());
Result futureResult = manager.start(); // this call is asynchronous

Tip: use the constructor ProActiveBranchNBound.newBnB(Task, VirtualNode[], String) and do not activate virtual nodes. This method provides a faster deployment and active objects creation way. Communications between workers are also optimized by a hierarchic group based on the array of virtual nodes. That means when it is possible define a virtual node by clusters.

44.4. An Example: FlowShop

This example solves the permutation flowshop scheduling problem, with the monoobjective case. The main objective is to minimized the overall completion time for all the jobs, i.e. makespan. A flowshop problem can be represented as a set of n jobs; this jobs have to scheduled on a set of m machines. Each jobs is defined by a set of m distinct operations. The goal consists to determine the sequence used for all machines to execute operations.

The algorithm used to find the best solution, tests all permutations and try to cut bad branches.

Firstly, the Flowshop Task :

import org.objectweb.proactive.ProActive;
import org.objectweb.proactive.extra.branchnbound.core.Result;
import org.objectweb.proactive.extra.branchnbound.core.Task;
import org.objectweb.proactive.extra.branchnbound.core.exception.NoResultsExcepti\
on;
public class FlowShopTask extends Task {
 public FlowShopTask() {
   // the empty no args constructor for ProActive
 }
 /**
  * Contruct a Task which search solution for all permutations to the
  * Flowshop problem. Use it to create the root Task.
  */
 public FlowShopTask(FlowShop fs) {
   this.flowshopProblem = fs;
 }
}

Now, implement all Task abstract methods.

Computation bound methods:

            // Compute the lower bound public void initLowerBound() {
            this.lowerBound = this.computeLowerBound(this.fs); } //
            Compute the upper bound public void initUpperBound() {
            this.upperBound = this.computeUpperBound(this.fs); }
        

The split method:

public Vector split() {
  // Divide the set of permutations in 10 sub-tasks
  int nbTasks = 10;
  Vector tasks = new Vector(nbTasks);
  for (int i = 0 ; i < nbTasks ; i++){
    tasks.add(new FlowShopTask(this, i, nbTasks));
  }
        
  return tasks;
}

Then, the execute method:

public Result execute() {
       
  if (! this.iHaveToSplit()) {
  // Test all permutation
    while((FlowShopTask.nextPerm(currentPerm)) != null) {
        int currentMakespan;
        fsr.makespan = ((FlowShopResult)this.bestKnownSolution).makespan;
        fsr.permutation = ((FlowShopResult)this.bestKnownSolution).permutat\
ion;
        if ((currentMakespan = FlowShopTask.computeConditionalMakespan(
            fs, currentPerm,
            ((FlowShopResult) this.bestKnownSolution).makespan,
            timeMachine)) < 0) {
        //bad branch
          int n = currentPerm.length + currentMakespan;
          FlowShopTask.jumpPerm(currentPerm, n, tmpPerm[n]);
          // ...
       } else {
         // better branch than previous best
         fsr.makespan = currentMakespan;
         System.arraycopy(currentPerm, 0, fsr.permutation, 0,
                            currentPerm.length);
         r.setSolution(fsr);
         this.worker.setBestCurrentResult(r);
       } 
    }
  } else {
  // Using the Stub for an asynchronous call
    this.worker.sendSubTasksToTheManager(
      ((FlowShopTask) PAActiveObject.getStubOnThis()).split());
  }
        
        // ...
        
  r.setSolution(bestKnownSolution);
  return r;
}

This example is available in a complete version here .

44.5. Future Work

  • An auto-dynamic task splitting mechanism.

  • Providing more queues for task allocation.

  • A new task interface for wrapping native code.