Working with large models

Question

I am working with a variant of TSP, number of nodes that I need to test are in between 2500 to 3000 nodes, I am using docplex for modelling, I have a 8 gb Ram but it gets filled with only 400 nodes.

for 100 nodes, there are 2280 constraints and 408100 indicator and if_then constraints.

for 200 nodes, there are 4480 constraints and 1616200 indicator and if_then constraints. (Maybe my model is not optimal.)

How to handle large models? I am looking for techniques available to solve or optimize large models.

My Model:

problem: there are $m$ cars they need to deliver goods at $n$ nodes, each car has goods and they give some % of there goods to these delivery points multiple cars can deliver at same point.

example 2 cars 3 delivery points

car 1 can deliver 0.4 goods at p1, 0.6 at p2

car 2 can deliver 0.6 goods at p1, 0.4 at p2

so p1 and p2 has 1 (represent it as T) they are full filled but p3 has none. If car has no goods left it comes back at start point.

variables:

$x_{i,j,k}$ - car k take edge i,j. (binary)

$d_{i}$ - delivery point i requirement full filled. (binary)

$G_{i,k}$ - goods car k has left at node i. (continuous $\in [0,1]$ )

$DG_{i,k}$ - amount of goods gained by node i from car k. (continuous $\in [0,1] $)

$A_{i,k}$ - arrival time of car k at node i.

objective:

start node is excluded.

$$max. \sum_{i}^{n} d_i$$

constraint

$$\sum_{j}^{n} x_{j,i,k} - \sum_{j}^{n} x_{i,j,k}=0 \text{, incoming node - outgoing node = 0}$$

$$\sum_{j}^{n} x_{j,0,k} = 1 \text{, for start point 1 incoming}$$ $$\sum_{j}^{n} x_{0,j,k} = 1 \text{, for start point 1 outgoing}$$

$$A_{0,k} = 0 \text{, initialise arrival time at start to 0 }$$ $$G_{0,k} = 1 \text{, initialise total goods at start to 100%}$$

$$x_{i,j,k} -> A_{j,k} = A_{i,k}+X $$ if i,j edge is taken ($x_{i,j,k} = 1$) so arrival time at j is arrival time at i + X, X is constant (also removes sub tours).

$$x_{i,j,k} -> G_{j,k} = G_{i,k} - DG_{j,k} - Y $$

if i,j edge is taken ($x_{i,j,k} = 1$) so goods at j is reduced by goods at i - goods gain by node at j, Y is constant.

$$\sum_{j}^{n} x_{j,i,k} = 0 -> DG_{i,k} = 0 $$

if there is no visit to node i then charge gain at node i is 0.

Referring to @robpratt answer here If else condition to MILP

$$T*d_{j} \leq Z+\sum_{k}^{m}DG_{j,k} \leq (T-0.0001) * (1-d_{j}) + T*d_{j}$$

above equation means if charge gain at node j from all cars to equal to threshold (T) then $d_{j}$ is 1

$$d_{i} = 0 -> \sum_{j}^{n} x_{j,i,k} = 0 $$

means if we can not deliver goods to i don't visit i.

docplex has methods such as add_indicator and add_if_then so I have not linearized there constraints.

Above formulation works for small nodes 10-20 how do I improve this model so that it can be tested with large number of nodes.

Answer 1

Please have a look at our answer to a previous post about modeling and solving TSP by using LocalSolver: How to model a TSP where the salesman can choose between flight, train and bus for every single connection?

Your problem can be modeled differently from the one you proposed above by following a list-based modeling approach instead of the classical Boolean modeling approach. This is a modeling approach offered by LocalSolver, which is different from traditional MILP solvers. Note that LocalSolver is commercial software. Nevertheless, it is free for faculty and students.

Below is the code snippet to model the classical TSP problem in Python:

    # Open the optimization model
    model = ls.model

    # List variable: cities[i] is the index of the ith city in the tour
    cities = model.list(nb_cities) 

    # Constraint: all cities must be visited
    model.constraint(model.count(cities) == nb_cities)

    # Array to store the distance matrix
    distance_array = model.array(distance_weight)

    # Objective: minimize the total traveled distance
    dist_selector = model.lambda_function(
        lambda i: model.at(distance_array, cities[i-1], cities[i]))
    obj = (model.sum(model.range(1, nb_cities), dist_selector)
        + model.at(distance_array, cities[nb_cities - 1], cities[0]))
    model.minimize(obj)

    # Close the optimization model
    model.close()

The complete code and the corresponding codes for Java, C#, and C++ are given here: https://www.localsolver.com/docs/last/exampletour/tsp.html.

Having followed this modeling approach, LocalSolver finds quality solutions (optimality gap less than 1%) in a few minutes on a standard computer for TSP or VRP instances and problem variants like CVRP, CVRTW, SDVRP, PDPTW, with thousands of customers to visit. LocalSolver embeds and combines neighborhood search, constraint programming, and mixed-integer linear programming techniques under the hood to get such results.

For an introduction to the list-based modeling approach for combinatorial optimization, have a look at https://www.localsolver.com/docs/last/advancedfeatures/collectionvariables.html.