Branch and Bound API

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:

The next figure show the architecture of the API:

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:

Finally, the methods order execution:

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.

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 .