finding the minimum number of lines to cover all zeros in an assignment problem

Question

I have been trying to follow the following steps to find the minimum number of horizontal and vertical lines that cover all the zeros in an assignment problem using Hungarian method:

Tick all unassigned rows.

If the ticked row has zeros, then tick the corresponding column.

Within the ticked column, if there is an assignment, then tick the corresponding row.

Draw a line through each un-ticked row and ticked column.

Repeat for each unassigned row.

Then find Theta (which is the smallest uncovered value)

The problem is when I do that, I still have zeros uncovered! causing Theta to be zero and go to an infinite loop!

The question is :

$$ \begin{matrix} 2 & 9 & 2 & 7 & 1 \\ 6 & 8 & 7 & 6 & 1 \\ 4 & 6 & 5 & 3 & 1 \\ 4 & 2 & 7 & 3 & 1 \\ 5 & 3 & 9 & 5 & 1 \\ \end{matrix} $$

After subtracting the row minimum from the corresponding row and column minimum from the corresponding column i got :

$$ \begin{matrix} 0 & 7 & 0 & 4 & 0 \\ 4 & 6 & 5 & 3 & 0 \\ 2 & 4 & 3 & 0 & 0 \\ 2 & 0 & 5 & 0 & 0 \\ 3 & 1 & 7 & 2 & 0 \\ \end{matrix} $$

Now when i used the algorithm given above for covering all the zeros i got:

$$ \begin{matrix} \color{red}{0} & \color{red}{7} & \color{red}{0} & \color{red}{4} & \color{red}{0} \\ 4 & 6 & 5 & 3 & \color{red}{0} \\ \color{red}{2} & \color{red}{4} & \color{red}{3} & \color{red}{0} & \color{red}{0} \\ \color{red}{2} & \color{red}{0} & \color{red}{5} & \color{red}{0} & \color{red}{0} \\ 3 & 1 & 7 & 2 & \color{red}{0} \\ \end{matrix} $$

Red rows and columns represent the ones covered (found according to the above steps).

After this i added and subtracted $1$ from the relevant positions to get the following matrix:

$$ \begin{matrix} 0 & 7 & 0 & 4 & 1 \\ 3 & 5 & 4 & 2 & 0 \\ 2 & 4 & 3 & 0 & 1 \\ 2 & 0 & 5 & 0 & 1 \\ 2 & 0 & 6 & 1 & 0 \\ \end{matrix} $$

Using the same method given above for covering all zeros i got the following matrix:

$$ \begin{matrix} \color{red}{0} & \color{red}{7} & \color{red}{0} & \color{red}{4} & \color{red}{1} \\ 3 & \color{red}{5} & 4 & 2 & \color{red}{0} \\ \color{red}{2} & \color{red}{4} & \color{red}{3} & \color{red}{0} & \color{red}{1} \\ 2 & \color{red}{0} & 5 & \color{blue}{0} & \color{red}{1} \\ 2 & \color{red}{0} & 6 & 1 & \color{red}{0} \\ \end{matrix} $$

I don't understand why one zero is being left out (colored blue) ?

I figured that instead of striking out the third column if i striked out the fourth column then i would get an optimal solution.

But i don't understand why this doesn't happen, using the steps given above?

Where have i gone wrong ?

Any help would be appreciated.

Answer 1

It's kinda late ;-) and I'm sure you've moved on, but here it is - the steps to draw a minimum number of lines should be a little different:

1. Tick all unassigned rows
2. Tick all (unticked) columns that have zeros in ticked rows
3. Tick all (unticked) rows that have assigned zeros in ticked columns
4. Go back to point 2 unless there are no more columns that need ticking
5. Draw a line through every ticked column and every unticked row.

If we stop ticking prematurely, we may miss some zeros. It works on the matrix you provided. This is a part of the solution of the assignment problem with the Hungarian Method (or the Hungarian algorithm), see Wikipedia for details: https://en.wikipedia.org/wiki/Hungarian_algorithm#Matrix_interpretation

Answer 2

The method given by you for covering all the zeros with minimum lines works in the later matrix as well.

If after assigning, we start with unassigned rows then the process goes as follows.

The 5th row is ticked.

Then 2nd and 5th column are ticked.

Then 2nd and 4th row are ticked as they have assignments.

Then 4th column is ticked as it has a 0 in the 4th row.

Then 3rd row are ticked as it has assignment.

This gives 1st row un-ticked and 2nd, 4th and 5th row ticked through which minimum lines can be drawn to cover all the zeroes.

Answer 3

I followed the Wikipedia article and I made an implementation that seems to work all the time. @000 answer helped me a lot with this but I figured I would post my code if anybody finds it useful to see how I did it. (note this is just for step which is what the OP was having trouble with.

Basically as long as there is still a zero which isn't covered the code repeats 2,3 and 4.

Ruby Code:

 
def draw_lines grid
    #copies the array   
    marking_grid = grid.map { |a| a.dup }

    marked_rows = Array.new
    marked_cols = Array.new

    while there_is_zero(marking_grid) do 
        marking_grid = grid.map { |a| a.dup }

        marked_cols.each do |col|
            cross_out(marking_grid,nil, col)
        end

        marked = assignment(grid, marking_grid) 
        marked_rows = marked[0]
        marked_cols.concat(marked[1]).uniq!

        marking_grid = grid.map { |a| a.dup }

        marking_grid.length.times do |row|
            if !(marked_rows.include? row) then
                cross_out(marking_grid,row, nil)
            end
        end

        marked_cols.each do |col|
            cross_out(marking_grid,nil, col)
        end
    end


    lines = Array.new

    marked_cols.each do |index|
        lines.push(["column", index])
    end
    grid.each_index do |index|
        if !(marked_rows.include? index) then
            lines.push(["row", index])
        end
    end
    return lines
end


def there_is_zero grid
    grid.each_with_index do |row|
        row.each_with_index do |value|
            if value == 0 then
                return true
            end
        end
    end
    return false
end

def assignment grid, marking_grid 
    marking_grid.each_index do |row_index|
        first_zero = marking_grid[row_index].index(0)
        #if there is no zero go to next row
        if first_zero.nil? then
            next        
        else
            cross_out(marking_grid, row_index, first_zero)
            marking_grid[row_index][first_zero] = "*"
        end
    end

    return mark(grid, marking_grid)
end


def mark grid, marking_grid, marked_rows = Array.new, marked_cols = Array.new
    marking_grid.each_with_index do |row, row_index|
        selected_assignment = row.index("*")
        if selected_assignment.nil? then
            marked_rows.push(row_index)
        end
    end

    marked_rows.each do |index|
        grid[index].each_with_index do |cost, col_index|
            if cost == 0 then
                marked_cols.push(col_index) 
            end
        end
    end
    marked_cols = marked_cols.uniq

    marked_cols.each do |col_index|
        marking_grid.each_with_index do |row, row_index|
            if row[col_index] == "*" then
                marked_rows.push(row_index) 
            end
        end
    end

    return [marked_rows, marked_cols]
end


def cross_out(marking_grid, row, col)
    if col != nil then
        marking_grid.each_index do |i|
            marking_grid[i][col] = "X"  
        end
    end
    if row != nil then
        marking_grid[row].map! {|i| "X"} 
    end
end

grid = [
    [0,0,1,0],
    [0,0,1,0],
    [0,1,1,1],
    [0,1,1,1],
]

p draw_lines(grid)