Python mip can not start due to memory buildup

[NguyenS-Crypto]

Hi, I am solving the vehicle capacitated route problem to find the optimized route for a network with a depot and over 40 locations. At the beginning, I start with 20 locations and python mip work fine. Netx, i increase the number of location to 40, python mip can not start to solve the problem. I got the message zhs: killed ..... I rerun the python script and check the monitor, the memory build up quite fast for the process named python3.9 before crashing. Can anyone can explain the reason and how to solve it? many thanks!

[christian2022]

If you want help, you need to provide more details. For example send your model or script.

[NguyenS-Crypto]

Hi @christian2022 , My code is: from mip import *

df = input_data(path_excel, sheet_name, df_depot) df = check_demand(df) distances = get_distance(df)

from sys import stdout as out from itertools import product

parameters from other functions

points, demands = len(df), df['demand'].values

set problem

Obj = Model()

Set variables

x = [[Obj.add_var(var_type=BINARY, lb=0, ub=1) for j in range(points)] for i in range(points)]

n_route = Obj.add_var(var_type=INTEGER, lb=0, ub=100)

set objective function

Obj.objective = minimize(xsum(distances[i][j] * x[i][j] for i in range(points) for j in range(points)))

set contrains

for i in range(points): Obj += x[i][i] == 0 if demands[i] >= 45.0: Obj += x[0][i] == 1 Obj += x[i][0] == 1

Vehicle must enter to location to start service and leave it after service

for i in range(1, points): Obj += xsum(x[j][i] for j in range(points)) == 1 Obj += xsum(x[i][j] for j in range(points)) == 1

Vehicle must start from depot and return to depot

Obj += xsum(x[i][0] for i in range(points)) == n_route Obj += xsum(x[0][i]for i in range(points)) == n_route

Eliminate subtours

subtours = [] # create an empty list for length in range(2, points): subtours += itertools.combinations(range(1, points), length) for st in subtours: demand = np.sum([demands[s] for s in st]) arcs = [x[i][j] for i, j in itertools.permutations(st, 2)] Obj += xsum(arcs) <= np.max([0, len(st) - np.ceil(demand / VCap)])

Obj.write('model.lp') Obj.optimize(max_seconds=500, relax=True)

nvehicles = n_route.x n_vehicles_r = np.ceil(((Obj.objective_value)/50 + nvehicles*2)/10)

print output

print('Solutions is: \t{} \nObjective function is: \t{:.1f}'.format(Obj.status, Obj.objective_value)) print('Total number of delivery turn is: \t', nvehicles) print('Minimum required number of vehicles is: \t', n_vehicles_r)

can you please help. many thanks

[christian2022]

Do yourself and especially the ones that are willing to help a favor and post complete examples, including data. Read the help how you can post code (and not text), e.g.

from mip import *

df = input_data(path_excel, sheet_name, df_depot)
df = check_demand(df)
distances = get_distance(df)

from sys import stdout as out
from itertools import product

Exercise to understand your problem:

for length in range(2, points):
    subtours += itertools.combinations(range(1, points), length)
for st in subtours:
    demand = np.sum([demands[s] for s in st])
    arcs = [x[i][j] for i, j in itertools.permutations(st, 2)]

How many arcs do you create depending on points? Draw a plot.

Then look into the tsp example in python-mip's examples forlder for how to generate lazy constraints.

[NguyenS-Crypto]

Hi @christian2022 , thank you for your very kind support. I am so sorry due to my bad experience with github. I attach the data file for the problem: data.csv Here below my code:

import numpy as np
import pandas as pd
from scipy.spatial import distance_matrix
from mip import Model, minimize, xsum, BINARY, INTEGER
import itertools

# create a function to calculate the distance
def get_distance(df):
    # create a copy of df
    df_copy = df.copy()
    # Convert degree to radian
    df_copy['lat'] = np.radians(df_copy['lat'])
    df_copy['long'] = np.radians(df_copy['long'])
    # Earth radius
    r_earth = 6378.0;
    # Get distance matrix
    distances = (pd.DataFrame(distance_matrix(df_copy[['lat', 'long']].values, df_copy[['lat', 'long']].values), index=df_copy.index, columns=df_copy.index) * r_earth).values
    return distances

# input_data
VCap = 50 # vehicle capacity
df = pd.read_csv('data.csv')
distances = get_distance(df)

# parameters
points, demands = len(df), df['demand'].values

# set problem
Obj = Model()

# Set variables
x = [[Obj.add_var(var_type=BINARY, lb=0, ub=1) for j in range(points)] for i in range(points)]
n_route = Obj.add_var(var_type=INTEGER, lb=0, ub=100)

# set objective function
Obj.objective = minimize(xsum(distances[i][j] * x[i][j] for i in range(points) for j in range(points)))

# set contrains
for i in range(points):
    Obj += x[i][i] == 0
    if demands[i] >= 45.0:
        Obj += x[0][i] == 1
        Obj += x[i][0] == 1

# Vehicle must enter to location to start service and leave it after service
for i in range(1, points):
    Obj += xsum(x[j][i] for j in range(points)) == 1
    Obj += xsum(x[i][j] for j in range(points)) == 1

# Vehicle must start from depot and return to depot
Obj += xsum(x[i][0] for i in range(points)) == n_route
Obj += xsum(x[0][i]for i in range(points)) == n_route

# Eliminate subtours
subtours = [] # create an empty list
for length in range(2, points):
    subtours += itertools.combinations(range(1, points), length)
for st in subtours:
    demand = np.sum([demands[s] for s in st])
    arcs = [x[i][j] for i, j in itertools.permutations(st, 2)]
    Obj += xsum(arcs) <= np.max([0, len(st) - np.ceil(demand / VCap)])

# write lp problem to disk
Obj.write('model.lp')

# solve the problem
Obj.optimize()

# for reporting
n_vehicles_ = n_route.x
n_vehicles_r = np.ceil(((Obj.objective_value)/50 + n_vehicles_*2)/10)

# print output
print('Solutions is: \t{} \nObjective function is: \t{:.1f}'.format(Obj.status, Obj.objective_value))
print('Total number of delivery turn is: \t', n_route.x)
print('Minimum required number of vehicles is: \t', n_vehicles_r)

Can you please review it once again, Christian? many thanks for your previous comment, now I know how to post a code block.

[christian2022]

Please complete the exercise I gave above. How many arcs do you have for points in range(40)?

When you understand what happens there read the documentation about lazy constraints and lookup the tsp example.

[NguyenS-Crypto]

Please complete the exercise I gave above. How many arcs do you have for points in range(40)?

When you understand what happens there read the documentation about lazy constraints and lookup the tsp example.

It was clear why my code did not work and memory dump. The problem happened due to itertools.permutations can not finish with a large number of node. with 40 nodes, the arcs by itertools would be 40! or 8.1591528e+47. many thank Christian, it's a great lesson for me. I have visited the tsp in mip examples and trying to figure out how to include the capacity constraint for my problem. I highly appreciate if you can give me some instruction? thank you

[christian2022]

Welcome to the world of combinatorial explosion.

To solve your problem: keep all the constraints you have except for the subtour eliminations. Add a subclass of constr_generator that identifies subtours in a given solution and adds the constraints to the model. How to do this can be seen in the tsp lazy example.

This way you only add the relevant subtour elimination out of the combinatorial many. Key is an efficient routine for identifying those. But don't expect wonders. You are solving the vehicle routing problem, which is known to be NP hard.

[NguyenS-Crypto]

Welcome to the world of combinatorial explosion.

To solve your problem: keep all the constraints you have except for the subtour eliminations. Add a subclass of constr_generator that identifies subtours in a given solution and adds the constraints to the model. How to do this can be seen in the tsp lazy example.

This way you only add the relevant subtour elimination out of the combinatorial many. Key is an efficient routine for identifying those. But don't expect wonders. You are solving the vehicle routing problem, which is known to be NP hard.

Many thanks @christian2022. the isssue has been solved.