python - PuLP 需要太多时间来解决

Question

我正在尝试使用 Pulp Solver 将元素包装到卡车中，当元素数量较少(即 <25)时，它工作得很好，但当我将数量增加到 30-32 时，它需要很长时间才能解决。

这是 PuLP 求解器的代码:

def allocator(item_mass, item_vol, truck_mass, truck_vol, truck_cost, id_series):
    n_items = len(item_vol)
    set_items = range(n_items)
    n_trucks = len(truck_cost)
    set_trucks = range(n_trucks)


    y = pulp.LpVariable.dicts('truckUsed', set_trucks,
        lowBound=0, upBound=1, cat=LpInteger)

    x = pulp.LpVariable.dicts('itemInTruck', (set_items, set_trucks), 
        lowBound=0, upBound=1, cat=LpInteger)

    # Model formulation
    prob = LpProblem("Truck allocation problem", LpMinimize)

    # Objective
    prob += lpSum([truck_cost[i] * y[i] for i in set_trucks])
    # Constraints
    for j in set_items:
        # Every item must be taken in one truck
        prob += lpSum([x[j][i] for i in set_trucks]) == 1

    for i in set_trucks:
        # Respect the mass constraint of trucks
        prob += lpSum([item_mass[j] * x[j][i] for j in set_items]) <= truck_mass[i]*y[i]

        # Respect the volume constraint of trucks
        prob += lpSum([item_vol[j] * x[j][i] for j in set_items]) <= truck_vol[i]*y[i]
    # Ensure y variables have to be set to make use of x variables:
    for j in set_items:
        for i in set_trucks:
            x[j][i] <= y[i]

    s = id_series  # id_series

    prob.solve()

我是不是做错了什么？

这是link到 jupyter 笔记本和测试文件。

Answer 1

默认情况下，您使用的是 CBC，一个开源 MIP 求解器。
2种可能的方法:

1. 使用更好的求解器，例如 CPLEX 或 GUROBI(商业广告，但对学生和学者免费)。 PuLP 有一个适用于这两者的 API。
2. 您需要最佳解决方案吗？如果情况并非如此，请设定时间限制。

示例:

prob.solve(pulp.COIN(maxSeconds=your_time_limit))