In [3]:

    

#部分巡回路除去定式化
#部分巡回路除去制約はカットセット制約と同じ
#部分巡回路除去制約を追加するaddcut関数を作る
import gurobipy
import networkx
def addcut(edges):
    G = networkx.Graph()
    G.add_nodes_from(V)
    for (i,j) in edges:
        G.add_edge(i,j)
    
    Components = networkx.connected_components(G)
    if len(Components) == 1:
        return False
    
    for S in Components:
        model.addConstr(quicksum(x[i,j] for i in S for j in S if j > i ) <= len(S) -1)
    
    return True


    

In [4]:

    

def make_data(n, prob):
    V = range(1, n+1)
    E = [(i,j) for i in V for j in V if i < j and random.random() < prob]
    return V, E


    

In [5]:

    

#部分巡回路除去法
def solve_tsp(V, c):
    model = Model("tsp")
    x = {}
    for i in V:
        for j in V:
            if j >i:
                x[i,j] = model.addVar(ub = 1)
    model.update()
    
    fori in V:
        model.addConstr(quicksum(x[j,i] for j in V if j < i) + quicksum(x[i,j] for j in V if j>i) == 2)
        
    model.setObjective(quicksum(c[i,j]*x[i,j] for i in V for j in V if j > i))
    EPS = 1.e-6
    while True:
        model.optimize()
        edges = []
        for (i,j) in x:
            if x[i,j].X > EPS:
                edges.append((i,j))
        if addcut(edges) == False:
            if model.IsMIP:
                break
            for (i,j) in x:
                x[i,j].Vtype = "B"
            model.update()
    
    return model.ObjVal, egdes


    

    




  File "<ipython-input-5-57d94b232dab>", line 11
    fori in V:
             ^
SyntaxError: invalid syntax

In [ ]: