Assignment Problem Algorithm Using Branch And Bound Algorithm

January 21st, 2017, 10:35 AM#1


Job assignment problem solve with Branch and Bound algorithm

I started doing Branch and Bound Algorithm for assignment problem in C++ and i can't find the right solution. First of all assignment problem example:


Ok so each person can be assigned to one job, and the idea is to assign each job to one of the person so that all the jobs are done in the quickest way.

Here is my code so far:

Code:

#include "Matrix.h" // Program to solve Job Assignment problem // using Branch and Bound #include <limits.h> #include <vector> #include <algorithm> using namespace std; template<class T> NUM getCost(Matrix& matrix, size_t x, size_t y, vector<bool>& colUsed); void run(Matrix& matrix, vector<size_t>& assignedJobs); int main() { Matrix matrix; matrix.setMatrix(N); matrix.print(); vector<size_t> assignedJobs; run(matrix, assignedJobs); cout << assignedJobs[0]; /* cout << "size:E " << v.size() << endl; for (vector<NUM>::iterator i = v.begin(); i != v.end(); i++) { cout << *i << endl; } */ return 0; } // remember to use x only LOCALLY!!! NUM getCost(Matrix& matrix, size_t x, size_t y, vector<bool>& colUsed) { // pathCost NUM pathCost = matrix.matrix[x++][y]; for (size_t col = 0; col < matrix.size(); col++) { if (!colUsed.at(col)) { NUM min = #if defined NUM_INT INT_MAX; #endif #if defined NUM_DBL DBL_MAX; #endif size_t row = x; for (; row < matrix.size(); row++) { if (min > matrix.matrix[row][col]) { min = matrix.matrix[row][col]; } } pathCost += min; } } return pathCost; } void run(Matrix& matrix, vector<size_t>& assignedJobs) { // array of used columns vector<bool> colUsed; for (size_t i = 0; i < matrix.size(); i++) { colUsed.push_back(false); } for (size_t row = 0; row < matrix.size(); row++) { size_t col = 0; // bombona while (colUsed.at(col++)); col--; // choose the best job for the current worker vector<NUM> jobs; // get all the job costs from which to choose the smallest // row++ jobs.push_back(getCost(matrix, col, row, colUsed)); // iterator at the position of the smallest element of jobs vector<NUM>::iterator i_min = min_element(jobs.begin(), jobs.end()); // index of the smallest element in jobs size_t index = (size_t)distance(jobs.begin(), i_min); colUsed.at(index) = true; assignedJobs.push_back(index); } }
I know i might be out of track. I didn't use lower bound in the beginning, i'm actually a little confused how this algorithm exactly works. So even step by step walktrough through the algorithm would be helpful.

Branch and Bound

I. Introduction

II. Illustration on the Job Assignment Problem

III. The General Branch and Bound Algorithm

IV. Criteria for the Choice of Approximate Cost Functions

V. Implementation of the B&B Job Assignment Algorithm

I. Introduction

  • Branch and bound is a systematic method for solving optimization problems
  • B&B is a rather general optimization technique that applies where the greedy method and dynamic programming fail.
  • However, it is much slower. Indeed, it often leads to exponential time complexities in the worst case.
  • On the other hand, if applied carefully, it can lead to algorithms that run reasonably fast on average.
  • The general idea of B&B is a BFS-like search for the optimal solution, but not all nodes get expanded (i.e., their children generated). Rather, a carefully selected criterion determines which node to expand and when, and another criterion tells the algorithm when an optimal solution has been found.
Back to Top

II. Illustration on the Job Assignment Problem

  • Input: n jobs, n employees, and an n x n matrix A where Aij be the cost if person i performs job j.
  • Problem: find a one-to-one matching of the n employees to the n jobs so that the total cost is minimized.
  • formally, find a permutation f such that C(f), where
    C(f)=A1f(1) + A2f(2) + ... + Anf(n)
    is minimized.
  • A brute-force method would generate the whole solution tree, where every path from the root to any leaf is a solution, then evaluate the C of each solution, and finally choose the path with the minimum cost.
  • Illustration on this specific instance of the job-assignment problem:
  • In informal terms, the problem is to choose a single number from each row such that (1) no two numbers are chosen from the same columns, and (2) the sum of the chosen numbers is minimized.
  • The brute force method:
  • The first idea of B&B is to develop "a predictor" of the likelihood (in a loose sense) of a node in the solution tree that it will lead to an optimal solution. This predictor is quantitative.
  • With such a predictor, the B&B works as follows:
    1. Which node to expand next: B&B chooses the live node with the best predictor value
    2. B&B simply expands that node (i.e., generate all its children)
    3. the predictor value of each newly generated node is computed, the just expanded node is now designated as a dead node, and the newly generated nodes are designated as live nodes.
    4. Termination criterion: When the best node chosen for expansion turn out to be a final leaf (i.e., at level n), that when the algorithm terminates, and that node corresponds to the optimal solution. The proof of optimality will be presented later on.
  • What could that predictor be?
  • In the case of minimization problem, one candidate predictor of any node is the cost so far . That is, each node corresponds to (partial) solution (from the root to that node). The cost-so-far predictor is the cost of the partial solution.
  • Apply this preliminary algorithm on the above specific instance of the job assignment problem
  • A better predictor for the job assignment problem is:
    (cost so far) + (sum of the minimums of the remaining rows)
  • Apply B&B with the new predictor to the same instance of the job assignment problem
  • A yet another predictor is
    cost so far + sumni=k+1p i
    where p i is the minimum value in row i of the cost matrix A, such that p is not in the column of any of the terms chosen in the partial solution so far.
  • Apply B&B with the last predictor to the same instance of the job assignment problem
Back to Top

The General Branch and Bound Algorithm

  • Each solution is assumed to be expressible as an array X[1:n] (as was seen in Backtracking).
  • A predictor, called an approximate cost function CC, is assumed to have been defined.
  • Definitions:
    • A live node is a node that has not been expanded
    • A dead node is a node that has been expanded
    • The expanded node (or E-node for short) is the live node with the best CC value.
  • The general B&B algorithm follows:

Procedure B&B() begin E: nodepointer; E := new(node); -- this is the root node which -- is the dummy start node H: heap; -- A heap for all the live nodes -- H is a min-heap for minimization problems, -- and a max-heap for maximization problems. while (true) do if (E is a final leaf) then -- E is an optimal solution print out the path from E to the root; return; endif Expand(E); if (H is empty) then report that there is no solution; return; endif E := delete-top(H); endwhileend

Procedure Expand(E) begin - Generate all the children of E; - Compute the approximate cost value CC of each child; - Insert each child into the heap H; end
Back to Top

IV. Criteria for the Choice of Approximate Cost Functions

  • Definition of the cost function C: For every node X in the solution tree, the cost function C(X) is the cost of the best solution that goes through node X.
  • Theorem: In the case of minimization problems, if CC(X) <= C(X) for every node X, and if CC(X)=C(X) for every final leaf node X, then the first expanding node (best-CC node) that happens to be a final leaf corresponds to an optimal solution.
  • Proof:
    • Let E be the E-node that happens to be a final leaf.
    • Need to prove that C(E) <= C(X) for any live node X.
    • C(E)=CC(E) because E is a final leaf
    • CC(E) <= CC(X) for any live node X, because E is the expanding node, that is, the minimum-CC node
    • CC(X) <= C(X) by assumption.
    • Therefore, C(E)=CC(E)<=CC(X) <=C(X), leading to C(E)<=C(X). Q.E.D.
  • Therefore, the criteria for the approximate cost function CC for minimization problems are:
    1. CC(X) <= C(X) for all live nodes X
    2. CC(X)=C(X) for all final leaves.
  • The criteria for the approximate cost function CC for maximization problems are:
    1. CC(X) >= C(X) for all live nodes X
    2. CC(X)=C(X) for all final leaves.
  • Because of those criteria, CC is called an underestimate of C (in the case of minimization), and an overestimate of C (in the case of maximization)
  • The closer CC is to C, the faster is the algorithm in reaching an optimal solution.
Back to Top

V. Implementation of the B&B Job Assignment Algorithm

  • We need to define the full record of a node
  • We need to fully implement the Expand procedure
  • Every node corresponds to something like X[i]=j, which signifies that the job X[i] assigned to person i is j.
  • every node must store its CC value.
  • each node must point to its parent so that when an optimal leaf is generated, the path from that leaf to the root can be traced and printed out as the optimal solution.
  • Therefore, a node record structure should look like: Record node Begin Parent: nodepointer; I: integer; -- person I J: integer; -- Job J is assigned to person I CC: real; End
  • Take the 2nd CC formula:
    CC(X at level k) = cost so far + sumni=k+1mi
    where mi is the minimum of row i.
  • observe that if X is a pointer to a node, then
    X->CC = X->Parent->CC + AX->I,A->J - mX->I
  • Write a piece of code that computes the mis for i=1,2,...,n
  • Code for Expand(E):
    Procedure Expand(E) begin /* Generate all the children of E; */ I := E->I; X,p: nodepointer; S[1:n]: Boolean; /* S is a bitmap set initialized to 0*/ /* S will contain all the jobs that have been assigned by the partial path from the root to E */ p := E; while (p is not the root) do S[p->J] := 1; p := p-> Parent; endwhilefor job=1 to n doif S[job] = 0 then X := new(node); X->I := I + 1; X->J := job; X->Parent := E; X->CC := E->CC + AX->I,X->J-mX->I; Insert(X,H); endifendforend
Back to Top

Exercise: The 0/1 knapsack problem is the same as the regular knapsack problem except that one cannot take a fraction of any item: either the whole item is taken, or nothing of that item is taken. Develop a B&B algorithm for the 0/1 knapsack problem.

Hint: take CC(X) to be

the cost so far + the regular knapsack solution for the remaining items.
Show that this approximate cost function CC meets the criteria.

0 comments

Leave a Reply

Your email address will not be published. Required fields are marked *