gistfile1.py

def build_model(self):
    #   Initialize the problem
    santa = LpProblem("santa", LpMinimize)

    #   Generate distances
    w = h = self.cities.shape[0]
    distances = [[0 for x in range(w)] for y in range(h)]
    for index_a, row_a in tqdm(self.cities.iterrows(), total=self.cities.shape[0]):
        lat_a = row_a["lat"]
        lon_a = row_a["lng"]
        for index_b, row_b in self.cities.iterrows():
            lat_b = row_b["lat"]
            lon_b = row_b["lng"]
            distances[index_a][index_b] = self.calculate_distance(lat_a, lon_a, lat_b, lon_b)

    #   Generate dictionary to create the Linear program decision variables
    distances_dict = dict(((a, b), distances[a][b]) for a in self.cities.index for b in self.cities.index if a != b)
    #   The objective function
    x = LpVariable.dicts('x', distances_dict, 0, 1, LpBinary)
    self.x = x
    self.variables_dict = dict([(str(value), key) for key, value in x.items()])
    cost = lpSum([x[(i, j)] * distances_dict[(i, j)] for (i, j) in distances_dict])

    #   Add cost function to the model
    santa += cost

    #   Add other constraints, after this we will only need to add the subtour elimination constraints!
    for k in self.cities.index:
        # every site has exactly one inbound connection
        santa += lpSum([x[(i, k)] for i in self.cities.index if (i, k) in x]) == 1
        # every site has exactly one outbound connection
        santa += lpSum([x[(k, i)] for i in self.cities.index if (k, i) in x]) == 1

    self.distances_dict = distances_dict
    self.santa = santa