vrp_lazy.py 文件源码

def addCuts(self, checkonly):
        """add cuts if necessary and return whether model is feasible"""
        cutsadded = False
        edges = []
        x = self.model.data
        for (i, j) in x:
            if self.model.getVal(x[i, j]) > .5:
                if i != V[0] and j != V[0]:
                    edges.append((i, j))
        G = networkx.Graph()
        G.add_edges_from(edges)
        Components = list(networkx.connected_components(G))
        for S in Components:
            S_card = len(S)
            q_sum = sum(q[i] for i in S)
            NS = int(math.ceil(float(q_sum) / Q))
            S_edges = [(i, j) for i in S for j in S if i < j and (i, j) in edges]
            if S_card >= 3 and (len(S_edges) >= S_card or NS > 1):
                cutsadded = True
                if checkonly:
                    break
                else:
                    self.model.addCons(quicksum(x[i, j] for i in S for j in S if j > i) <= S_card - NS)
                    print("adding cut for", S_edges)

        return cutsadded