maximizing number of nodes with max_distance constraint

[hiramf]

I would like my objective to be maximizing the number of nodes in a route while not exceeding a fixed distance. However, I can't seem to figure out how make my route contiguous. I get a route with length of 3 and 2 routes that are one arc long.

Using the example from the documentation for the TSP, I have tried setting the objective to:

m.objective = maximize(xsum(x[(i,j)] for (i,j) in arcs))

and adding the constraint:

m.add_constr( 
    xsum(distance_matrix[i][j] * x[(i,j)] for (i,j) in arcs) <= max_distance,
    "max_distance"
)

Here is my full code:

from itertools import product
from mip import Model, xsum, BINARY, INTEGER
from mip import maximize, CBC, minimize
from sys import stdout as out

N = ['Antwerp', 'Bruges', 'C-Mine', 'Dinant', 'Ghent',
          'Grand-Place de Bruxelles', 'Hasselt', 'Leuven',
          'Mechelen', 'Mons', 'Montagne de Bueren', 'Namur',
          'Remouchamps', 'Waterloo']

n, V = len(N), set(range(len(N)))
arcs = [(i, j) for i in V for j in V]

# distances in an upper triangular matrix
dists = [[83, 81, 113, 52, 42, 73, 44, 23, 91, 105, 90, 124, 57],
         [161, 160, 39, 89, 151, 110, 90, 99, 177, 143, 193, 100],
         [90, 125, 82, 13, 57, 71, 123, 38, 72, 59, 82],
         [123, 77, 81, 71, 91, 72, 64, 24, 62, 63],
         [51, 114, 72, 54, 69, 139, 105, 155, 62],
         [70, 25, 22, 52, 90, 56, 105, 16],
         [45, 61, 111, 36, 61, 57, 70],
         [23, 71, 67, 48, 85, 29],
         [74, 89, 69, 107, 36],
         [117, 65, 125, 43],
         [54, 22, 84],
         [60, 44],
         [97],
         []]

# distances matrix
distance_matrix = [[0 if i == j
      else dists[i][j-i-1] if j > i
      else dists[j][i-j-1]
      for j in V] for i in V]

max_distance = 100
# max_distance = None

m = Model(solver_name=CBC)
m.verbose = 1

x = {
    arc: m.add_var(name="x{0}".format(arc), var_type=BINARY)
    for arc in arcs
}

if max_distance:
    m.objective = maximize(xsum(x[(i,j)] for (i,j) in arcs))
    # visit each  node no more than once
    for i in V:
        m += xsum(x[(j,i)] for j in V - {i} ) <= 1
        m += xsum(x[(i,j)] for j in V - {i} ) <= 1 
        m += x[(i,i)] == 0 # don't visit yourself

    m.add_constr( 
        xsum(distance_matrix[i][j] * x[(i,j)] for (i,j) in arcs) <= max_distance,
        "max_distance"
    )

else:
    m.objective = minimize(xsum(distance_matrix[i][j] * x[(i,j)] for (i,j) in arcs))
    # visit each node only once
    for i in V:
        m += xsum(x[(j,i)] for j in V - {i}) == 1 # enter
        m += xsum(x[(i,j)] for j in V - {i}) == 1 # leave

# # continuous variable to prevent subtours: each city will have a
# # different sequential id in the planned route except the first one
y = {i: m.add_var(name="y({})".format(i), lb=0.0) for i in V}

# # (weak) subtour elimination
# # subtour elimination
for (i, j) in product(V - {0}, V - {0}):
    if i != j:
        m += y[i] - (n+1)*x[(i,j)] >= y[j]-n

# constraint: don't allow subtours of size 2
for (i, j) in arcs:
    m += x[(i,j)] + x[(j,i)] <= 1

m.optimize()

if m.num_solutions:
    print(sum(distance_matrix[i][j] * x[(i,j)].x for (i,j) in arcs)) #total distance
    out.write('route with objective value %g found: %s'
              % (m.objective_value, N[0]))
    nc = 0
    while True:
        nc = [i for i in V if x[(i, nc)].x >= 0.99][0]
        out.write(' -> %s' % N[nc])
        if nc == 0:
            break
    out.write('\n')

else:
    out.write('No solution found.')

[sebheger]

Hi @hiramf, do you want to report any bug or strange behavior with your example? Otherwise, I will close this issues as we do not offer support for pure modeling questions.

[rschwarz]

Help with modeling questions is, however, available at the OR StackExchange.