My model is infeasible. Can someone please help me?
AnsweredHi, i currently have the following code for an MILP program modelling a CVRP situations with multiple vehicles. My model does not run because it is infeasible, however I am not quite sure why it should print it as infeasible, I added code to print the infeasible constraints.
The following constraint(s) cannot be satisfied:
VisitOnceTo_1
VisitOnceTo_2
VisitOnceTo_3
VisitOnceTo_4
VisitOnceTo_5
VisitOnceTo_6
VisitOnceTo_7
VisitOnceTo_8
VisitOnceTo_9
VisitOnceTo_10
VisitOnceTo_11
VisitOnceTo_12
VisitOnceTo_13
VisitOnceTo_14
VisitOnceTo_15
VisitOnceTo_16
VisitOnceTo_17
VisitOnceTo_18
VisitOnceTo_19
VisitOnceTo_20
VisitOnceTo_21
VisitOnceTo_22
VisitOnceTo_23
VisitOnceTo_24
VehicleLeavesDepot_0
VehicleLeavesDepot_1
VehicleLeavesDepot_2
VehicleLeavesDepot_3
VehicleLeavesDepot_6
VehicleLeavesDepot_7
VehicleLeavesDepot_8
VehicleLeavesDepot_9
VehicleLeavesDepot_10
VehicleLeavesDepot_11
VehicleLeavesDepot_12
VehicleLeavesDepot_13
VehicleLeavesDepot_14
VehicleLeavesDepot_15
VehicleLeavesDepot_16
VehicleLeavesDepot_17
VehicleLeavesDepot_18
VehicleLeavesDepot_19
VehicleLeavesDepot_20
VehicleLeavesDepot_21
VehicleLeavesDepot_22
VehicleLeavesDepot_23
VehicleLeavesDepot_24
VehicleLeavesDepot_25
VehicleLeavesDepot_26
can someone please help me? I have been stuck for quite some time.
Thank you in advance!
Here is my code along with the 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")
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, 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[j] - (1 - x[i, j, k]) * max(demand_list), name="LoadAfterVisit_{}_{}_{}".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(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 = 30 # seconds
mdl.write("myLP.lp")
mdl.optimize()
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(vehicle_types)):
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__":
vehicle_types = ["car", "tractor"]
capacity_dict = {'car': 1100, 'tractor': 5000}
used_vehicles = ['tractor', 'car', 'tractor', 'car', 'tractor', 'tractor', 'tractor', 'tractor', 'tractor', 'tractor', 'tractor', 'tractor', 'tractor', 'tractor', 'tractor', 'tractor', 'tractor', 'tractor', 'tractor', 'tractor', 'tractor', 'tractor', 'tractor', 'tractor', 'tractor', 'tractor', 'tractor']
demand_list = [0, 1342, 2064, 1442, 2673, 3578, 2120, 418, 3218, 354, 3701, 503, 3630, 2171, 2090, 3466, 1126, 1639, 3720, 3502, 1033, 2570, 2429, 2257, 1029]
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]]}
num_vehicles = len(used_vehicles)
main(distance_matrix_dict, num_vehicles, capacity_dict, demand_list, used_vehicles)
-
Hi Jordi,
I was able to remove the infeasibility by relaxing the below equality constraints to larger or equal to constraints.>= 1, name="VisitOnceFrom_{}".format(i))
>= 1, name="VisitOnceTo_{}".format(j))Before, it was forbidden for multiple vehicles to visit a specific client. I can think of two cases how this resulted in infeasibility. One is that if the demand of one client exceeded a vehicle type's capacity, it would render your model infeasible because multiple visits to one client were forbidden. The second is that each vehicle is forced to leave the depot, but the number of vehicles is larger than the number of clients; hence, some clients had to be visited by more than one vehicle – which was not allowed.
I hope this information is helpful, please let me know if otherwise.
Best regards,
Lennart0
Please sign in to leave a comment.
Comments
1 comment