Question

Como resolver o problema da alocação em python usando a técnica conhecida como Branch and Bound?

Comments

É interessante notar que a estratégia "branch and bound" é um caso particular da estratégia "exhaustive search" (ie gerar todos os casos e identificar o que atende ao critério desejado). Nesse sentido, a estratégia "branch and bound" é uma implementação esperta, pois acrescenta um critério de viabilidade que restringe o universo da busca, baseado numa cota superior/inferior ao que se pode obter com um determinado "caminho", daí sua aplicação natural em problemas de otimização.

Answer 1

people_jobs = {0:[9,2,7,8],
               1:[6,4,3,7],
               2:[5,8,1,8],
               3:[7,6,9,4]}

import Queue

bestList=[]

class Node:
    def __init__(self,level,value,bound,ans):
        self.level=level 
        self.value=value 
        self.bound=bound   
        self.ans=ans   

def get_Bound(node,people_jobs):
    lowerBound = node.value
    j = node.level + 1
    while j < len(people_jobs[0]):
        lowerBound = lowerBound + min(people_jobs[j])
        j = j + 1
    return lowerBound

def solve_assignment(people_jobs):
    numberJobs=len(people_jobs[0])
    queue=Queue.PriorityQueue()
    root=Node(-1,0,0,[])
    queue.put((0,root))
    minvalue=10000000000
    while not queue.empty():
        v=queue.get()[1]
        print "Level: ",v.level,"Value: ",v.value, "Bound: ",v.bound,"Value ",v.value,"Ans ",v.ans
        if(v.bound<minvalue and v.level<numberJobs-1):
            uLevel=v.level+1
            for i in range(0,numberJobs):
                if i not in v.ans:
                    uValue=v.value+people_jobs[uLevel][i]
                    uAssignment=v.ans[:]
                    uAssignment.append(i)
                    u=Node(uLevel,uValue,0,uAssignment)
                    uBound=get_Bound(u,people_jobs)
                    u=Node(uLevel,uValue,uBound,uAssignment)

                if u.level==numberJobs-1 and u.value<minvalue:
                    minvalue=u.value
                    global bestList 
                    bestList=u.ans[:]

                if u.bound<minvalue:
                    queue.put((u.bound,u))

    print "minValue",minvalue                
    return minvalue,bestList

solve_assignment(people_jobs)

Comments

O algoritmo dessa resposta é baseado no desenvolvido em http://prorum.com/index.php/2470/resolver-problema-mochila-usando-tecnica-conhecida-branch.

---

No caso particular desse problema, o critério para determinar se um determinado "caminho" é promissor é o mínimo das alocações com as quais é factível, supondo que os trabalhos possam ser alocados a mais de uma pessoa. Naturalmente essa suposição não se sustenta na resposta final, mas é um indicativo se a solução "tentative" é promissora e permite cortar ("prune") as que não o forem. Afinal, se nem com essa hipótese o caminho leva a uma solução melhor que a já identificada, que dirá sem ela.