Auction algorithm using numba.

auction.py

from numba import jit
import numpy as np

index_dtype = np.int32
cost_dtype = np.int32    

@jit(nopython=True)
def auction(a, eps=1):
    n = len(a)
    p = np.zeros(n, dtype=cost_dtype)
    for eps_scaling in [10000,1000,100,10,1]:
        eps_scaled = eps_scaling * eps
        o = -np.ones(n, dtype=index_dtype)
        q = list(range(n))        
        while len(q):
            i = q.pop()
            j = 0
            v = 0
            w = 0
            for jc in range(n):
                value = a[i,jc] - p[jc]
                if value > w:
                    if value <= v:
                        w = value
                    else:
                        w = v
                        v = value
                        j = jc
            if o[j] > -1:
                q.append(o[j])
            o[j] = i
            gamma = (v - w) + eps_scaled
            p[j] += gamma
    return o

n = 10000
max_entry = 1000000
a = np.random.randint(low=0, high=max_entry, size=(n, n), dtype=cost_dtype)
sol = auction(a) # 1.8 seconds