Pseudo-code

note: This is just one possible solution.

Python Implementation

This is not a heavily optimized solution. Winning the contest is part luck and part efficiency. The more efficient your code, the more solutions you can search during class - thereby making your own luck! This code is just a straight-forward implementation of the pseudo-code.

import numpy

def iterative_improvement_ja(cost_matrix):
    """ 
    Computes a local minimum of the job assignment problem.

    Arguments:
    cost_matrix - a nxn matrix where cost_matrix[person][job] is the cost of
                  assigning job to person.

    Returns:
    a list representing a local minumum where index n stores the job to assign to person n.
    """

    best_seen_assignment = []
    for job in xrange(cost_matrix.shape[0]): # start with the solution "person n gets job n"
        best_seen_assignment.append(job)

    best_seen_assignment_cost = compute_cost(best_seen_assignment, cost_matrix)
    found_better = True

    while found_better:  # while better solutions are being found for each iteration of the search
        found_better = False
        assignment = list(best_seen_assignment) # start with best known solution
        for personA in xrange(len(assignment)): # try swapping jobs for every pair of persons
            for personB in xrange(personA + 1, len(assignment)):
                tmp = assignment[personA] # swap jobs
                assignment[personA] = assignment[personB]
                assignment[personB] = tmp

                cost = compute_cost(assignment, cost_matrix)

                if( cost < best_seen_assignment_cost): # is swap bettter?
                    best_seen_assignment = list(assignment)
                    best_seen_assignment_cost = cost
                    found_better = True
                
                tmp = assignment[personA] # undo swap
                assignment[personA] = assignment[personB]
                assignment[personB] = tmp

    
    print best_seen_assignment

def compute_cost(assignment, cost_matrix):
    """ 
    Computes the cost of a job assignment

    Arguments:
    assignment - a list representing an assignment where index n stores the job to assign to person n.
    cost_matrix - a nxn matrix where cost_matrix[person][job] is the cost of
                  assigning job to person.

    Returns:
    the cost of the assignment
    """
    total = 0
    for person in xrange(len(assignment)):
        job = assignment[person]
        total += cost_matrix[person][job]

    return total