Assignment Problem Solve by Hungarian Method with Algorithm and solution in c++

Assignment Problem Solve by Hungarian Method with Algorithm and solution in c++

Here i have post Assignment problem solved by Hungarian Method  with algorithm, example and program written in c++

Hungarian Method Algorithm:

Step 1: develop the cost table from the give problem

     If no of rows does not equal to the no of columns and vise a versa, then a dummy row or column    must be added. The assignment cost for a dummy cells are 0.

Step 2: find the opportunity cost table;

1. . Locate the smallest element in each row of the given cost table and then subtract that from each element of the rows. 
2.  In the reduced matrix obtain from 2.1. locate the smallest element in  each columns and then subtract that from each element of that column each row and column now have at least one zero value

Step 3: make assignment in the opportunity cost matrix

1. Examine rows successively until a row with exactly one unmarked zero is obtained make an assignment to this single zero by making a square around it.
2. For each zero value that becomes assigned eliminate(X) strike off all other zero in the same row and/or column.
3.  Repeat step 3.1. and 3.2. for column also with exactly single zero value cell that has not been assigned or eliminated.
4.  If a row and/or columns has two or more unmarked zeros and one can not be chosen by inspection, then choose the assigned zero cell arbitrarily.
5.  Continue this process until all zeros in row/columns are either enclosed(assigned) or strike off(X).

Step 4: optimality criterion

• If the number of assignment cell is equal to the no. of row/columns then it is an optimal solution the total cost associated with this solution is obtained by adding original cost figure in the occupied cells
• If a zero cell was chosen arbitrarily in step 3 there exists an alternative optimal solution but if no optimal solution is found then go to step 5.

Step 5: revise the opportunity cost table

Draw a set of horizontal and vertical lines to cover all the zeros in the revised cost obtained from step3 by using the following procedure.

1. For each row in which no allocation was made mark a tick.
2. Examine the marked row, if any zero in tick to the respective columns that contain zero.
3. Examine marked column. If any assigned zero occurs in those columns then tick the respective rows that contain those assigned zero.
4. Repeat this process until no more row or columns can be marked
5. Draw a straight line through each marked column and each unmarked rows

If the no of line drawn is equal to the no. of rows  then the current solution is the optimal solution otherwise go to step 6.

Step 6: develop the new revised opportunity cost table

1. From among the cells not covered by any line, choose the smallest element call this value k.
2. Subtract k from every element in the cell not covered by a line.
3. Add k to every element in the cell covered by the two lines i.e. intersection of two line.
4. Elements in cell covered by one line remain unchanged

Step 7: repeat steps

Repeat step 3 to 6 until an optimal solution is obtained.

Example 

Entered Cost Matrix(3X3):

 Opportunity Cost Matrix for Each Row:

 Opportunity Cost Matrix For Each Row and Column:

Assignment done in Each Row:

After Row Assignment Column Assignment Take place:

Final Answer:

Program Using C++:

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<iomanip.h>
#define MAX 50
enum boolean{FALSE,TRUE};

class HungarianMethod{
    int data[MAX][MAX];
    int allocation[MAX][MAX];
    int no_of_rows,no_of_columns;
    int bal_stat;

    public:
        HungarianMethod(){
            int i,j;
            for(i=0;i<MAX;i++){
                for(j=0;j<MAX;j++){
                    data[i][j]=0;
                    allocation[i][j]=0;
                }
            }
            no_of_rows=no_of_columns=bal_stat=0;
        }
        void setRow(int no){no_of_rows=no;}
        void setColumn(int no){no_of_columns=no;}
        void getData();
        void makeAllocation();
        void display();
        void rowMinima(int [][MAX],int,int);
        void columnMinima(int [][MAX],int,int);
        boolean checkValue(int,int,int [][MAX]);
};
void HungarianMethod::getData(){
    int i,j;
    cout<<"enter cost Metrix :\n";
    for(i=0;i<no_of_rows;i++){
        cout<<"enter "<<i+1<<" row :";
        for(j=0;j<no_of_columns;j++)
            cin>>data[i][j];
    }
}
void copyArray(int startRow,int startCol,int endRow,int endCol,int temp[][MAX],int start1row,int start1col,int ans[][MAX]){
    int i,j,k,l;
    for(i=startRow,k=start1row;i<endRow;i++,k++)
        for(j=startCol,l=start1col;j<endCol;j++,l++)
            ans[k][l]=temp[i][j];
}
int getMinVal(int temp[],int no){
    int min=temp[0];
    for(int i=0;i<no;i++)
        if(min>temp[i])
            min=temp[i];
    return min;
}
int getPosition(int temp[],int no,int value){
    for(int i=0;i<no;i++)
        if(temp[i]==value)
            return i;
    return -1;
}
int countVal(int temp[],int no,int value){
    int i,sum=0;
    for(i=0;i<no;i++)
        if(temp[i]==value)
            sum++;
    return sum;
}
void HungarianMethod::rowMinima(int temp[][MAX],int row,int col){
    int i,j,min;
    for(i=0;i<row;i++){
        min=9999;
        for(j=0;j<col;j++)
            if(min>temp[i][j])
                min=temp[i][j];
        for(j=0;j<col;j++)
            temp[i][j]-=min;
    }
}
void HungarianMethod::columnMinima(int temp[][MAX],int row,int col){
    int i,j,min;
    for(i=0;i<row;i++){
        min=9999;
        for(j=0;j<col;j++)
            if(min>temp[j][i])
                min=temp[j][i];
        for(j=0;j<col;j++)
            temp[j][i]-=min;
    }
}
boolean HungarianMethod::checkValue(int row,int col,int temp[][MAX]){
    int i,j;
    for(i=0;i<row;i++)
        for(j=0;j<col;j++)
            if(temp[i][j]==0)
                return TRUE;
    return FALSE;

}
void HungarianMethod::makeAllocation(){
    int temp_data[MAX][MAX]={0};
    int i,j;
    if(no_of_rows>no_of_columns){
        for(i=0;i<no_of_rows;i++)
            data[i][no_of_columns]=0;
        no_of_columns++;
        bal_stat=1;
    }else if(no_of_rows<no_of_columns){
        for(i=0;i<no_of_columns;i++)
            data[no_of_rows][i]=0;
        no_of_rows++;
        bal_stat=2;
    }
    copyArray(0,0,no_of_rows,no_of_columns,data,0,0,temp_data);
    rowMinima(temp_data,no_of_rows,no_of_columns);
    columnMinima(temp_data,no_of_rows,no_of_columns);
    int min,pos,count;
    int tempCol[MAX]={0};
    while(checkValue(no_of_rows,no_of_columns,temp_data)){
        for(i=0;i<no_of_rows;i++){
            count=countVal(temp_data[i],no_of_columns,0);
            if(count==1){
                pos=getPosition(temp_data[i],no_of_columns,0);
                allocation[i][pos]=data[i][pos];
                for(j=0;j<no_of_rows;j++)
                    if(temp_data[j][pos]==0)
                        temp_data[j][pos]=9999;
            }
        }
        for(i=0;i<no_of_rows;i++){
            for(j=0;j<no_of_columns;j++)
                tempCol[j]=temp_data[j][i];
            count=countVal(tempCol,no_of_rows,0);
            if(count==1){
                pos=getPosition(tempCol,no_of_rows,0);
                allocation[i][pos]=data[i][pos];
                for(j=0;j<no_of_columns;j++)
                    if(temp_data[pos][j]==0)
                        temp_data[pos][j]=9999;
            }

        }
    }
}
void HungarianMethod::display(){
    int i,j;
    cout<<"\nGiven Cost Metrix :\n";
    for(i=0;i<no_of_rows;i++)
        cout<<"\t"<<char(65+i);
    cout<<endl;
    for(i=0;i<no_of_rows;i++){
        cout<<i+1;
        for(j=0;j<no_of_columns;j++)
            cout<<"\t"<<data[i][j];
        cout<<endl;
    }
    if(bal_stat!=0){
        cout<<"\n\nhere the give cost metrix is not squar Matrix\n";
        cout<<"so this is a unbalance problem and as a solution";
        cout<<"\n we have add an extra "<<((bal_stat==1)?"column":"row")<<" with 0 value in each\n";
    }
    cout<<"\n\nOpportunity Matrix :\n";
    rowMinima(data,no_of_rows,no_of_columns);
    columnMinima(data,no_of_rows,no_of_columns);
    for(i=0;i<no_of_rows;i++){
        for(j=0;j<no_of_columns;j++)
            cout<<"\t"<<data[i][j];
        cout<<endl;
    }
    int sum=0;
    cout<<"\n\nJobs\t:\tMachine\t:\tCost\n";
    for(i=0;i<no_of_rows;i++)
        for(j=0;j<no_of_columns;j++)
            if(allocation[i][j]!=0){
                cout<<i+1<<"\t:\t"<<char(65+j)<<"\t:\t"<<allocation[i][j];
                sum+=allocation[i][j];
                cout<<endl;
            }
    cout<<"\nTotal Assignment Cost = "<<sum<<" RS.";
}
void main(){
    clrscr();
    HungarianMethod hm;
    int row,col;

    cout<<"enter no of row :";
    cin>>row;
    cout<<"enter no of column :";
    cin>>col;

    hm.setRow(row);
    hm.setColumn(col);
    hm.getData();
    clrscr();
    hm.makeAllocation();
    hm.display();
    getch();
}

OUTPUT: