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

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 & Item3SlotC: Item4以下是此示例的完整表格的链接：https://i.stack.imgur.com/TluHG.jpg我希望这个例子能让问题更容易理解。

Answer 1

数学模型

我会引入一个二元变量：

x[i,j] = 1 if item i is assigned to slot j
         0 otherwise

这是我们的第一个问题：有许多 (i,j) 组合是不允许的。智能模型会尽量不生成禁止的组合。因此我们需要实现一个稀疏变量而不是完全分配的变量。x[i,j]我们只想在为allowed(i,j)真时分配和使用。

此外，引入一个连续变量xstat[s]来计算每个统计数据的总值。

一旦我们有了这个，我们就可以写下约束：

sum( i | allowed(i,j),  x[i,j] ) = 1  for all slots j          (exactly one item in each slot)

  xstat[s] = sum( (i,j) | allowed(i,j),  x[i,j] * stat[i,s])     (calculate total stats)  

  xstat['StatDark'] >= 9                                         

该目标是两个目标的加权和：

  minimize xstat['StatDark'] - 9

  maximize xstat['StatLight']

所以我们这样做：

  maximize -w1*(xstat['StatDark'] - 9) +  w2*xstat['StatLight']

对于用户提供的权重 w1 和 w2。

这两个问题让问题变得更加复杂。此外，我们还需要对数据做一些工作，使其适合在优化模型中使用。

Python代码

import pandas as pd

import pulp as lp

from io import StringIO

#----------------------------------------

# raw data

#----------------------------------------

itemData = pd.read_table(StringIO("""

Item   Group  StatDark StatLight

Item1  Group1    3        5

Item2  Group1    7        1

Item3  Group1    2        5

Item4  Group2    1        6

Item5  Group2    2        5

"""),sep="\s+")

slotData = pd.read_table(StringIO("""

Slot   Group

SlotA  Group1

SlotB  Group1

SlotC  Group2

"""),sep='\s+')

# minimum total of Dark

minDark = 9

# stats

stat = ['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'])

 

items = itemData['Item']

slots = slotData['Slot']

# we will use the convention:

#  i : items

#  j : slots

#  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

#            0 otherwise

# only use combinations (i,j) that are allowed

x = lp.LpVariable.dicts('x', [(i,j) for i,j in merged.index], cat='Binary') 

# xstat[stat] = total accumulated values

xstat = 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 statLight

prob +=  -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:

  prob += lp.lpSum([x[(i,j)] for i,jj in merged.index if jj==j]) == 1

#  minimum total value for dark 

prob += xstat['StatDark'] >= minDark 

# calculate stat totals

for s in stat:

  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 

# 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:

  if lp.value(x[(i,j)]) > 0.5:

    assigned += [[i, j]]

assigned = pd.DataFrame(assigned, columns=['item','slot'])

print(assigned)

讨论

该表merged看起来像：

Item   Slot   Group

-----------------------

Item1   SlotA   Group1

        SlotB   Group1

Item2   SlotA   Group1

        SlotB   Group1

Item3   SlotA   Group1

        SlotB   Group1

Item4   SlotC   Group2

Item5   SlotC   Group2 

Item,Slot 列为我们提供了允许的组合。

该字典statv提供了一个方便的数据结构来访问统计贡献：

{('Item1', 'StatDark'): 3,

 ('Item1', 'StatLight'): 5,

 ('Item2', 'StatDark'): 7,

 ('Item2', 'StatLight'): 1,

 ('Item3', 'StatDark'): 2,

 ('Item3', 'StatLight'): 5,

 ('Item4', 'StatDark'): 1,

 ('Item4', 'StatLight'): 6,

 ('Item5', 'StatDark'): 2,

 ('Item5', 'StatLight'): 5}

生成的 MIP 模型如下所示：

assignItemsToSlots:

MAXIMIZE

-0.3*xstat_StatDark + 0.7*xstat_StatLight + 2.6999999999999997

SUBJECT 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')

 - 7 x_('Item2',_'SlotA') - 7 x_('Item2',_'SlotB') - 2 x_('Item3',_'SlotA')

 - 2 x_('Item3',_'SlotB') - x_('Item4',_'SlotC') - 2 x_('Item5',_'SlotC')

 + xstat_StatDark = 0

_C6: - 5 x_('Item1',_'SlotA') - 5 x_('Item1',_'SlotB') - x_('Item2',_'SlotA')

 - x_('Item2',_'SlotB') - 5 x_('Item3',_'SlotA') - 5 x_('Item3',_'SlotB')

 - 6 x_('Item4',_'SlotC') - 5 x_('Item5',_'SlotC') + xstat_StatLight = 0

VARIABLES

0 <= x_('Item1',_'SlotA') <= 1 Integer

0 <= x_('Item1',_'SlotB') <= 1 Integer

0 <= x_('Item2',_'SlotA') <= 1 Integer

0 <= x_('Item2',_'SlotB') <= 1 Integer

0 <= x_('Item3',_'SlotA') <= 1 Integer

0 <= x_('Item3',_'SlotB') <= 1 Integer

0 <= x_('Item4',_'SlotC') <= 1 Integer

0 <= x_('Item5',_'SlotC') <= 1 Integer

xstat_StatDark Continuous

xstat_StatLight Continuous

解决方案

解决方案如下所示：

Status: Optimal

Objective: 8.099999999999998

    item   slot

0  Item2  SlotB

1  Item3  SlotA

2  Item4  SlotC