BnB

#!/usr/bin/python
def cmax(p, solution):
    """A value function for C_max"""

    machines = range(len(p))
    return max(sum(p[machine][task]
        for task in range(len(solution)) if solution[task]==machine)
            for machine in machines)

def lower(p, solution):
    """Our testing lower bound function"""
    machines = range(len(p))
    tasks = range(len(p[0]))
    estimate = float(sum(min(
        p[machine][task] for machine in machines)
            for task in tasks))/len(machines)
    return max(cmax(p, solution), estimate)

def next_gen(p, solution):
    """A generator for subproblems"""

    for machine in range(len(p)):
        yield solution+[machine]

def bnb(p, value_function, bound_function, subsolution_gen):
    """Generic Branch&Bound procedure"""

    best = (1000.0, [])
    queue = [best]
    steps = 0
    max_length = len(p[0])
    while queue:
        steps += 1
        bound, solution = queue.pop(0)
        if len(solution)>=max_length and value_function(p, solution)<best[0]:
            best = (value_function(p, solution), solution)
        if len(solution)<max_length:
            for subsolution in subsolution_gen(p, solution):
                bound = bound_function(p, subsolution)
                if bound <= best[0]:
                    queue.append((bound, subsolution))
        queue.sort()
    return best, steps

if __name__=="__main__":
    import random
    for i in range(1000):
        tasks = range(random.randint(2, 5))
        machines = range(random.randint(2, 3))
        p = [[random.randint(1, 10) for task in tasks] for machine in machines]
        brute_solution, brute_steps = bnb(p, cmax, brute, next_gen)
        lower_solution, lower_steps = bnb(p, cmax, lower, next_gen)
        if lower_steps!=brute_steps:
            print brute_steps, lower_steps
        if brute_solution!=lower_solution:
            print "Difference!"
            print "Input: ", p
            print "Brute: ", brute_solution
            print "Lower: ", lower_solution
        if brute_solution[0]!=lower_solution[0]:
            break