AMPL / Python - 性能和内存问题

Question

我编写了一个简单的模型，可以优化拥有 30,000 个位置的仓库的物品位置分配。

我的代码适用于 3 个项目和 gurobi 或 cplex，但是：

• 使用 CBC：即使只有 3 个项目，1 分钟后也不起作用……
• 高点：

  Error -1 for call Highs_passH

• 拥有 3000 件物品并使用 Gurobi 或 Cplex :

  Unexpected end of file while reading AMPL output.

但是这是一个非常简单的模型，数据也不是很大。 你能帮我吗？

AMPL 型号：

set Items;  # Ensembles des articles
set Locations;  # Ensemble des emplacements

param Quantity{Items};  # Coût de chaque allée
param Cost_Location{Locations};  # Capacité maximale des emplacements
param Cost_Move := 1; # Coût de déplacement d'un article
param valid_allocations{Items, Locations} binary;  # Table des allocations valides pour chaque article

var assign{Items, Locations} binary;  # Variables de décision : 1 si l'article est attribué à l'emplacement, 0 sinon
var prev_loc{Items, Locations} binary;  # Variables de décision : 1 si l'article est attribué à l'emplacement, 0 sinon

minimize Total_Cost:
    sum{i in Items, j in Locations} assign[i,j] * (Cost_Location[j] + Cost_Move * prev_loc[i,j]);

subject to Assignment_Constraint{i in Items}:
    sum{j in Locations} assign[i,j] = 1;  

subject to Valid_Allocation_Constraint{i in Items, j in Locations}:
    assign[i,j] <= valid_allocations[i,j];

subject to AtLeastOneAssignment_Constraint{i in Items}:
    sum{j in Locations} assign[i,j] >= 1;

Python 代码：

    from amplpy import AMPL
    import polars as pl
    
    
    ampl = AMPL()
    ampl.option["solver"] = "gurobi"
    ampl.read("allocation.model")
    
    items_set = ampl.getSet("Items")
    locations_set = ampl.getSet("Locations")
    quantity_demand_param = ampl.getParameter("Quantity")
    cost_location_param = ampl.getParameter("Cost_Location")
    valid_allocations_param = ampl.getParameter("valid_allocations")
    
    orders = pl.read_csv("./data/orders.csv", separator=';')
    locations = pl.read_csv("./data/locations.csv", separator=';')

#Work only with this filter
    orders = orders.filter((pl.col("ITEM_ID") == 34682) | (pl.col("ITEM_ID") == 34657) | (pl.col("ITEM_ID") == 29840))
    
    items_set.setValues(orders.select("ITEM_ID").unique().to_dict(as_series=False)["ITEM_ID"])
    locations_set.setValues(locations.select("LOCATION_ID").unique().to_dict(as_series=False)["LOCATION_ID"])
    
    
    quantity_demand_param.setValues(dict(orders.unique(subset = "ITEM_ID").select(["ITEM_ID","QTY"]).iter_rows()))
    cost_location_param.setValues(dict(locations.unique(subset = "LOCATION_ID").select(["LOCATION_ID","WALKING_DISTANCE"]).iter_rows()))
    cartesian_locations = orders.select("ITEM_ID").unique().join(locations,how='cross', suffix="_LOCATIONS" )
    cartesian_locations = cartesian_locations.select(pl.col("ITEM_ID"),pl.col("LOCATION_ID"),(pl.col("CART_STD1") | pl.col("CART_STD2") | pl.col("CART_DEMI-HAUT") | pl.col("CART_VOLUMINEUX")))
    cartesian_locations =  cartesian_locations.with_columns(pl.col("CART_STD1").apply(lambda col: int(col)))
    cartesian_locations = cartesian_locations.pivot( values="CART_STD1", index="ITEM_ID", columns="LOCATION_ID",aggregate_function="first")
    cartesian_locations = cartesian_locations.to_pandas()
    cartesian_locations = cartesian_locations.set_index("ITEM_ID").transpose()
    valid_allocations_param.setValues(cartesian_locations.unstack())
    
    ampl.solve()

Answer 1

在此模型中，您有在两个集合（位置和项目）上索引的参数和变量。由于您有 3,000 个商品和 30,000 个位置，如果所有商品在所有位置都可用，则这意味着 90,000,000 个变量。在具有大量内存的计算机上使用 Gurobi 或 CPLEX 仍然可以解决这个问题，但它比当今开源求解器能够解决的任何问题都要大得多。

要了解模型，请执行以下操作以查看传递到 AMPL 的数据大小：

print(cartesian_locations.stack().shape)

您可以过滤此数据以仅包含每个位置可用的商品。这将有助于提高性能并大幅减少内存使用量。

请注意，您应该在有效分配上对变量进行索引，以减少变量的数量，而不是在

{Items, Locations}

上对变量进行索引。这也避免了约束

Valid_Allocation_Constraint

。使用包含有效分配的集合

ItemLocations

，您可以按如下方式建模：

set Items;  # Ensembles des articles
set Locations;  # Ensemble des emplacements
set ItemLocations within {Items, Locations}; # Valid allocations

param Quantity{Items};  # Coût de chaque allée
param Cost_Location{Locations};  # Capacité maximale des emplacements
param Cost_Move := 1; # Coût de déplacement d'un article

var assign{ItemLocations} binary;  # Variables de décision : 1 si l'article est attribué à l'emplacement, 0 sinon
var prev_loc{ItemLocations} binary;  # Variables de décision : 1 si l'article est attribué à l'emplacement, 0 sinon

minimize Total_Cost:
    sum{(i,j) in ItemLocations} assign[i,j] * (Cost_Location[j] + Cost_Move * prev_loc[i,j]);

subject to Assignment_Constraint{i in Items}:
    sum{(i,j) in ItemLocations} assign[i,j] = 1;

# redundant constraint as Assignment_Constraint enforces that each item is assigned to exactly one location:
#subject to AtLeastOneAssignment_Constraint{i in Items}:
#   sum{(i,j) in ItemLocations} assign[i,j] >= 1;

我还要注意，尽管 prev_loc 被声明为变量，但它似乎是一个指示该项目是否位于给定位置的参数。您可以将其切换为参数，以最终将模型大小减小到可以使用开源求解器的程度。您可以过滤以仅包含特定值下的分配（即排除所有昂贵的重新分配）。如果您选择较低的阈值，该解决方案将不能保证是最佳的，但仍然应该相当不错。您可以在 ItemLocations 中仅放置似乎值得考虑的对（项目、位置），而不是所有有效的分配。