notebook.community

Edit and run

Mowing Like a Salesperson Travels





In [1]:



    


import gurobi as g
import numpy as np

These classes are used for creating the map of a yard. T is for a standard tile and B is for a "blocked" tile. Blocked tiles are for areas in a yard one can't mow like trees, bushes, houses, etc.

I is used as a sort of identity service. It generates unique ids when asked. The tiles make use of this to id themselves.





In [2]:



    


class I:
    def __init__(self):
        self._counter = -1
    def next(self):
        self._counter += 1
        return self._counter

class T:
    def __init__(self, incrementor):
        self._connected_tiles = []
        self._id = incrementor.next()
    def connects_to(self, to_tile):
        self._connected_tiles.append(to_tile)
    def get_both_directed_edges(self):
        return [(self._id, to_tile._id) for to_tile in self._connected_tiles]
    def is_blocked(self):
        return False
class B:
    def __init__(self, incrementor):
        self._id = incrementor.next()
    def connects_to(self, to_tile):
        pass
    def get_both_directed_edges(self):
        return []
    def is_blocked(self):
        return True

These are scenarios I created to play with this program. These can be used further down the notebook.





In [3]:



    


def generate_house_tiles():
    i = I()
    # Create tiles for my yard as a grid
    tiles = []
    # Map grid locations to an array
    locations = []
    for row_index in range(44):
        row = []
        for column_index in range(26):
            if 0 <= row_index and row_index <= 5 and \
               0 <= column_index and column_index <= 7:
                row.append(B(i))
            elif 6 <= row_index and row_index <= 10 and \
                 0 <= column_index and column_index <= 5:
                row.append(B(i))
            elif 0 <= row_index and row_index <= 2 and \
                 19 <= column_index and column_index <= 25:
                row.append(B(i))
            elif 3 <= row_index and row_index <= 4 and \
                 20 <= column_index and column_index <= 25:
                row.append(B(i))
            elif 5 <= row_index and row_index <= 5 and \
                 23 <= column_index and column_index <= 25:
                row.append(B(i))
            elif 6 <= row_index and row_index <= 7 and \
                 24 <= column_index and column_index <= 25:
                row.append(B(i))
            elif 8 <= row_index and row_index <= 9 and \
                 25 <= column_index and column_index <= 25:
                row.append(B(i))
            elif 8 <= row_index and row_index <= 10 and \
                 10 <= column_index and column_index <= 12:
                row.append(B(i))
            elif 16 <= row_index and row_index <= 17 and \
                 1 <= column_index and column_index <= 2:
                row.append(B(i))
            elif 13 <= row_index and row_index <= 15 and \
                 6 <= column_index and column_index <= 16:
                row.append(B(i))
            elif 16 <= row_index and row_index <= 17 and \
                 6 <= column_index and column_index <= 23:
                row.append(B(i))
            elif 18 <= row_index and row_index <= 23 and \
                 5 <= column_index and column_index <= 23:
                row.append(B(i))
            elif 24 <= row_index and row_index <= 31 and \
                 5 <= column_index and column_index <= 25:
                row.append(B(i))
            elif 32 <= row_index and row_index <= 43 and \
                 21 <= column_index and column_index <= 25:
                row.append(B(i))
            elif 34 <= row_index and row_index <= 35 and \
                 17 <= column_index and column_index <= 18:
                row.append(B(i))
            elif 41 <= row_index and row_index <= 42 and \
                 5 <= column_index and column_index <= 6:
                row.append(B(i))
            elif 41 <= row_index and row_index <= 42 and \
                 9 <= column_index and column_index <= 10:
                row.append(B(i))
            elif 41 <= row_index and row_index <= 42 and \
                 13 <= column_index and column_index <= 14:
                row.append(B(i))
            elif 41 <= row_index and row_index <= 42 and \
                 17 <= column_index and column_index <= 18:
                row.append(B(i))
            else:
                row.append(T(i))
            locations.append((column_index, row_index))
        tiles.append(row)

    # Tiles mapped onto linear list
    flat_tiles = [x for row in tiles for x in row] #AKA tile_list
    return tiles, locations, flat_tiles

def generate_demo_tiles():
    i = I()
    # Create tiles for my yard as a grid
    tiles = []
    # Map grid locations to an array
    locations = []
    for row_index in range(15):
        row = []
        for column_index in range(15):
            if 4 <= row_index and row_index <= 8 and \
               2 <= column_index and column_index <= 4:
                row.append(B(i))
            elif 5 <= row_index and row_index <= 6 and \
                 5 <= column_index and column_index <= 9:
                row.append(B(i))
            elif 2 <= row_index and row_index <= 2 and \
                 6 <= column_index and column_index <= 7:
                row.append(B(i))
            elif 7 <= row_index and row_index <= 8 and \
                 8 <= column_index and column_index <= 9:
                row.append(B(i))
            else:
                row.append(T(i))
            locations.append((column_index, row_index))
        tiles.append(row)

    # Tiles mapped onto linear list
    flat_tiles = [x for row in tiles for x in row] #AKA tile_list
    return tiles, locations, flat_tiles

These functions do the hard stuff. They interpret the tile layout and create a set of edges and turns for the unblocked locations.





In [4]:



    


def enumerate_edge_turns(edges):
    edge_turns = set()
    for left_edge_indexes in edges:
        left_edge = tuple(locations[x] for x in left_edge_indexes)
        for right_edge_indexes in [x for x in edges if x != left_edge_indexes and left_edge_indexes[1] == x[0]]:
            right_edge = tuple(locations[x] for x in right_edge_indexes)
            if is_turn(left_edge, right_edge):
                edge_turns.add(((locations.index(left_edge[0]), locations.index(left_edge[1])), (locations.index(right_edge[0]), locations.index(right_edge[1]))))
    return edge_turns

def is_turn(edge1, edge2):
    assert edge1[1] == edge2[0], 'Edge1 doesn\'t connect to edge2! {0}'.format(edge1,edge2)
    x, y = list(zip(*[edge1[0],edge1[1],edge2[1]]))
    return not (x[0] == x[1] == x[2]) and not (y[0] == y[1] == y[2])

def generate_edges_for(tiles):
    for row_index in range(len(tiles)):
        for col_index in range(len(tiles[0])):
            from_tile = tiles[row_index][col_index]
            if from_tile.is_blocked():
                continue
            for row_offset in [-1,0,1]:
                for col_offset in [-1,0,1]:
                    offset_row_index = row_index + row_offset
                    offset_col_index = col_index + col_offset

                    if offset_row_index < 0 or offset_row_index > len(tiles)-1:
                        continue
                    if offset_col_index < 0 or offset_col_index > len(tiles[0])-1:
                        continue
                    if row_offset == 0 and col_offset == 0:
                        continue
                    if np.abs(row_offset) + np.abs(col_offset) == 2:
                        continue
                    to_tile = tiles[offset_row_index][offset_col_index]
                    if not to_tile.is_blocked():
                        from_tile.connects_to(to_tile)

    edges = [from_tile.get_both_directed_edges() for rows in tiles for from_tile in rows]
    edges = [pair for edge_list in edges for pair in edge_list]
    edge_turns = enumerate_edge_turns(edges)
    return edges, edge_turns

This code can evaluate a proposed solution and find cycles that are added as constraints.





In [5]:



    


def _find_cycles(solution_edges):
    cycles = []
    shortest_cycle = None
    while len(solution_edges) > 0:
        cycle=[]
        edge = solution_edges[0]
        first_node = edge[0]
        next_node = first_node
        nodes_to_remove = set()
        while True:
            next_node_index = [from_node for from_node, to_node in solution_edges].index(next_node)
            next_edge = solution_edges[next_node_index]
            next_node = next_edge[1]
            cycle.append(tuple([element for tuple_ in next_edge for element in tuple_]))
            nodes_to_remove.add(next_node_index)
            if next_node == first_node:
                print('Cycle length: ', len(cycle))
                break
        solution_edges = [x for i, x in enumerate(solution_edges) if i not in nodes_to_remove]
        cycles.append(cycle)
        if shortest_cycle is None or len(cycle) < len(shortest_cycle):
            shortest_cycle = cycle
    return shortest_cycle, len(cycles), cycles

# This method just enables debugging.
def find_cycles(location_edges):
    # We round the solution because floating point error is REAL!!
    solution_edges = [(locations[xy1], locations[xy2]) for xy1, xy2 in location_edges if round(location_edges[xy1, xy2].X) == 1]
    print('About to find cycles!')
    return _find_cycles(solution_edges)

def to_loc(edge):
    location_index_1 = locations.index((edge[0], edge[1]))
    location_index_2 = locations.index((edge[2], edge[3]))
    return (location_index_1, location_index_2)

This code is used for displaying the map and the solutions. Basically just works by plotting a line segment for every activated edge. Turns aren't necessary since the edges themselves imply turns.





In [6]:



    


import matplotlib.pyplot as plt
%matplotlib inline

def plot_tsp_solution(flat_tiles, location_edges=[], row_count=44, col_count=26, solution_exists=True):
    plt.figure(figsize=(col_count/3,row_count/3))
    plt.suptitle('TSP Solution to Mowing Lawn ({0} units x {1} units)'.format(col_count, row_count))
    plt.title('Red things are blocking objects')
    for column_index in range(col_count+1):
        plt.plot([-0.5+column_index, -0.5+column_index], [0-0.5, row_count+0.5-1], color='g', linestyle=':', linewidth=1);
    for row_index in range(row_count+1):
        plt.plot([0-0.5, (col_count-1)+0.5], [-0.5+row_index, -0.5+row_index], color='g', linestyle=':', linewidth=1);
    
    # If we don't have edges to plot don't try so 
    # we can still just plot the tiles without paths
    if solution_exists:
        for edge in location_edges:
            if round(location_edges[edge].X) == 1:
                xy1, xy2 = edge
                y1 = locations[xy1][1]
                x1 = locations[xy1][0]

                y2 = locations[xy2][1]
                x2 = locations[xy2][0]

                #print((x1, y1), (x2,y2))
                plt.plot([x1, x2], [y1, y2], color='k', linestyle='-', linewidth=2);
    
    # Plot blocked points
    for index, tile in enumerate(flat_tiles):
        if tile.is_blocked():
            x,y = locations[index]
            plt.scatter(x,y,c='r',marker='s',s=160);
    plt.show()

The Mathematical Model

Variables:

$ L = (x,y)\ locations\ of\ all\ tiles$

$ E = (l_1, l_2) \in L $

$ T = (e_1, e_2)\ where\ e_1,e_2 \in E\ and\ F_T(e_1, e_2)$

$F_T(e_1, e_2) = \begin{cases} 1 & if\ edges\ form\ a\ turn\\ 0 & otherwise \end{cases}$

$F_A(l_1, l_2) = \begin{cases} 1 & if\ locations\ are\ adjacent\\ 0 & otherwise \end{cases}$

$x^T_{ij} = \begin{cases} 1 & if\ turn\ is\ used\\ 0 & otherwise \end{cases} where\ (i,j) \in T $

$x^E_{ij} = \begin{cases} 1 & if\ edge\ is\ used\\ 0 & otherwise \end{cases} where (i,j) \in L $

$ \sum_{i \in L} x^E_{ij} = F_A(i,j),\ \forall\ j \in L$ Each location is entered via exactly one edge

$ \sum_{j \in L} x^E_{ij} = F_A(i,j),\ \forall\ i \in L $ Each location is exited via exactly one edge

$ x^E_{ij} + x^E_{ji} <= 1,\ \forall\ i,j \in L $ A location can't loop to itself.

$-1 + x^E_i + x^E_j <= 2x^T_{ij} <= x^E_i + x^E_j\ \forall i,j \in T $

The Coded Model





In [7]:



    


# For generating tiles to optimize mowing my personal yard
tiles, locations, flat_tiles = generate_house_tiles()
# This one generates a fairly solveable problem for testing.
#tiles, locations, flat_tiles = generate_demo_tiles()

# Create what I'll use for my variables
edges, edge_turns = generate_edges_for(tiles)

# Let's see what our scenario looks like without a path
print('The top of the picture is the front of my house.')
plot_tsp_solution(flat_tiles, solution_exists=False)



    


















    






The top of the picture is the front of my house.

Create the model and define the variables we'll use. Here we create variables for every valid edge and every possible turn from each of those edges.





In [8]:



    


# The actual model definition
m = g.Model('tsp')
location_edges  = m.addVars(edges,  name="location_edges",  vtype=g.GRB.BINARY)
location_edge_turns  = m.addVars(edge_turns,  name="location_edge_turns",  vtype=g.GRB.BINARY)



    


















    






Academic license - for non-commercial use only

For every location that isn't "blocked" (blocked meaning it has a red square in the picture above) constrain the solution such that exactly one edge leads into the location and one leads out from it.





In [9]:



    


for location in range(len(tiles)*len(tiles[0])):
    if not flat_tiles[location].is_blocked():
        m.addConstr(location_edges.sum(location, '*') == 1)
        m.addConstr(location_edges.sum('*', location) == 1)

Make sure no location has an edge that leads to itself.





In [10]:



    


for edge in location_edges:
    m.addConstr(location_edges[edge] + location_edges[(edge[1], edge[0])] <= 1)

Next add the constraints that will set the turn variables enabling us to count how many turns are made.





In [11]:



    


for edge_turn in edge_turns:
    # These two constraints work to fix the turn variables
    # And keep them in sync with the edges
    # -1/2 + 1/2 * (edge_1 + edge_2) <= turn_12
    # turn_12 <= 1/2 * (edge_1 + edge_2)
    m.addConstr(-1 + location_edges[edge_turn[0]] + location_edges[edge_turn[1]] <= 2*location_edge_turns[edge_turn[0], edge_turn[1]])
    m.addConstr(2*location_edge_turns[edge_turn[0], edge_turn[1]] <= location_edges[edge_turn[0]] + location_edges[edge_turn[1]])

Our objective value is most important! Here I set the objective value to just minimize the number of turns that are made when mowing my lawn.





In [12]:



    


objective_value = g.LinExpr()
objective_value += sum([location_edge_turns[turn] for turn in location_edge_turns])
m.setObjective(objective_value, g.GRB.MINIMIZE)

Next, we run the model. Note that it is ran and then we enter a while loop to keep running it as long as there are more than two cycles. Why two and not one? If we find a solution with two cycles I'm willing to call it "good enough".





In [ ]:



    


m.optimize()
plot_tsp_solution(flat_tiles, location_edges, row_count=len(tiles), col_count=len(tiles[0]))

while True:
    shortest_cycle, cycle_count, cycles = find_cycles(location_edges)
    if cycle_count <= 2:
        print('Solved!')
        plot_tsp_solution(flat_tiles, location_edges, row_count=len(tiles), col_count=len(tiles[0]))
        break
    else:
        for cycle in cycles:
            m.addConstr(sum([location_edges[to_loc(edge)] for edge in cycle]) <= len(cycle)-1)
        m.optimize()
        plot_tsp_solution(flat_tiles, location_edges, row_count=len(tiles), col_count=len(tiles[0]))



    


















    






Optimize a model with 10538 rows, 5722 columns and 30200 nonzeros
Variable types: 0 continuous, 5722 integer (5722 binary)
Coefficient statistics:
  Matrix range     [1e+00, 2e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 1e+00]
Presolve removed 1762 rows and 400 columns
Presolve time: 0.17s
Presolved: 8776 rows, 5322 columns, 26186 nonzeros
Variable types: 0 continuous, 5322 integer (5322 binary)
Found heuristic solution: objective 190.0000000

Root relaxation: objective 2.300000e+01, 2253 iterations, 0.16 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0   23.00000    0 1291  190.00000   23.00000  87.9%     -    1s
H    0     0                     186.0000000   23.00000  87.6%     -    1s
     0     0   34.00000    0 1490  186.00000   34.00000  81.7%     -    1s
     0     0   34.00000    0 1477  186.00000   34.00000  81.7%     -    1s
     0     0   42.00000    0 1539  186.00000   42.00000  77.4%     -    2s
     0     0   42.33333    0 1501  186.00000   42.33333  77.2%     -    2s
     0     0   42.33333    0 1494  186.00000   42.33333  77.2%     -    2s
     0     0   45.39583    0 1568  186.00000   45.39583  75.6%     -    2s
     0     0   45.83333    0 1551  186.00000   45.83333  75.4%     -    2s
     0     0   45.85714    0 1525  186.00000   45.85714  75.3%     -    3s
     0     0   45.86667    0 1502  186.00000   45.86667  75.3%     -    3s
     0     0   45.86667    0 1492  186.00000   45.86667  75.3%     -    3s
     0     0   50.63853    0 1573  186.00000   50.63853  72.8%     -    3s
     0     0   51.69091    0 1573  186.00000   51.69091  72.2%     -    3s
     0     0   51.99012    0 1550  186.00000   51.99012  72.0%     -    3s
     0     0   51.99246    0 1528  186.00000   51.99246  72.0%     -    3s
     0     0   57.02931    0 1567  186.00000   57.02931  69.3%     -    4s
     0     0   57.86257    0 1642  186.00000   57.86257  68.9%     -    4s
     0     0   58.08298    0 1630  186.00000   58.08298  68.8%     -    4s
     0     0   58.09976    0 1612  186.00000   58.09976  68.8%     -    4s
     0     0   58.14388    0 1577  186.00000   58.14388  68.7%     -    4s
     0     0   58.14408    0 1568  186.00000   58.14408  68.7%     -    4s
     0     0   63.38546    0 1634  186.00000   63.38546  65.9%     -    5s
H    0     0                     184.0000000   63.38546  65.6%     -    5s
     0     0   64.99315    0 1674  184.00000   64.99315  64.7%     -    5s
     0     0   65.21472    0 1648  184.00000   65.21472  64.6%     -    5s
     0     0   65.28921    0 1661  184.00000   65.28921  64.5%     -    5s
     0     0   65.34504    0 1661  184.00000   65.34504  64.5%     -    5s
     0     0   65.34882    0 1659  184.00000   65.34882  64.5%     -    5s
     0     0   68.30663    0 1649  184.00000   68.30663  62.9%     -    6s
     0     0   69.55696    0 1651  184.00000   69.55696  62.2%     -    6s
     0     0   69.88036    0 1662  184.00000   69.88036  62.0%     -    6s
     0     0   69.92683    0 1683  184.00000   69.92683  62.0%     -    6s
     0     0   69.93522    0 1647  184.00000   69.93522  62.0%     -    6s
     0     0   71.76486    0 1703  184.00000   71.76486  61.0%     -    6s
     0     0   72.45896    0 1733  184.00000   72.45896  60.6%     -    7s
     0     0   72.59816    0 1738  184.00000   72.59816  60.5%     -    7s
     0     0   72.60965    0 1701  184.00000   72.60965  60.5%     -    7s
     0     0   75.67164    0 1715  184.00000   75.67164  58.9%     -    7s
H    0     0                     182.0000000   75.67164  58.4%     -    7s
     0     0   76.33509    0 1756  182.00000   76.33509  58.1%     -    8s
     0     0   76.55284    0 1784  182.00000   76.55284  57.9%     -    8s
     0     0   76.61788    0 1781  182.00000   76.61788  57.9%     -    8s
     0     0   76.64444    0 1763  182.00000   76.64444  57.9%     -    8s
     0     0   76.65086    0 1766  182.00000   76.65086  57.9%     -    8s
     0     0   79.56159    0 1665  182.00000   79.56159  56.3%     -    8s
     0     0   80.36759    0 1771  182.00000   80.36759  55.8%     -    9s
     0     0   80.51917    0 1814  182.00000   80.51917  55.8%     -    9s
     0     0   80.58462    0 1825  182.00000   80.58462  55.7%     -    9s
     0     0   80.62665    0 1837  182.00000   80.62665  55.7%     -    9s
     0     0   80.63779    0 1833  182.00000   80.63779  55.7%     -    9s
     0     0   82.15785    0 1784  182.00000   82.15785  54.9%     -    9s
     0     0   82.93787    0 1764  182.00000   82.93787  54.4%     -    9s
     0     0   83.03145    0 1782  182.00000   83.03145  54.4%     -    9s
     0     0   83.09144    0 1833  182.00000   83.09144  54.3%     -    9s
     0     0   83.10047    0 1824  182.00000   83.10047  54.3%     -   10s
     0     0   85.49541    0 1795  182.00000   85.49541  53.0%     -   10s
     0     0   86.03667    0 1849  182.00000   86.03667  52.7%     -   10s
     0     0   86.13210    0 1841  182.00000   86.13210  52.7%     -   10s
     0     0   86.14346    0 1857  182.00000   86.14346  52.7%     -   10s
     0     0   88.02937    0 1819  182.00000   88.02937  51.6%     -   11s
     0     0   88.60125    0 1843  182.00000   88.60125  51.3%     -   11s
     0     0   88.72221    0 1849  182.00000   88.72221  51.3%     -   11s
     0     0   88.76221    0 1856  182.00000   88.76221  51.2%     -   11s
     0     0   88.76419    0 1848  182.00000   88.76419  51.2%     -   11s
     0     0   90.06746    0 1836  182.00000   90.06746  50.5%     -   11s
     0     0   90.44092    0 1899  182.00000   90.44092  50.3%     -   12s
     0     0   90.59178    0 1872  182.00000   90.59178  50.2%     -   12s
     0     0   90.63763    0 1894  182.00000   90.63763  50.2%     -   12s
     0     0   90.73034    0 1879  182.00000   90.73034  50.1%     -   12s
     0     0   90.73224    0 1897  182.00000   90.73224  50.1%     -   12s
     0     0   93.51254    0 1849  182.00000   93.51254  48.6%     -   12s
     0     0   93.95920    0 1867  182.00000   93.95920  48.4%     -   13s
     0     0   94.01786    0 1916  182.00000   94.01786  48.3%     -   13s
     0     0   94.04752    0 1901  182.00000   94.04752  48.3%     -   13s
     0     0   94.07399    0 1886  182.00000   94.07399  48.3%     -   13s
     0     0   94.08574    0 1876  182.00000   94.08574  48.3%     -   13s
     0     0   94.82999    0 1882  182.00000   94.82999  47.9%     -   13s
H    0     0                     180.0000000   94.82999  47.3%     -   13s
     0     0   94.97749    0 1909  180.00000   94.97749  47.2%     -   14s
     0     0   95.00585    0 1919  180.00000   95.00585  47.2%     -   14s
     0     0   95.00815    0 1919  180.00000   95.00815  47.2%     -   14s
     0     0   95.67708    0 1915  180.00000   95.67708  46.8%     -   14s
     0     0   95.85694    0 1914  180.00000   95.85694  46.7%     -   14s
     0     0   95.87974    0 1947  180.00000   95.87974  46.7%     -   14s
     0     0   96.39892    0 1905  180.00000   96.39892  46.4%     -   14s
     0     0   96.50681    0 1924  180.00000   96.50681  46.4%     -   15s
     0     0   96.57104    0 1919  180.00000   96.57104  46.3%     -   15s
     0     0   96.62493    0 1962  180.00000   96.62493  46.3%     -   15s
     0     0   96.64504    0 1955  180.00000   96.64504  46.3%     -   15s
     0     0   97.07137    0 1913  180.00000   97.07137  46.1%     -   15s
     0     0   97.22969    0 1945  180.00000   97.22969  46.0%     -   15s
     0     0   97.27184    0 1972  180.00000   97.27184  46.0%     -   15s
     0     0   97.27500    0 1980  180.00000   97.27500  46.0%     -   16s
     0     0   98.04567    0 1934  180.00000   98.04567  45.5%     -   16s
     0     0   98.22986    0 1917  180.00000   98.22986  45.4%     -   16s
     0     0   98.35598    0 1945  180.00000   98.35598  45.4%     -   16s
     0     0   98.36452    0 1958  180.00000   98.36452  45.4%     -   16s
     0     0   99.36941    0 1923  180.00000   99.36941  44.8%     -   16s
     0     0   99.46817    0 1949  180.00000   99.46817  44.7%     -   17s
     0     0   99.50078    0 1954  180.00000   99.50078  44.7%     -   17s
     0     0   99.51746    0 1968  180.00000   99.51746  44.7%     -   17s
     0     0   99.80481    0 1921  180.00000   99.80481  44.6%     -   17s
     0     0   99.84010    0 1966  180.00000   99.84010  44.5%     -   17s
     0     0   99.84905    0 1958  180.00000   99.84905  44.5%     -   17s
     0     0   99.95268    0 1935  180.00000   99.95268  44.5%     -   17s
     0     0   99.95268    0 1902  180.00000   99.95268  44.5%     -   18s
     0     2   99.95268    0 1883  180.00000   99.95268  44.5%     -   19s
     7    10  100.34390    3 1921  180.00000  100.34390  44.3%   322   20s
H   28    28                     178.0000000  100.36045  43.6%   177   20s
   222   224  117.54704   84 1321  178.00000  100.36045  43.6%   141   25s
H  387   371                     162.0000000  100.36045  38.0%   121   27s
H  468   456                     154.0000000  100.36045  34.8%   114   28s
H  503   471                     152.0000000  100.36045  34.0%   111   29s
H  538   525                     150.0000000  100.36045  33.1%   108   29s
   539   529  146.82997  215  415  150.00000  100.68090  32.9%   109   30s
H  569   438                     138.0000000  100.70701  27.0%   109   30s
H  635   473                     136.0000000  100.70701  26.0%   120   32s
   694   540  116.57358   56 1601  136.00000  100.70701  26.0%   131   35s
   744   587  126.38409  120 1585  136.00000  100.70701  26.0%   133   40s
   756   595  132.42063   62  782  136.00000  132.42063  2.63%   131   47s

Cutting planes:
  Gomory: 31
  Implied bound: 640
  MIR: 396
  Flow cover: 96
  Zero half: 336

Explored 759 nodes (177922 simplex iterations) in 48.74 seconds
Thread count was 4 (of 4 available processors)

Solution count 10: 136 138 150 ... 184

Optimal solution found (tolerance 1.00e-04)
Best objective 1.360000000000e+02, best bound 1.360000000000e+02, gap 0.0000%










    

















    






About to find cycles!
Cycle length:  22
Cycle length:  78
Cycle length:  32
Cycle length:  40
Cycle length:  38
Cycle length:  16
Cycle length:  62
Cycle length:  10
Cycle length:  10
Cycle length:  10
Cycle length:  20
Cycle length:  66
Cycle length:  172
Cycle length:  4
Optimize a model with 10552 rows, 5722 columns and 30780 nonzeros
Variable types: 0 continuous, 5722 integer (5722 binary)
Coefficient statistics:
  Matrix range     [1e+00, 2e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 2e+02]

MIP start did not produce a new incumbent solution
MIP start violates constraint R10538 by 1.000000000

Presolve removed 1762 rows and 400 columns
Presolve time: 0.19s
Presolved: 8790 rows, 5322 columns, 26708 nonzeros
Variable types: 0 continuous, 5322 integer (5322 binary)
Found heuristic solution: objective 190.0000000

Root relaxation: objective 2.300000e+01, 2342 iterations, 0.15 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0   23.00000    0 1281  190.00000   23.00000  87.9%     -    1s
H    0     0                     186.0000000   23.00000  87.6%     -    1s
     0     0   32.33333    0 1450  186.00000   32.33333  82.6%     -    1s
     0     0   32.33333    0 1431  186.00000   32.33333  82.6%     -    1s
     0     0   40.58333    0 1534  186.00000   40.58333  78.2%     -    2s
     0     0   41.91667    0 1496  186.00000   41.91667  77.5%     -    2s
     0     0   41.91667    0 1485  186.00000   41.91667  77.5%     -    2s
     0     0   45.48377    0 1597  186.00000   45.48377  75.5%     -    2s
     0     0   45.61667    0 1558  186.00000   45.61667  75.5%     -    2s
     0     0   45.61667    0 1519  186.00000   45.61667  75.5%     -    2s
     0     0   49.48966    0 1528  186.00000   49.48966  73.4%     -    3s
     0     0   50.30744    0 1504  186.00000   50.30744  73.0%     -    3s
     0     0   50.40385    0 1455  186.00000   50.40385  72.9%     -    3s
     0     0   50.40385    0 1423  186.00000   50.40385  72.9%     -    3s
     0     0   55.18750    0 1607  186.00000   55.18750  70.3%     -    4s
     0     0   56.24365    0 1639  186.00000   56.24365  69.8%     -    4s
     0     0   56.47146    0 1621  186.00000   56.47146  69.6%     -    4s
     0     0   56.57266    0 1611  186.00000   56.57266  69.6%     -    4s
     0     0   56.57266    0 1592  186.00000   56.57266  69.6%     -    4s
     0     0   61.62573    0 1618  186.00000   61.62573  66.9%     -    5s
     0     0   62.53851    0 1657  186.00000   62.53851  66.4%     -    5s
     0     0   62.97054    0 1661  186.00000   62.97054  66.1%     -    5s
     0     0   63.06712    0 1638  186.00000   63.06712  66.1%     -    5s
     0     0   63.15156    0 1625  186.00000   63.15156  66.0%     -    5s
     0     0   63.17219    0 1620  186.00000   63.17219  66.0%     -    5s
     0     0   63.17226    0 1632  186.00000   63.17226  66.0%     -    5s
     0     0   68.73321    0 1658  186.00000   68.73321  63.0%     -    6s
     0     0   69.64134    0 1663  186.00000   69.64134  62.6%     -    6s
     0     0   69.89321    0 1651  186.00000   69.89321  62.4%     -    6s
     0     0   69.89321    0 1640  186.00000   69.89321  62.4%     -    6s
     0     0   73.28547    0 1673  186.00000   73.28547  60.6%     -    7s
     0     0   74.86535    0 1725  186.00000   74.86535  59.7%     -    7s
     0     0   75.41536    0 1700  186.00000   75.41536  59.5%     -    7s
     0     0   75.48856    0 1738  186.00000   75.48856  59.4%     -    7s
     0     0   75.56115    0 1744  186.00000   75.56115  59.4%     -    8s
     0     0   75.60905    0 1721  186.00000   75.60905  59.3%     -    8s
     0     0   75.60911    0 1719  186.00000   75.60911  59.3%     -    8s
     0     0   78.41267    0 1742  186.00000   78.41267  57.8%     -    8s
H    0     0                     182.0000000   78.41267  56.9%     -    8s
     0     0   79.03921    0 1759  182.00000   79.03921  56.6%     -    8s
     0     0   79.17846    0 1733  182.00000   79.17846  56.5%     -    8s
     0     0   79.18855    0 1747  182.00000   79.18855  56.5%     -    8s
     0     0   82.02022    0 1767  182.00000   82.02022  54.9%     -    9s
     0     0   82.72740    0 1788  182.00000   82.72740  54.5%     -    9s
     0     0   82.84374    0 1807  182.00000   82.84374  54.5%     -    9s
     0     0   82.88399    0 1816  182.00000   82.88399  54.5%     -    9s
     0     0   82.89121    0 1817  182.00000   82.89121  54.5%     -    9s
     0     0   86.82260    0 1797  182.00000   86.82260  52.3%     -   10s
     0     0   87.60212    0 1800  182.00000   87.60212  51.9%     -   10s
     0     0   87.98290    0 1826  182.00000   87.98290  51.7%     -   10s
     0     0   88.04707    0 1812  182.00000   88.04707  51.6%     -   10s
     0     0   88.04959    0 1803  182.00000   88.04959  51.6%     -   10s
     0     0   90.05058    0 1778  182.00000   90.05058  50.5%     -   11s
     0     0   90.55588    0 1843  182.00000   90.55588  50.2%     -   11s
     0     0   90.66847    0 1846  182.00000   90.66847  50.2%     -   11s
     0     0   90.68162    0 1857  182.00000   90.68162  50.2%     -   11s
     0     0   92.13832    0 1820  182.00000   92.13832  49.4%     -   12s
     0     0   92.58991    0 1851  182.00000   92.58991  49.1%     -   12s
     0     0   92.63955    0 1878  182.00000   92.63955  49.1%     -   12s
     0     0   92.64927    0 1865  182.00000   92.64927  49.1%     -   12s
     0     0   94.00555    0 1797  182.00000   94.00555  48.3%     -   13s
     0     0   94.26052    0 1879  182.00000   94.26052  48.2%     -   13s
     0     0   94.41594    0 1916  182.00000   94.41594  48.1%     -   13s
     0     0   94.44913    0 1938  182.00000   94.44913  48.1%     -   14s
     0     0   94.46056    0 1924  182.00000   94.46056  48.1%     -   14s
     0     0   96.08533    0 1872  182.00000   96.08533  47.2%     -   14s
     0     0   96.41266    0 1906  182.00000   96.41266  47.0%     -   15s
     0     0   96.49846    0 1932  182.00000   96.49846  47.0%     -   15s
     0     0   96.52662    0 1941  182.00000   96.52662  47.0%     -   15s
     0     0   96.54904    0 1957  182.00000   96.54904  47.0%     -   15s
     0     0   97.86345    0 1928  182.00000   97.86345  46.2%     -   16s
     0     0   98.22289    0 1917  182.00000   98.22289  46.0%     -   16s
     0     0   98.26945    0 1959  182.00000   98.26945  46.0%     -   16s
     0     0   98.29207    0 1963  182.00000   98.29207  46.0%     -   16s
     0     0   99.18002    0 1842  182.00000   99.18002  45.5%     -   17s
     0     0   99.58633    0 1894  182.00000   99.58633  45.3%     -   17s
     0     0   99.63029    0 1887  182.00000   99.63029  45.3%     -   17s
     0     0   99.64631    0 1900  182.00000   99.64631  45.2%     -   17s
     0     0  100.24015    0 1879  182.00000  100.24015  44.9%     -   17s
     0     0  100.51862    0 1916  182.00000  100.51862  44.8%     -   18s
     0     0  100.54277    0 1897  182.00000  100.54277  44.8%     -   18s
     0     0  101.28676    0 1869  182.00000  101.28676  44.3%     -   18s
     0     0  101.33835    0 1922  182.00000  101.33835  44.3%     -   18s
     0     0  101.41159    0 1963  182.00000  101.41159  44.3%     -   19s
     0     0  101.41790    0 1953  182.00000  101.41790  44.3%     -   19s
     0     0  102.10289    0 1891  182.00000  102.10289  43.9%     -   19s
     0     0  102.22835    0 1926  182.00000  102.22835  43.8%     -   19s
     0     0  102.25029    0 1958  182.00000  102.25029  43.8%     -   19s
     0     0  102.83385    0 1877  182.00000  102.83385  43.5%     -   19s
     0     0  103.04268    0 1917  182.00000  103.04268  43.4%     -   20s
     0     0  103.08437    0 1948  182.00000  103.08437  43.4%     -   20s
     0     0  103.10241    0 1962  182.00000  103.10241  43.4%     -   20s
     0     0  104.15601    0 1881  182.00000  104.15601  42.8%     -   20s
     0     0  104.28890    0 1912  182.00000  104.28890  42.7%     -   20s
     0     0  104.36462    0 1919  182.00000  104.36462  42.7%     -   20s
     0     0  104.37265    0 1932  182.00000  104.37265  42.7%     -   20s
     0     0  104.74439    0 1940  182.00000  104.74439  42.4%     -   21s
     0     0  104.79117    0 1967  182.00000  104.79117  42.4%     -   21s
     0     0  104.81190    0 1950  182.00000  104.81190  42.4%     -   21s
     0     0  105.19260    0 1979  182.00000  105.19260  42.2%     -   21s
     0     0  105.44989    0 1998  182.00000  105.44989  42.1%     -   21s
     0     0  105.48891    0 2030  182.00000  105.48891  42.0%     -   21s
     0     0  105.49394    0 2027  182.00000  105.49394  42.0%     -   22s
     0     0  105.91556    0 1989  182.00000  105.91556  41.8%     -   22s
     0     0  105.91716    0 2007  182.00000  105.91716  41.8%     -   22s
     0     0  106.06106    0 1976  182.00000  106.06106  41.7%     -   22s
     0     0  106.06106    0 1937  182.00000  106.06106  41.7%     -   23s
     0     2  106.06106    0 1937  182.00000  106.06106  41.7%     -   24s
    64    65  112.22205   31 1571  182.00000  106.07534  41.7%  64.7   25s
H   85    86                     180.0000000  106.07534  41.1%  86.7   25s
H  115   116                     178.0000000  106.07534  40.4%  95.0   26s
H  146   146                     176.0000000  106.07534  39.7%  90.8   26s
H  216   218                     168.0000000  106.07534  36.9%   112   28s
H  224   223                     156.0000000  106.07534  32.0%   113   28s
H  227   223                     148.0000000  106.07534  28.3%   112   28s
   290   275  111.12708   18 1680  148.00000  106.09958  28.3%   111   30s
H  310   271                     144.0000000  106.09958  26.3%   116   30s
H  369   298                     138.0000000  106.09958  23.1%   115   32s
H  403   314                     136.0000000  106.09958  22.0%   114   32s
   464   374  134.68744   82  647  136.00000  106.09958  22.0%   124   36s
   550   440  113.31908   28 1607  136.00000  106.17766  21.9%   121   40s
   617   510  118.22332   44 1386  136.00000  106.17766  21.9%   121   45s
   729   611  115.90446   35 1449  136.00000  106.17766  21.9%   121   51s
   731   613  125.94652   55 1882  136.00000  119.07565  12.4%   121   55s

Cutting planes:
  Gomory: 27
  Implied bound: 556
  Clique: 3
  MIR: 413
  Flow cover: 69
  Zero half: 308

Explored 744 nodes (167016 simplex iterations) in 59.84 seconds
Thread count was 4 (of 4 available processors)

Solution count 10: 136 138 144 ... 182

Optimal solution found (tolerance 1.00e-04)
Best objective 1.360000000000e+02, best bound 1.360000000000e+02, gap 0.0000%










    

















    






About to find cycles!
Cycle length:  82
Cycle length:  36
Cycle length:  14
Cycle length:  18
Cycle length:  8
Cycle length:  76
Cycle length:  24
Cycle length:  16
Cycle length:  18
Cycle length:  10
Cycle length:  14
Cycle length:  6
Cycle length:  6
Cycle length:  20
Cycle length:  126
Cycle length:  38
Cycle length:  28
Cycle length:  24
Cycle length:  16
Optimize a model with 10571 rows, 5722 columns and 31360 nonzeros
Variable types: 0 continuous, 5722 integer (5722 binary)
Coefficient statistics:
  Matrix range     [1e+00, 2e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 2e+02]

MIP start did not produce a new incumbent solution
MIP start violates constraint R10552 by 1.000000000

Presolve removed 1762 rows and 400 columns
Presolve time: 0.19s
Presolved: 8809 rows, 5322 columns, 27230 nonzeros
Variable types: 0 continuous, 5322 integer (5322 binary)
Found heuristic solution: objective 190.0000000

Root relaxation: objective 2.300000e+01, 2345 iterations, 0.14 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0   23.00000    0 1295  190.00000   23.00000  87.9%     -    0s
H    0     0                     186.0000000   23.00000  87.6%     -    0s
     0     0   30.83333    0 1397  186.00000   30.83333  83.4%     -    1s
     0     0   30.83333    0 1392  186.00000   30.83333  83.4%     -    1s
     0     0   41.41667    0 1491  186.00000   41.41667  77.7%     -    1s
     0     0   41.83333    0 1476  186.00000   41.83333  77.5%     -    1s
     0     0   41.83333    0 1464  186.00000   41.83333  77.5%     -    1s
     0     0   45.96667    0 1559  186.00000   45.96667  75.3%     -    2s
     0     0   46.16667    0 1550  186.00000   46.16667  75.2%     -    2s
     0     0   46.25000    0 1538  186.00000   46.25000  75.1%     -    2s
     0     0   46.25000    0 1510  186.00000   46.25000  75.1%     -    2s
     0     0   48.99230    0 1586  186.00000   48.99230  73.7%     -    3s
     0     0   50.32369    0 1581  186.00000   50.32369  72.9%     -    3s
     0     0   50.73688    0 1601  186.00000   50.73688  72.7%     -    3s
     0     0   50.80417    0 1574  186.00000   50.80417  72.7%     -    3s
     0     0   50.80417    0 1574  186.00000   50.80417  72.7%     -    3s
     0     0   55.50093    0 1587  186.00000   55.50093  70.2%     -    4s
     0     0   56.65515    0 1632  186.00000   56.65515  69.5%     -    4s
     0     0   56.94382    0 1565  186.00000   56.94382  69.4%     -    4s
     0     0   56.96466    0 1553  186.00000   56.96466  69.4%     -    4s
     0     0   56.97160    0 1549  186.00000   56.97160  69.4%     -    4s
     0     0   60.32504    0 1667  186.00000   60.32504  67.6%     -    4s
     0     0   61.19412    0 1650  186.00000   61.19412  67.1%     -    5s
     0     0   61.28779    0 1647  186.00000   61.28779  67.0%     -    5s
     0     0   61.29793    0 1616  186.00000   61.29793  67.0%     -    5s
     0     0   61.31471    0 1621  186.00000   61.31471  67.0%     -    5s
     0     0   61.31471    0 1603  186.00000   61.31471  67.0%     -    5s
     0     0   65.73692    0 1680  186.00000   65.73692  64.7%     -    5s
     0     0   67.06537    0 1696  186.00000   67.06537  63.9%     -    6s
     0     0   67.28899    0 1709  186.00000   67.28899  63.8%     -    6s
     0     0   67.30984    0 1732  186.00000   67.30984  63.8%     -    6s
     0     0   67.36585    0 1709  186.00000   67.36585  63.8%     -    6s
     0     0   67.36585    0 1717  186.00000   67.36585  63.8%     -    6s
     0     0   69.73890    0 1703  186.00000   69.73890  62.5%     -    7s
H    0     0                     184.0000000   69.73890  62.1%     -    7s
     0     0   70.60021    0 1715  184.00000   70.60021  61.6%     -    7s
     0     0   70.82098    0 1688  184.00000   70.82098  61.5%     -    7s
     0     0   70.87168    0 1736  184.00000   70.87168  61.5%     -    7s
     0     0   70.91541    0 1710  184.00000   70.91541  61.5%     -    7s
     0     0   70.91568    0 1704  184.00000   70.91568  61.5%     -    7s
     0     0   75.15228    0 1656  184.00000   75.15228  59.2%     -    7s
     0     0   76.03072    0 1722  184.00000   76.03072  58.7%     -    8s
     0     0   76.08758    0 1728  184.00000   76.08758  58.6%     -    8s
     0     0   76.11735    0 1750  184.00000   76.11735  58.6%     -    8s
     0     0   76.13785    0 1756  184.00000   76.13785  58.6%     -    8s
     0     0   76.14998    0 1747  184.00000   76.14998  58.6%     -    8s
     0     0   79.86529    0 1697  184.00000   79.86529  56.6%     -    9s
     0     0   80.29573    0 1711  184.00000   80.29573  56.4%     -    9s
     0     0   80.54207    0 1758  184.00000   80.54207  56.2%     -    9s
     0     0   80.77230    0 1760  184.00000   80.77230  56.1%     -    9s
     0     0   80.83249    0 1762  184.00000   80.83249  56.1%     -    9s
     0     0   80.83940    0 1770  184.00000   80.83940  56.1%     -    9s
     0     0   83.40447    0 1692  184.00000   83.40447  54.7%     -   10s
H    0     0                     182.0000000   83.40447  54.2%     -   10s
     0     0   84.19502    0 1734  182.00000   84.19502  53.7%     -   10s
     0     0   84.33028    0 1759  182.00000   84.33028  53.7%     -   10s
     0     0   84.40180    0 1818  182.00000   84.40180  53.6%     -   10s
     0     0   84.43582    0 1817  182.00000   84.43582  53.6%     -   10s
     0     0   84.44700    0 1818  182.00000   84.44700  53.6%     -   10s
     0     0   86.48690    0 1810  182.00000   86.48690  52.5%     -   11s
     0     0   86.97941    0 1800  182.00000   86.97941  52.2%     -   11s
     0     0   87.08447    0 1785  182.00000   87.08447  52.2%     -   11s
     0     0   87.11649    0 1830  182.00000   87.11649  52.1%     -   11s
     0     0   87.13862    0 1840  182.00000   87.13862  52.1%     -   11s
     0     0   89.08758    0 1803  182.00000   89.08758  51.1%     -   12s
     0     0   89.41916    0 1893  182.00000   89.41916  50.9%     -   12s
     0     0   89.45037    0 1881  182.00000   89.45037  50.9%     -   12s
     0     0   89.46541    0 1875  182.00000   89.46541  50.8%     -   12s
     0     0   91.55074    0 1746  182.00000   91.55074  49.7%     -   12s
     0     0   92.19858    0 1842  182.00000   92.19858  49.3%     -   13s
     0     0   92.41150    0 1839  182.00000   92.41150  49.2%     -   13s
     0     0   92.42129    0 1845  182.00000   92.42129  49.2%     -   13s
     0     0   93.97558    0 1797  182.00000   93.97558  48.4%     -   13s
     0     0   94.29732    0 1853  182.00000   94.29732  48.2%     -   14s
     0     0   94.35330    0 1857  182.00000   94.35330  48.2%     -   14s
     0     0   94.38995    0 1886  182.00000   94.38995  48.1%     -   14s
     0     0   94.40343    0 1869  182.00000   94.40343  48.1%     -   14s
     0     0   95.40286    0 1839  182.00000   95.40286  47.6%     -   14s
     0     0   95.56149    0 1873  182.00000   95.56149  47.5%     -   14s
     0     0   95.58931    0 1885  182.00000   95.58931  47.5%     -   14s
     0     0   95.59246    0 1902  182.00000   95.59246  47.5%     -   14s
     0     0   96.32229    0 1819  182.00000   96.32229  47.1%     -   15s
     0     0   96.46425    0 1850  182.00000   96.46425  47.0%     -   15s
     0     0   96.47115    0 1869  182.00000   96.47115  47.0%     -   15s
     0     0   96.94064    0 1882  182.00000   96.94064  46.7%     -   15s
     0     0   97.19686    0 1907  182.00000   97.19686  46.6%     -   16s
     0     0   97.23764    0 1909  182.00000   97.23764  46.6%     -   16s
     0     0   97.25000    0 1911  182.00000   97.25000  46.6%     -   16s
     0     0   98.90910    0 1843  182.00000   98.90910  45.7%     -   16s
     0     0   99.03290    0 1895  182.00000   99.03290  45.6%     -   16s
     0     0   99.17184    0 1875  182.00000   99.17184  45.5%     -   16s
     0     0   99.20899    0 1901  182.00000   99.20899  45.5%     -   16s
     0     0   99.20950    0 1909  182.00000   99.20950  45.5%     -   16s
     0     0  100.44589    0 1850  182.00000  100.44589  44.8%     -   17s
     0     0  100.57576    0 1865  182.00000  100.57576  44.7%     -   17s
     0     0  100.59837    0 1914  182.00000  100.59837  44.7%     -   17s
     0     0  101.03230    0 1857  182.00000  101.03230  44.5%     -   17s
     0     0  101.12520    0 1869  182.00000  101.12520  44.4%     -   17s
     0     0  101.17916    0 1895  182.00000  101.17916  44.4%     -   18s
     0     0  101.18135    0 1888  182.00000  101.18135  44.4%     -   18s
     0     0  101.74847    0 1888  182.00000  101.74847  44.1%     -   18s
H    0     0                     180.0000000  101.74847  43.5%     -   18s
     0     0  101.94996    0 1893  180.00000  101.94996  43.4%     -   18s
     0     0  102.00004    0 1922  180.00000  102.00004  43.3%     -   18s
     0     0  102.00958    0 1907  180.00000  102.00958  43.3%     -   18s
     0     0  102.38764    0 1918  180.00000  102.38764  43.1%     -   19s
     0     0  102.43497    0 1918  180.00000  102.43497  43.1%     -   19s
     0     0  102.48659    0 1968  180.00000  102.48659  43.1%     -   19s
     0     0  102.49792    0 1974  180.00000  102.49792  43.1%     -   19s
     0     0  103.06565    0 1931  180.00000  103.06565  42.7%     -   19s
     0     0  103.14917    0 1924  180.00000  103.14917  42.7%     -   19s
     0     0  103.16295    0 1946  180.00000  103.16295  42.7%     -   20s
     0     0  103.44389    0 1932  180.00000  103.44389  42.5%     -   20s
     0     0  103.55577    0 1950  180.00000  103.55577  42.5%     -   20s
     0     0  103.56604    0 1963  180.00000  103.56604  42.5%     -   20s
     0     0  104.13614    0 1912  180.00000  104.13614  42.1%     -   20s
     0     0  104.27594    0 1959  180.00000  104.27594  42.1%     -   21s
     0     0  104.36329    0 1967  180.00000  104.36329  42.0%     -   21s
     0     0  104.37617    0 1961  180.00000  104.37617  42.0%     -   21s
     0     0  104.61682    0 1948  180.00000  104.61682  41.9%     -   21s
     0     0  104.64128    0 1958  180.00000  104.64128  41.9%     -   21s
     0     0  104.82274    0 1967  180.00000  104.82274  41.8%     -   21s
     0     0  104.82274    0 1942  180.00000  104.82274  41.8%     -   21s
     0     2  104.82274    0 1929  180.00000  104.82274  41.8%     -   22s
   101   104  115.05554   37 1512  180.00000  105.31550  41.5%   108   25s
H  190   188                     166.0000000  105.31550  36.6%   142   27s
H  199   201                     152.0000000  105.31550  30.7%   144   28s
H  203   205                     138.0000000  105.31550  23.7%   144   28s
H  230   228                     136.0000000  105.31550  22.6%   148   29s
   309   310  130.45942  113  893  136.00000  105.31550  22.6%   132   30s
   456   435  110.44898   26 1883  136.00000  105.56424  22.4%   128   35s
   556   537  120.43972   72 1491  136.00000  105.56424  22.4%   132   40s
   726   695  125.67779  103 1516  136.00000  105.66255  22.3%   128   47s
   728   697  129.52224   83 1748  136.00000  119.98941  11.8%   127   50s

Cutting planes:
  Gomory: 23
  Implied bound: 614
  MIR: 441
  Flow cover: 57
  Zero half: 262

Explored 735 nodes (176001 simplex iterations) in 54.57 seconds
Thread count was 4 (of 4 available processors)

Solution count 9: 136 138 152 ... 190

Optimal solution found (tolerance 1.00e-04)
Best objective 1.360000000000e+02, best bound 1.360000000000e+02, gap 0.0000%










    

















    






About to find cycles!
Cycle length:  62
Cycle length:  36
Cycle length:  14
Cycle length:  32
Cycle length:  28
Cycle length:  20
Cycle length:  6
Cycle length:  8
Cycle length:  50
Cycle length:  34
Cycle length:  8
Cycle length:  82
Cycle length:  6
Cycle length:  56
Cycle length:  38
Cycle length:  26
Cycle length:  34
Cycle length:  36
Cycle length:  4
Optimize a model with 10590 rows, 5722 columns and 31940 nonzeros
Variable types: 0 continuous, 5722 integer (5722 binary)
Coefficient statistics:
  Matrix range     [1e+00, 2e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 2e+02]

MIP start did not produce a new incumbent solution
MIP start violates constraint R10571 by 1.000000000

Presolve removed 1747 rows and 393 columns
Presolve time: 0.19s
Presolved: 8843 rows, 5329 columns, 27791 nonzeros
Variable types: 0 continuous, 5329 integer (5329 binary)
Found heuristic solution: objective 190.0000000

Root relaxation: objective 2.300000e+01, 2424 iterations, 0.16 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0   23.00000    0 1245  190.00000   23.00000  87.9%     -    0s
H    0     0                     186.0000000   23.00000  87.6%     -    0s
     0     0   32.83333    0 1449  186.00000   32.83333  82.3%     -    1s
     0     0   33.33333    0 1457  186.00000   33.33333  82.1%     -    1s
     0     0   41.66667    0 1521  186.00000   41.66667  77.6%     -    2s
     0     0   42.50000    0 1493  186.00000   42.50000  77.2%     -    2s
     0     0   42.50000    0 1493  186.00000   42.50000  77.2%     -    2s
     0     0   43.61667    0 1578  186.00000   43.61667  76.6%     -    2s
     0     0   43.86667    0 1535  186.00000   43.86667  76.4%     -    2s
     0     0   43.86667    0 1519  186.00000   43.86667  76.4%     -    2s
     0     0   48.82738    0 1588  186.00000   48.82738  73.7%     -    3s
     0     0   50.24306    0 1561  186.00000   50.24306  73.0%     -    3s
     0     0   50.38750    0 1555  186.00000   50.38750  72.9%     -    3s
     0     0   50.38750    0 1545  186.00000   50.38750  72.9%     -    3s
     0     0   55.60417    0 1592  186.00000   55.60417  70.1%     -    4s
     0     0   57.08942    0 1629  186.00000   57.08942  69.3%     -    4s
     0     0   57.35378    0 1626  186.00000   57.35378  69.2%     -    4s
     0     0   57.46306    0 1602  186.00000   57.46306  69.1%     -    4s
     0     0   57.49228    0 1586  186.00000   57.49228  69.1%     -    4s
     0     0   57.49456    0 1581  186.00000   57.49456  69.1%     -    4s
     0     0   64.21497    0 1644  186.00000   64.21497  65.5%     -    5s
     0     0   65.30225    0 1658  186.00000   65.30225  64.9%     -    5s
     0     0   65.52372    0 1638  186.00000   65.52372  64.8%     -    5s
     0     0   65.81056    0 1649  186.00000   65.81056  64.6%     -    5s
     0     0   65.87941    0 1633  186.00000   65.87941  64.6%     -    5s
     0     0   65.87941    0 1624  186.00000   65.87941  64.6%     -    5s
     0     0   69.66329    0 1679  186.00000   69.66329  62.5%     -    6s
H    0     0                     182.0000000   69.66329  61.7%     -    6s
     0     0   70.47821    0 1710  182.00000   70.47821  61.3%     -    6s
     0     0   70.80717    0 1652  182.00000   70.80717  61.1%     -    6s
     0     0   70.93220    0 1681  182.00000   70.93220  61.0%     -    6s
     0     0   70.93905    0 1653  182.00000   70.93905  61.0%     -    6s
     0     0   73.97577    0 1689  182.00000   73.97577  59.4%     -    7s
     0     0   74.68184    0 1727  182.00000   74.68184  59.0%     -    7s
     0     0   75.05625    0 1707  182.00000   75.05625  58.8%     -    7s
     0     0   75.11377    0 1672  182.00000   75.11377  58.7%     -    7s
     0     0   75.11819    0 1693  182.00000   75.11819  58.7%     -    7s
     0     0   78.08474    0 1710  182.00000   78.08474  57.1%     -    7s
     0     0   78.27043    0 1754  182.00000   78.27043  57.0%     -    8s
     0     0   78.41155    0 1742  182.00000   78.41155  56.9%     -    8s
     0     0   78.41808    0 1758  182.00000   78.41808  56.9%     -    8s
     0     0   80.78706    0 1760  182.00000   80.78706  55.6%     -    8s
     0     0   81.79490    0 1758  182.00000   81.79490  55.1%     -    8s
     0     0   81.99589    0 1773  182.00000   81.99589  54.9%     -    9s
     0     0   82.03965    0 1756  182.00000   82.03965  54.9%     -    9s
     0     0   82.05059    0 1747  182.00000   82.05059  54.9%     -    9s
     0     0   83.12913    0 1753  182.00000   83.12913  54.3%     -    9s
     0     0   83.89541    0 1713  182.00000   83.89541  53.9%     -    9s
     0     0   83.99911    0 1778  182.00000   83.99911  53.8%     -    9s
     0     0   84.08697    0 1783  182.00000   84.08697  53.8%     -   10s
     0     0   84.10622    0 1778  182.00000   84.10622  53.8%     -   10s
     0     0   85.63517    0 1753  182.00000   85.63517  52.9%     -   10s
H    0     0                     180.0000000   85.63517  52.4%     -   10s
     0     0   85.94451    0 1749  180.00000   85.94451  52.3%     -   10s
     0     0   86.02761    0 1800  180.00000   86.02761  52.2%     -   10s
     0     0   86.06382    0 1815  180.00000   86.06382  52.2%     -   10s
     0     0   86.12650    0 1779  180.00000   86.12650  52.2%     -   10s
     0     0   86.13198    0 1808  180.00000   86.13198  52.1%     -   11s
     0     0   87.79804    0 1809  180.00000   87.79804  51.2%     -   11s
     0     0   88.10012    0 1848  180.00000   88.10012  51.1%     -   11s
     0     0   88.26949    0 1818  180.00000   88.26949  51.0%     -   11s
     0     0   88.29270    0 1842  180.00000   88.29270  50.9%     -   11s
     0     0   88.29497    0 1842  180.00000   88.29497  50.9%     -   11s
     0     0   89.24422    0 1750  180.00000   89.24422  50.4%     -   12s
     0     0   89.74110    0 1749  180.00000   89.74110  50.1%     -   12s
     0     0   89.98241    0 1781  180.00000   89.98241  50.0%     -   12s
     0     0   90.09622    0 1796  180.00000   90.09622  49.9%     -   12s
     0     0   90.11302    0 1798  180.00000   90.11302  49.9%     -   12s
     0     0   91.48870    0 1769  180.00000   91.48870  49.2%     -   12s
     0     0   91.76852    0 1843  180.00000   91.76852  49.0%     -   13s
     0     0   91.81990    0 1823  180.00000   91.81990  49.0%     -   13s
     0     0   91.84187    0 1812  180.00000   91.84187  49.0%     -   13s
     0     0   92.53131    0 1823  180.00000   92.53131  48.6%     -   13s
     0     0   92.91106    0 1842  180.00000   92.91106  48.4%     -   13s
     0     0   92.98330    0 1848  180.00000   92.98330  48.3%     -   13s
     0     0   93.06453    0 1853  180.00000   93.06453  48.3%     -   14s
     0     0   93.07854    0 1860  180.00000   93.07854  48.3%     -   14s
     0     0   93.87454    0 1829  180.00000   93.87454  47.8%     -   14s
     0     0   93.99055    0 1866  180.00000   93.99055  47.8%     -   14s
     0     0   94.08555    0 1893  180.00000   94.08555  47.7%     -   14s
     0     0   94.10820    0 1889  180.00000   94.10820  47.7%     -   14s
     0     0   94.53266    0 1859  180.00000   94.53266  47.5%     -   14s
     0     0   94.85447    0 1879  180.00000   94.85447  47.3%     -   15s
     0     0   94.96478    0 1903  180.00000   94.96478  47.2%     -   15s
     0     0   94.98454    0 1917  180.00000   94.98454  47.2%     -   15s
     0     0   96.12107    0 1875  180.00000   96.12107  46.6%     -   15s
     0     0   96.25364    0 1895  180.00000   96.25364  46.5%     -   15s
     0     0   96.32035    0 1921  180.00000   96.32035  46.5%     -   15s
     0     0   96.35027    0 1896  180.00000   96.35027  46.5%     -   15s
     0     0   96.35522    0 1936  180.00000   96.35522  46.5%     -   16s
     0     0   97.23579    0 1857  180.00000   97.23579  46.0%     -   16s
     0     0   97.41812    0 1944  180.00000   97.41812  45.9%     -   16s
     0     0   97.45828    0 1957  180.00000   97.45828  45.9%     -   16s
     0     0   97.46833    0 1969  180.00000   97.46833  45.9%     -   16s
     0     0   98.36646    0 1907  180.00000   98.36646  45.4%     -   16s
     0     0   98.54629    0 1943  180.00000   98.54629  45.3%     -   17s
     0     0   98.57605    0 1944  180.00000   98.57605  45.2%     -   17s
     0     0   98.57932    0 1950  180.00000   98.57932  45.2%     -   17s
     0     0   98.81069    0 1903  180.00000   98.81069  45.1%     -   17s
     0     0   98.92739    0 1938  180.00000   98.92739  45.0%     -   17s
     0     0   98.95922    0 1958  180.00000   98.95922  45.0%     -   17s
     0     0   98.98171    0 1974  180.00000   98.98171  45.0%     -   17s
     0     0   99.33430    0 1969  180.00000   99.33430  44.8%     -   18s
     0     0   99.44724    0 1978  180.00000   99.44724  44.8%     -   18s
     0     0   99.47243    0 2001  180.00000   99.47243  44.7%     -   18s
     0     0   99.60433    0 1934  180.00000   99.60433  44.7%     -   18s
     0     0   99.60433    0 1912  180.00000   99.60433  44.7%     -   18s
     0     2   99.60433    0 1884  180.00000   99.60433  44.7%     -   19s
     3     6   99.92340    2 1950  180.00000   99.92340  44.5%   317   20s
   104   106  109.51166   32 1667  180.00000  100.19903  44.3%   219   25s
H  145   142                     178.0000000  100.19903  43.7%   198   26s
   293   295  124.63445   89 1225  178.00000  100.19903  43.7%   176   30s
H  357   356                     176.0000000  100.19903  43.1%   170   31s
H  385   385                     158.0000000  100.19903  36.6%   173   32s
H  390   389                     156.0000000  100.19903  35.8%   174   32s
H  423   418                     144.0000000  100.19903  30.4%   175   34s
H  450   421                     142.0000000  100.19903  29.4%   168   34s
   467   435     cutoff  153       142.00000  100.37950  29.3%   167   35s
H  480   411                     138.0000000  100.39718  27.2%   173   35s
   569   502  109.71247   45 1823  138.00000  100.39718  27.2%   174   40s
H  625   537                     136.0000000  100.39718  26.2%   180   42s
   745   658  133.58955  114 1912  136.00000  100.39718  26.2%   178   47s
   748   660  105.00869   16 1717  136.00000  101.32872  25.5%   178   51s
   756   665  132.73455   55  964  136.00000  132.73455  2.40%   176   56s

Cutting planes:
  Gomory: 18
  Implied bound: 654
  Clique: 3
  MIR: 407
  Flow cover: 53
  Zero half: 209

Explored 757 nodes (206012 simplex iterations) in 56.90 seconds
Thread count was 4 (of 4 available processors)

Solution count 10: 136 138 142 ... 182

Optimal solution found (tolerance 1.00e-04)
Best objective 1.360000000000e+02, best bound 1.360000000000e+02, gap 0.0000%










    

















    






About to find cycles!
Cycle length:  82
Cycle length:  60
Cycle length:  86
Cycle length:  6
Cycle length:  26
Cycle length:  14
Cycle length:  14
Cycle length:  10
Cycle length:  28
Cycle length:  148
Cycle length:  78
Cycle length:  24
Cycle length:  4
Optimize a model with 10603 rows, 5722 columns and 32520 nonzeros
Variable types: 0 continuous, 5722 integer (5722 binary)
Coefficient statistics:
  Matrix range     [1e+00, 2e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 2e+02]

MIP start did not produce a new incumbent solution
MIP start violates constraint R10590 by 1.000000000

Presolve removed 1762 rows and 400 columns
Presolve time: 0.21s
Presolved: 8841 rows, 5322 columns, 28275 nonzeros
Variable types: 0 continuous, 5322 integer (5322 binary)
Found heuristic solution: objective 190.0000000

Root relaxation: objective 2.300000e+01, 2482 iterations, 0.23 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0   23.00000    0 1319  190.00000   23.00000  87.9%     -    1s
     0     0   32.00000    0 1474  190.00000   32.00000  83.2%     -    1s
H    0     0                     186.0000000   32.00000  82.8%     -    1s
     0     0   32.00000    0 1443  186.00000   32.00000  82.8%     -    1s
     0     0   40.58333    0 1533  186.00000   40.58333  78.2%     -    2s
     0     0   40.83333    0 1530  186.00000   40.83333  78.0%     -    2s
     0     0   40.83333    0 1513  186.00000   40.83333  78.0%     -    2s
     0     0   44.21667    0 1525  186.00000   44.21667  76.2%     -    3s
     0     0   44.71667    0 1507  186.00000   44.71667  76.0%     -    3s
     0     0   44.71667    0 1476  186.00000   44.71667  76.0%     -    3s
     0     0   47.50060    0 1566  186.00000   47.50060  74.5%     -    3s
     0     0   49.42857    0 1563  186.00000   49.42857  73.4%     -    4s
     0     0   49.45635    0 1519  186.00000   49.45635  73.4%     -    4s
     0     0   49.47321    0 1495  186.00000   49.47321  73.4%     -    4s
     0     0   49.47387    0 1495  186.00000   49.47387  73.4%     -    4s
     0     0   53.74146    0 1583  186.00000   53.74146  71.1%     -    4s
     0     0   55.22821    0 1566  186.00000   55.22821  70.3%     -    5s
     0     0   55.76042    0 1552  186.00000   55.76042  70.0%     -    5s
     0     0   55.87282    0 1531  186.00000   55.87282  70.0%     -    5s
     0     0   55.88872    0 1523  186.00000   55.88872  70.0%     -    5s
     0     0   55.88872    0 1519  186.00000   55.88872  70.0%     -    5s
     0     0   59.57333    0 1632  186.00000   59.57333  68.0%     -    5s
     0     0   60.45496    0 1668  186.00000   60.45496  67.5%     -    5s
     0     0   60.55501    0 1647  186.00000   60.55501  67.4%     -    6s
     0     0   60.57496    0 1642  186.00000   60.57496  67.4%     -    6s
     0     0   60.58351    0 1624  186.00000   60.58351  67.4%     -    6s
     0     0   64.86231    0 1644  186.00000   64.86231  65.1%     -    6s
     0     0   65.59814    0 1684  186.00000   65.59814  64.7%     -    6s
     0     0   65.91699    0 1671  186.00000   65.91699  64.6%     -    6s
     0     0   66.05546    0 1675  186.00000   66.05546  64.5%     -    6s
     0     0   66.08626    0 1648  186.00000   66.08626  64.5%     -    7s
     0     0   66.11007    0 1653  186.00000   66.11007  64.5%     -    7s
     0     0   66.11119    0 1655  186.00000   66.11119  64.5%     -    7s

















In [ ]:



    


plot_tsp_solution(flat_tiles, location_edges, row_count=len(tiles), col_count=len(tiles[0]))



    











In [ ]:

Content source: jcbozonier/research

Similar notebooks:

notebook.community | gallery | about