back to API     back to index     prev     next  
ProActive Logo

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

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:

Further research information is available here.

The Model Architecture

The next figure show the architecture of the API:

Architecture

The API architecture.

The API active objects are:

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 solution

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.

The API Details

The Task Description

The Task object is located in this followed package:

org.objectweb.proactive.branchnbound.core

All abstract methods are described bellow:

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.

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.

public void initLowerBound()

Initialize a lower bound local to the task.

public void initUpperBound()

Initialize a upper bound local to the task.

public Result gather(Result[] results)

This one is not abstract but it is strongly recommended to override it. 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.

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:

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

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.

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.branchnbound.core.Result;
import org.objectweb.proactive.branchnbound.core.Task;
import org.objectweb.proactive.branchnbound.core.exception.NoResultsException;

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).permutation;
        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) ProActive.getStubOnThis()).split());
  }
        
        // ...
        
  r.setSolution(bestKnownSolution);
  return r;
}

This example is available in a complete version here.

Future Work


Copyright © November 2005 INRIA All Rights Reserved.