当穷举搜索花费太长时间时，如何找到最佳组合？

Question

我是一个完全的业余爱好者，没有接受过正式培训，只是自学了一些 C# 和 Python

有47个槽位。每一项必须填写一项。这些插槽分为 8 组。项目被分为相同的 8 组。
每个槽只能由同一组的一个项目填充。
同一物品可用于填充多个插槽。

每个项目由一个名称、一个组和 9 个统计数据组成。

item ("name", "group", "stat1", "stat2", "stat3", ..., "stat9")
exampleItem (exampleName, groupA, 3, 8, 19, ..., 431)

每个槽由一个 ID 和一个组组成。

slot1 (1, groupC)

让每个槽填满一个物品（遵循上述规则）。

然后将每个不同的统计数据相加。

stat1Total=item1(stat1)+item2(stat1)+item3(stat1)+...+item47(stat1)

目标是： -
让每个槽填满相应组的项目。（没有空槽）
- 让 stat1Total、stat2Total 和 stat3Total 达到一定数量（stat1Goal、stat2Goal、stat3Goal）
- 让 stat1Total、stat2Total 和 stat3Total 尽可能少地超过该数量 -
最大化所有其他 statTotal，并分别赋予权重

输出满足上述目标的最佳项目组合。（如果 2 个或更多组合同样是最佳组合，则输出所有组合。

我尝试搜索所有可能的组合以获得最佳输出，但总共有 2.16x10^16 种可能的组合，所以我认为这是不可行的。
现在我不知道如何解决这个问题，而且我对整数规划的了解越多，我就越困惑。

为了说明这个问题，我将给出一个包含 3 个槽、2 个组和 5 个项目的简化示例：

SlotA、SlotB 和 SlotC 必须分别填充 5 个项目中的一个。
Slot A 和SlotB 属于组Group1，SlotC 属于Group2。
这些项目被分类到相同的组中。因此，我们有属于 Group1 的 Item1、Item2 和 Item3，以及属于 Group2 的 Item4 和 Item5。

这意味着SlotA和SlotB只能由Item1、Item2和Item3填充。您可以将插槽想象为不同形状的孔，并且具有适合这些孔的形状的物品。您无法将星形钉放入方孔中，也无法将 Item5 放入 SlotB 中，因为它不适合。

这些物品本身有不同的统计数据。对于此示例，我们假设每个项目仅具有其所属的组和 2 个统计数据：StatDark、StatLight。这些可以采用 0 到 10 之间的整数值。

Item1(Group1, StatDark=3, StatLight=5)

Item2(Group1, StatDark=7, StatLight=1)

Item3(Group1, StatDark=2, StatLight=5)

Item4(Group2, StatDark=1, StatLight=6)

Item5(Group2, StatDark=2, StatLight=5)

此示例的目标是：
- 用一个项目填充每个槽，同时遵守分组规则
- 使所有选定项目的所有 StatDark 之和等于或大于 9
- 将 StatDark 最小化为高于 9（每个高于 9 的 StatDark 都是无用和浪费）
-最大化所有选定项目的所有 StatLight 的总和

在这种情况下，最佳解决方案是：
SlotA & SlotB: Item2 & Item3
SlotC: Item4

以下是此示例的完整表格的链接：https://i.stack.imgur.com/TluHG.jpg

我希望这个例子能让问题更容易理解。

Answer 1

数学模型我会引入一个二元变量：x[i,j]&nbsp;=&nbsp;1&nbsp;if&nbsp;item&nbsp;i&nbsp;is&nbsp;assigned&nbsp;to&nbsp;slot&nbsp;j &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0&nbsp;otherwise这是我们的第一个问题：有许多 (i,j) 组合是不允许的。智能模型会尽量不生成禁止的组合。因此我们需要实现一个稀疏变量而不是完全分配的变量。x[i,j]我们只想在为allowed(i,j)真时分配和使用。此外，引入一个连续变量xstat[s]来计算每个统计数据的总值。一旦我们有了这个，我们就可以写下约束：sum( i | allowed(i,j),&nbsp; x[i,j] ) = 1&nbsp; for all slots j&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (exactly one item in each slot)&nbsp; xstat[s] = sum( (i,j) | allowed(i,j),&nbsp; x[i,j] * stat[i,s])&nbsp; &nbsp; &nbsp;(calculate total stats)&nbsp;&nbsp;&nbsp; xstat['StatDark'] >= 9&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;该目标是两个目标的加权和：&nbsp; minimize xstat['StatDark'] - 9&nbsp; maximize xstat['StatLight']所以我们这样做：&nbsp; maximize -w1*(xstat['StatDark'] - 9) +&nbsp; w2*xstat['StatLight']对于用户提供的权重 w1 和 w2。这两个问题让问题变得更加复杂。此外，我们还需要对数据做一些工作，使其适合在优化模型中使用。Python代码import pandas as pdimport pulp as lpfrom io import StringIO#----------------------------------------# raw data#----------------------------------------itemData = pd.read_table(StringIO("""Item&nbsp; &nbsp;Group&nbsp; StatDark StatLightItem1&nbsp; Group1&nbsp; &nbsp; 3&nbsp; &nbsp; &nbsp; &nbsp; 5Item2&nbsp; Group1&nbsp; &nbsp; 7&nbsp; &nbsp; &nbsp; &nbsp; 1Item3&nbsp; Group1&nbsp; &nbsp; 2&nbsp; &nbsp; &nbsp; &nbsp; 5Item4&nbsp; Group2&nbsp; &nbsp; 1&nbsp; &nbsp; &nbsp; &nbsp; 6Item5&nbsp; Group2&nbsp; &nbsp; 2&nbsp; &nbsp; &nbsp; &nbsp; 5"""),sep="\s+")slotData = pd.read_table(StringIO("""Slot&nbsp; &nbsp;GroupSlotA&nbsp; Group1SlotB&nbsp; Group1SlotC&nbsp; Group2"""),sep='\s+')# minimum total of DarkminDark = 9# statsstat = ['StatDark','StatLight']# objective weights# we have two objectives and there are trde offs between them.# here we use a simple weighted sum approach. These are the weights.w = {'StatDark':0.3, 'StatLight':0.7}#----------------------------------------# data prep#----------------------------------------# join on Group# we need to know which (Item,Slot) combinations are allowed.merged = pd.merge(itemData[['Item','Group']],slotData,on='Group').set_index(['Item','Slot'])&nbsp;items = itemData['Item']slots = slotData['Slot']# we will use the convention:#&nbsp; i : items#&nbsp; j : slots#&nbsp; s : stats# stat values# easy lookup of statv[(i,s)]itemData = itemData.set_index('Item')statv = {(i,s):itemData.loc[i,s] for i in items for s in stat}#----------------------------------------# MIP model#----------------------------------------# x[(i,j)] = 1 if item i is assigned to slot j#&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0 otherwise# only use combinations (i,j) that are allowedx = lp.LpVariable.dicts('x', [(i,j) for i,j in merged.index], cat='Binary')&nbsp;# xstat[stat] = total accumulated valuesxstat = lp.LpVariable.dicts('xstat', [s for s in stat], cat='Continuous', lowBound = 0)prob = lp.LpProblem("assignItemsToSlots", lp.LpMaximize)# objective: weighted sum#----------# 1. minimize statDark exceeding minDark# 2. maximize statLightprob +=&nbsp; -w['StatDark']*(xstat['StatDark'] - minDark) + w['StatLight']*xstat['StatLight']# constraints# -----------# each slot much have exactly one item# (but the same item can go to different slots)for j in slots:&nbsp; prob += lp.lpSum([x[(i,j)] for i,jj in merged.index if jj==j]) == 1#&nbsp; minimum total value for dark&nbsp;prob += xstat['StatDark'] >= minDark&nbsp;# calculate stat totalsfor s in stat:&nbsp; prob += xstat[s] == lp.lpSum([x[(i,j)]*statv[i,s] for i,j in merged.index])#----------------------------------------# solve problem#----------------------------------------prob.solve()# to show the log use&nbsp;# solve(pulp.PULP_CBC_CMD(msg=1))print("Status:", lp.LpStatus[prob.status])print("Objective:",lp.value(prob.objective))#----------------------------------------# solution#----------------------------------------assigned = []for i,j in merged.index:&nbsp; if lp.value(x[(i,j)]) > 0.5:&nbsp; &nbsp; assigned += [[i, j]]assigned = pd.DataFrame(assigned, columns=['item','slot'])print(assigned)讨论该表merged看起来像：Item&nbsp; &nbsp;Slot&nbsp; &nbsp;Group-----------------------Item1&nbsp; &nbsp;SlotA&nbsp; &nbsp;Group1&nbsp; &nbsp; &nbsp; &nbsp; SlotB&nbsp; &nbsp;Group1Item2&nbsp; &nbsp;SlotA&nbsp; &nbsp;Group1&nbsp; &nbsp; &nbsp; &nbsp; SlotB&nbsp; &nbsp;Group1Item3&nbsp; &nbsp;SlotA&nbsp; &nbsp;Group1&nbsp; &nbsp; &nbsp; &nbsp; SlotB&nbsp; &nbsp;Group1Item4&nbsp; &nbsp;SlotC&nbsp; &nbsp;Group2Item5&nbsp; &nbsp;SlotC&nbsp; &nbsp;Group2&nbsp;Item,Slot 列为我们提供了允许的组合。该字典statv提供了一个方便的数据结构来访问统计贡献：{('Item1', 'StatDark'): 3,&nbsp;('Item1', 'StatLight'): 5,&nbsp;('Item2', 'StatDark'): 7,&nbsp;('Item2', 'StatLight'): 1,&nbsp;('Item3', 'StatDark'): 2,&nbsp;('Item3', 'StatLight'): 5,&nbsp;('Item4', 'StatDark'): 1,&nbsp;('Item4', 'StatLight'): 6,&nbsp;('Item5', 'StatDark'): 2,&nbsp;('Item5', 'StatLight'): 5}生成的 MIP 模型如下所示：assignItemsToSlots:MAXIMIZE-0.3*xstat_StatDark + 0.7*xstat_StatLight + 2.6999999999999997SUBJECT TO_C1: x_('Item1',_'SlotA') + x_('Item2',_'SlotA') + x_('Item3',_'SlotA') = 1_C2: x_('Item1',_'SlotB') + x_('Item2',_'SlotB') + x_('Item3',_'SlotB') = 1_C3: x_('Item4',_'SlotC') + x_('Item5',_'SlotC') = 1_C4: xstat_StatDark >= 9_C5: - 3 x_('Item1',_'SlotA') - 3 x_('Item1',_'SlotB')&nbsp;- 7 x_('Item2',_'SlotA') - 7 x_('Item2',_'SlotB') - 2 x_('Item3',_'SlotA')&nbsp;- 2 x_('Item3',_'SlotB') - x_('Item4',_'SlotC') - 2 x_('Item5',_'SlotC')&nbsp;+ xstat_StatDark = 0_C6: - 5 x_('Item1',_'SlotA') - 5 x_('Item1',_'SlotB') - x_('Item2',_'SlotA')&nbsp;- x_('Item2',_'SlotB') - 5 x_('Item3',_'SlotA') - 5 x_('Item3',_'SlotB')&nbsp;- 6 x_('Item4',_'SlotC') - 5 x_('Item5',_'SlotC') + xstat_StatLight = 0VARIABLES0 <= x_('Item1',_'SlotA') <= 1 Integer0 <= x_('Item1',_'SlotB') <= 1 Integer0 <= x_('Item2',_'SlotA') <= 1 Integer0 <= x_('Item2',_'SlotB') <= 1 Integer0 <= x_('Item3',_'SlotA') <= 1 Integer0 <= x_('Item3',_'SlotB') <= 1 Integer0 <= x_('Item4',_'SlotC') <= 1 Integer0 <= x_('Item5',_'SlotC') <= 1 Integerxstat_StatDark Continuousxstat_StatLight Continuous解决方案解决方案如下所示：Status: OptimalObjective: 8.099999999999998&nbsp; &nbsp; item&nbsp; &nbsp;slot0&nbsp; Item2&nbsp; SlotB1&nbsp; Item3&nbsp; SlotA2&nbsp; Item4&nbsp; SlotC