My model does not find a single solution, even if the time limit is set to high numbers.
Answered
Hello, i am currently trying to solve a MILP for a HCVRP in python. My MILP model is not infeasible but does not provide a solution, even if there are only 25 nodes. I am trying to find out whats wrong, however I have been unable to find out what is wrong, I hope someone can help me!
This is my model and the input data:
import numpy as np
from gurobipy import Model, GRB, quicksum
import pandas as pd
import os
def define_variables(distance_matrix_dict, num_vehicles, capacity_dict, demand_list, vehicle_types):
n = len(demand_list) # number of clients
N = [i for i in range(1, n)] # set of clients
V = [i for i in range(n)] # set of clients plus the depot (depot is 0)
A = [(i, j) for i in V for j in V if i != j] # set of arcs connecting different locations
total_vehicles_needed = num_vehicles
c = {(i, j, k): distance_matrix_dict[vehicle_types[k]][i][j] for i, j in A for k in range(total_vehicles_needed)}
Q = {k: capacity_dict[vehicle_types[k]] for k in range(total_vehicles_needed)}
q = {i: demand_list[i] for i in N}
mdl = Model("CVRP")
mdl.Params.Presolve = 2
mdl.Params.NoRelHeurTime = 2.0 # Setting the NoRelHeurTime parameter
x = mdl.addVars(A, range(total_vehicles_needed), vtype=GRB.BINARY)
u = mdl.addVars(N, range(total_vehicles_needed), vtype=GRB.CONTINUOUS)
mdl.modelSense = GRB.MINIMIZE
mdl.setObjective(quicksum(x[i, j, k] * c[i, j, k] for (i, j) in A for k in range(total_vehicles_needed)))
for i in N:
mdl.addConstr(quicksum(x[i, j, k] for j in V if j != i for k in range(total_vehicles_needed)) >= 1, name="VisitOnceFrom_{}".format(i))
for j in N:
mdl.addConstr(quicksum(x[i, j, k] for i in V if i != j for k in range(total_vehicles_needed)) >= 1, name="VisitOnceTo_{}".format(j))
for i in N:
for k in range(total_vehicles_needed):
# If customer demand is more than vehicle capacity, disallow that vehicle for the customer
if q[i] > Q[k]:
mdl.addConstr(quicksum(x[i, j, k] for j in V if j != i) == 0, name="VehicleCapacityDemandCheck_{}_{}".format(i, k))
for i, j in A:
if i != 0 and j != 0:
for k in range(total_vehicles_needed):
mdl.addConstr(u[j, k] - u[i, k] + Q[k] * (1 - x[i, j, k]) >= q[j], name="LoadAfterVisit_{}_{}_{}".format(i, j, k))
mdl.addConstr(u[j, k] - u[i, k] <= Q[k] * (1 - x[i, j, k]) + q[j], name="LoadAfterVisitUB_{}_{}_{}".format(i, j, k))
for i in N:
for k in range(total_vehicles_needed):
if q[i] <= Q[k]: # Only create a constraint if the vehicle can potentially serve the client.
mdl.addConstr(u[i, k] >= q[i], name="LoadGEQDemand_{}_{}".format(i, k))
mdl.addConstr(u[i, k] <= Q[k], name="LoadLEQCapacity_{}_{}".format(i, k))
for k in range(total_vehicles_needed):
mdl.addConstr(quicksum(q[i] * x[i, j, k] for i in N for j in V if i != j) <= Q[k], name="Capacity_{}".format(k))
for k in range(total_vehicles_needed):
mdl.addConstr(quicksum(x[0, i, k] for i in V if i != 0) == 1, name="VehicleLeavesDepot_{}".format(k))
for i in N:
for k in range(total_vehicles_needed):
mdl.addConstr(quicksum(x[i, j, k] for j in V if j != i) == quicksum(x[j, i, k] for j in V if j != i), name="SameVehicleInOut_{}_{}".format(i, k))
mdl.Params.MIPGap = 0.1
mdl.Params.TimeLimit = 600 # seconds
mdl.write("myLP.lp")
mdl.optimize()
if mdl.SolCount > 0:
print("Best Objective Value Found:", mdl.ObjVal)
else:
print("No feasible solution found.")
if mdl.status == GRB.INFEASIBLE:
mdl.computeIIS()
print('\nThe following constraint(s) cannot be satisfied:')
for c in mdl.getConstrs():
if c.IISConstr:
print('%s' % c.constrName)
total_distance = 0
df_route_order = {}
for k in range(len(used_vehicles)):
solution_list = [0]
total_load = 0
while True:
added = False
for j in V:
if j not in solution_list and x[solution_list[-1], j, k].X > 0.5:
total_distance += c[solution_list[-1], j, k]
total_load += demand_list[j]
solution_list.append(j)
added = True
break
if not added or solution_list[-1] == 0:
total_distance += c[solution_list[-1], 0, k]
solution_list.append(0)
break
df_route_order[vehicle_types[k]] = solution_list
return total_distance, df_route_order
# You can call the function by passing the required arguments:
# distance_matrix_dict, num_vehicles, capacity_dict, demand_list, vehicle_types
def main(distance_matrix_dict, num_vehicles, capacity_dict, demand_list, vehicle_types):
total_distance, df_route_order = define_variables(distance_matrix_dict, num_vehicles, capacity_dict, demand_list, vehicle_types)
print(total_distance)
print(df_route_order)
return total_distance, df_route_order
if __name__ == "__main__":
"""
distance_matrix_dict = {'car': [[0, 973, 382, 1342, 914, 1103, 298, 186, 357, 495], [988, 0, 729, 466, 231, 230, 795, 1050, 1061, 745], [382, 723, 0, 1093, 705, 811, 238, 414, 402, 285], [1348, 429, 1120, 0, 573, 464, 1144, 1410, 1071, 846], [924, 250, 668, 576, 0, 278, 749, 986, 972, 656], [1105, 197, 788, 464, 286, 0, 928, 1202, 934, 710], [294, 797, 238, 1158, 738, 933, 0, 419, 512, 452], [191, 1045, 414, 1415, 986, 1176, 420, 0, 337, 475], [364, 1056, 402, 1163, 1007, 1114, 517, 341, 0, 311], [499, 788, 284, 943, 701, 746, 452, 476, 311, 0]]}
num_vehicles = 4
capacity_dict = {'car': 1100}
demand_list = [0, 161, 507, 779, 495, 424, 531, 298, 512, 381]
used_vehicles = ['car', 'car', 'car', 'car']
"""
initial_route = [[0, 2, 23, 15, 20, 0], [0, 7, 8, 9, 0], [0, 12, 14, 6, 19, 16, 11, 17, 1, 0], [0, 10, 0], [0, 21, 18, 4, 5, 24, 3, 22, 0], [0, 13, 0]]
capacity_dict = {'car': 1100, 'tractor': 5000}
used_vehicles = ['tractor','car', 'tractor', 'car', 'tractor', 'tractor']
demand_list = [0, 249, 882, 434, 1271, 245, 786, 480, 272, 127, 862, 2004, 334, 1340, 380, 1440, 245, 143, 199, 758, 2188, 168, 1949, 431, 622]
distance_matrix_dict = {'car': [[0, 973, 382, 1342, 914, 1103, 298, 186, 357, 495, 355, 793, 195, 908, 362, 503, 588, 900, 868, 378, 458, 658, 1380, 360, 1280], [988, 0, 729, 466, 231, 230, 795, 1050, 1061, 745, 1326, 260, 911, 370, 813, 750, 423, 86, 473, 742, 871, 649, 501, 708, 401], [382, 723, 0, 1093, 705, 811, 238, 414, 402, 285, 677, 543, 354, 819, 238, 121, 338, 650, 576, 348, 213, 275, 1130, 49, 1030], [1348, 429, 1120, 0, 573, 464, 1144, 1410, 1071, 846, 1686, 620, 1260, 638, 1173, 1055, 783, 497, 624, 1092, 924, 750, 118, 1067, 116], [924, 250, 668, 576, 0, 278, 749, 986, 972, 656, 1263, 215, 865, 395, 749, 603, 377, 157, 326, 696, 783, 560, 610, 644, 510], [1105, 197, 788, 464, 286, 0, 928, 1202, 934, 710, 1283, 394, 1044, 503, 930, 723, 557, 245, 446, 876, 787, 613, 499, 827, 399], [294, 797, 238, 1158, 738, 933, 0, 419, 512, 452, 633, 633, 223, 728, 183, 359, 420, 724, 708, 228, 380, 514, 1204, 217, 1104], [191, 1045, 414, 1415, 986, 1176, 420, 0, 337, 475, 462, 865, 369, 1030, 485, 542, 660, 972, 940, 530, 437, 690, 1452, 393, 1352], [364, 1056, 402, 1163, 1007, 1114, 517, 341, 0, 311, 361, 902, 542, 1127, 571, 401, 670, 983, 878, 627, 283, 506, 1225, 353, 1125], [499, 788, 284, 943, 701, 746, 452, 476, 311, 0, 660, 784, 568, 1033, 453, 278, 552, 756, 652, 562, 131, 287, 1006, 235, 906], [339, 1313, 677, 1682, 1253, 1443, 637, 464, 367, 672, 0, 1132, 535, 1247, 702, 761, 927, 1240, 1207, 762, 643, 867, 1720, 655, 1620], [808, 258, 549, 628, 199, 394, 632, 870, 904, 680, 1147, 0, 748, 369, 633, 534, 251, 185, 341, 624, 714, 619, 665, 528, 565], [193, 912, 353, 1273, 853, 1048, 222, 370, 540, 567, 532, 748, 0, 843, 298, 474, 535, 839, 823, 288, 495, 629, 1319, 332, 1219], [936, 442, 869, 641, 451, 578, 756, 1061, 1155, 1084, 1275, 437, 872, 0, 825, 875, 567, 383, 717, 669, 1012, 988, 743, 848, 633], [362, 816, 242, 1186, 757, 947, 181, 487, 580, 456, 700, 636, 297, 791, 0, 362, 431, 744, 711, 291, 384, 517, 1224, 220, 1123], [503, 731, 121, 1088, 638, 745, 358, 542, 401, 278, 750, 533, 474, 826, 359, 0, 345, 658, 509, 468, 212, 209, 1123, 137, 1023], [599, 423, 340, 792, 363, 556, 420, 661, 672, 555, 938, 251, 536, 516, 424, 346, 0, 350, 362, 412, 483, 453, 830, 319, 730], [932, 125, 673, 506, 145, 240, 738, 994, 1004, 698, 1270, 204, 854, 313, 756, 678, 367, 0, 426, 686, 815, 601, 540, 651, 440], [901, 522, 557, 789, 339, 446, 725, 972, 862, 632, 1210, 346, 841, 670, 725, 492, 372, 434, 0, 773, 672, 577, 824, 597, 724], [376, 729, 368, 1090, 670, 865, 243, 549, 642, 582, 747, 631, 290, 590, 313, 489, 425, 656, 752, 0, 510, 620, 1136, 347, 1036], [457, 866, 212, 1020, 817, 924, 380, 436, 284, 131, 633, 712, 496, 961, 381, 211, 480, 793, 688, 490, 0, 364, 1083, 163, 983], [657, 691, 274, 846, 604, 649, 512, 688, 505, 281, 854, 618, 628, 933, 513, 209, 452, 659, 555, 607, 358, 0, 909, 313, 809], [1435, 510, 1201, 147, 654, 545, 1242, 1497, 1189, 964, 1774, 708, 1358, 786, 1260, 1136, 871, 578, 860, 1190, 1042, 868, 0, 1155, 173], [361, 702, 49, 1072, 643, 850, 217, 393, 353, 235, 656, 522, 333, 798, 217, 137, 317, 629, 615, 327, 163, 314, 1109, 0, 1009], [1293, 367, 1058, 114, 511, 403, 1099, 1354, 1078, 853, 1631, 565, 1215, 640, 1117, 993, 728, 436, 717, 1047, 931, 757, 136, 1012, 0]], 'tractor': [[0, 1745, 1087, 2289, 1653, 1967, 872, 508, 952, 1480, 724, 1546, 402, 1506, 820, 1287, 1273, 1638, 1709, 703, 1294, 1489, 2425, 1048, 2229], [1888, 0, 1259, 609, 412, 342, 1244, 2269, 1686, 1508, 2196, 595, 1547, 661, 1192, 1143, 728, 262, 701, 1209, 1323, 1242, 745, 1220, 504], [1073, 1118, 0, 1675, 1027, 1269, 595, 1330, 699, 522, 1210, 842, 701, 1243, 647, 329, 575, 1012, 923, 775, 336, 531, 1811, 90, 1612], [2285, 706, 1671, 0, 854, 784, 1641, 2665, 2128, 1950, 2638, 1008, 1944, 1020, 1588, 1585, 1140, 780, 1143, 1606, 1765, 1684, 159, 1632, 151], [1703, 355, 1062, 861, 0, 382, 1059, 2077, 1446, 1269, 1957, 334, 1362, 583, 1007, 903, 531, 217, 461, 1024, 1083, 1003, 996, 999, 756], [2006, 319, 1253, 809, 411, 0, 1348, 2241, 1610, 1433, 2121, 595, 1651, 779, 1295, 1067, 792, 354, 625, 1327, 1247, 1167, 945, 1163, 704], [876, 1113, 588, 1658, 1021, 1318, 0, 1281, 807, 981, 1317, 871, 504, 986, 52, 788, 598, 1007, 1034, 263, 795, 990, 1793, 549, 1597], [499, 2153, 1426, 2697, 2061, 2350, 1302, 0, 739, 1339, 536, 1976, 832, 1914, 1250, 1410, 1703, 2046, 2003, 1111, 1154, 1612, 2833, 1336, 2637], [862, 1680, 699, 2171, 1490, 1623, 814, 655, 0, 613, 535, 1413, 920, 1801, 867, 683, 1147, 1583, 1277, 1078, 427, 885, 2307, 609, 2066], [1453, 1502, 521, 1992, 1311, 1445, 987, 1245, 615, 0, 1125, 1234, 1093, 1636, 1040, 437, 968, 1405, 1098, 1168, 185, 534, 2128, 431, 1887], [738, 2194, 1212, 2684, 2003, 2136, 1327, 534, 526, 1126, 0, 1926, 1025, 2105, 1380, 1196, 1660, 2097, 1790, 1302, 940, 1398, 2820, 1122, 2579], [1494, 369, 793, 926, 277, 591, 818, 1885, 1363, 1186, 1874, 0, 1121, 499, 766, 862, 262, 263, 513, 825, 1000, 962, 1062, 754, 863], [403, 1416, 716, 1961, 1325, 1621, 501, 808, 935, 1109, 1005, 1175, 0, 1289, 449, 916, 902, 1310, 1338, 482, 923, 1118, 2097, 677, 1900], [1652, 615, 1322, 1115, 626, 838, 1065, 2033, 1872, 1715, 2230, 659, 1368, 0, 1012, 1391, 791, 529, 1042, 973, 1529, 1491, 1251, 1283, 1054], [824, 1060, 641, 1605, 969, 1266, 52, 1228, 859, 1033, 1370, 819, 451, 933, 0, 841, 546, 954, 982, 211, 848, 953, 1741, 602, 1544], [1273, 1157, 328, 1647, 966, 1099, 795, 1315, 685, 437, 1195, 944, 901, 1376, 847, 0, 703, 1115, 753, 975, 322, 361, 1783, 238, 1542], [1237, 830, 531, 1387, 739, 1000, 561, 1641, 1100, 923, 1611, 554, 864, 960, 509, 730, 0, 724, 717, 624, 737, 824, 1523, 491, 1324], [1671, 137, 1042, 741, 182, 328, 1027, 2052, 1599, 1422, 2110, 378, 1330, 449, 975, 1056, 511, 0, 614, 992, 1236, 1156, 877, 1002, 636], [1728, 668, 901, 1158, 477, 610, 1053, 1888, 1258, 1080, 1768, 459, 1356, 958, 1000, 715, 497, 626, 0, 1103, 895, 814, 1294, 811, 1053], [706, 1066, 799, 1611, 974, 1288, 289, 1086, 1097, 1192, 1283, 891, 509, 827, 237, 999, 642, 959, 1078, 0, 1006, 1092, 1746, 760, 1550], [1267, 1316, 335, 1807, 1126, 1259, 802, 1060, 429, 185, 940, 1049, 908, 1450, 854, 319, 782, 1219, 912, 982, 0, 521, 1942, 245, 1702], [1474, 1238, 529, 1728, 1047, 1180, 996, 1516, 886, 521, 1396, 1025, 1102, 1457, 965, 343, 784, 1196, 834, 1080, 523, 0, 1864, 439, 1623], [2480, 902, 1867, 195, 1049, 979, 1836, 2861, 2323, 2146, 2834, 1203, 2139, 1215, 1784, 1780, 1336, 976, 1338, 1802, 1960, 1880, 0, 1827, 347], [1035, 1080, 89, 1637, 988, 1179, 556, 1239, 608, 431, 1119, 803, 662, 1205, 609, 238, 537, 974, 832, 737, 246, 440, 1773, 0, 1574], [2230, 607, 1617, 160, 754, 684, 1586, 2611, 2028, 1851, 2539, 939, 1889, 965, 1534, 1485, 1086, 681, 1043, 1551, 1666, 1585, 296, 1577, 0]]}
avg_distance_list = []
num_vehicles = len(used_vehicles)
main(distance_matrix_dict, num_vehicles, capacity_dict, demand_list, used_vehicles)
0
-
Hi Jordi,
Did you try the NoRelHeurTime parameter?
Could you please post the log output of your run?
Best regards,
Jaromił0 -
Hi Jaromil,
I have tried some things and have gotten the code to work in the case of a single vehicle type for both the cars and tractors, however, in the case that both vehicles get used it seems to make the model infeasible. The infeasibility code I get of the IIS is:
IIS computed: 2 constraints, 0 bounds
IIS runtime: 0.04 seconds (0.01 work units)The following constraint(s) cannot be satisfied:
LoadAfterVisit_11_20_3
LoadAfterVisit_20_11_3
I think it has something to do with the capacity of the car being to little for some of the demand at the nodes. However, with a simple nearest neighbour heuristic a solution can be found. I am not quite sure how I should edit the code. The updated Code is edited on the original post.
Thank you in advance!
Jordi0 -
Hi Jordi,
You can write the IIS to a file via
model.optimize()
if model.Status == GRB.INFEASIBLE:
model.computeIIS()
model.write("iis.ilp")You can then open the file \(\texttt{iis.ilp}\) in any standard text editor and try to find out why it is infeasible. You can also post the IIS here, if you need further advice.
Best regards,
Jaromił0 -
Hi Jaromil,
This is my IIS:
\ Model CVRP_copy
\ LP format - for model browsing. Use MPS format to capture full model detail.
Minimize
Subject To
LoadAfterVisit_11_20_3: - 1100 C1701 - C3663 + C3717 >= 1088
LoadAfterVisit_20_11_3: - 1100 C2949 + C3663 - C3717 >= 904
Bounds
C3663 free
C3717 free
Binaries
C1701 C2949
EndHowever, I am not quite sure what to do about it.
0 -
You have two binary variables of interest. The continuous variables are not interesting for the infeasibility because they can be free.
Let's try all 4 cases for the 2 binaries.
For C1701 = 1, C2949 = 1, we get
- 1100 * 1 - C3663 + C3717 >= 1088
- 1100 * 1 + C3663 - C3717 >= 904
<=>
- C3663 + C3717 >= 2188
+ C3663 - C3717 >= 2004
<=>
+ C3663 - C3717 <= - 2188
+ C3663 - C3717 >= 2004For C1701 = 1, C2949 = 0, we get
- 1100 * 1 - C3663 + C3717 >= 1088
- 1100 * 0 + C3663 - C3717 >= 904
<=>
- C3663 + C3717 >= 2188
+ C3663 - C3717 >= 904
<=>
+ C3663 - C3717 <= - 2188
+ C3663 - C3717 >= 904For C1701 = 0, C2949 = 1, we get
- 1100 * 0 - C3663 + C3717 >= 1088
- 1100 * 1 + C3663 - C3717 >= 904
<=>
- C3663 + C3717 >= 1088
+ C3663 - C3717 >= 2004
<=>
+ C3663 - C3717 <= - 1088
+ C3663 - C3717 >= 2004For C1701 = 0, C2949 = 0, we get
- 1100 * 0 - C3663 + C3717 >= 1088
- 1100 * 0 + C3663 - C3717 >= 904
<=>
- C3663 + C3717 >= 1088
+ C3663 - C3717 >= 904
<=>
+ C3663 - C3717 <= - 1088
+ C3663 - C3717 >= 904So, independent of how you set the 2 binary variables, the 2 constraint will always be infeasible. Now, it is up to you to understand why these constraints are present in this form in your model.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
5 comments