货架空间分配约束规划求解时出现UNSATISFIABLE问题的排查求助

我正在用约束规划实现货架排面（planogram）的商品空间分配，目前的思路是把整个排面拆分成网格来逐步落地，但遇到了一个头疼的问题：小配置下完全正常，一放大到大规模场景就一直返回UNSATISFIABLE，试了各种调整都找不到根源，想请各位帮忙分析下！

核心实现思路 #

我把排面按指定粒度拆分为独立网格，比如：

• 排面宽度10cm、3层货架、粒度1cm时，总共有30个网格（3*10）
• 一个长度6cm的商品会占用6个连续网格

为了正确分配商品，我定义了4个核心约束：

1. 每个商品必须恰好占用等于自身长度的网格数
2. 每个网格只能分配给一个商品
3. 同一个商品的所有网格必须在同一层货架上
4. 同一个商品的所有网格必须是连续的

小场景验证有效 #

比如下面这个小配置：

granularity = 1,
shelf_count = 3,
section_width = 10

搭配几个商品（tpnb是商品编号，linear是所需空间），求解器能给出完全符合预期的分配结果——每个商品都在单一层货架上占用连续的对应数量网格，没有重叠也没有浪费。

大规模场景出现问题 #

但当我切换到更大的配置时：

granularity = 1
shelf_count = 7
section_width = 133

总共有57个商品需要分配，求解器跑了近60秒后返回：

Status: ExitStatus.UNSATISFIABLE (59.21191700000001 seconds)
No solution found.

我反复调整约束的写法，甚至简化了部分逻辑，但还是一直报不可行，实在搞不懂是约束有漏洞，还是求解器的性能/建模方式有问题？

我的代码实现 #

下面是核心的约束建模代码，麻烦各位帮忙看看有没有潜在问题：

pog_df['linear'] = pog_df.linear.apply(np.ceil)
pog_df['gridlinear'] = pog_df.linear//granularity

G = nx.grid_2d_graph(int(section_width * bay_count/granularity),int(shelf_count))

# 定义节点位置（用于可视化，核心逻辑无关）
pos = {(x, y): (x, y) for x, y in G.nodes()}
plt.figure(figsize=(8, 4))
nx.draw(G, pos, node_size=0.07)

products = pog_df[['tpnb', 'gridlinear']].astype(str)
locations = pd.Series([str(s) for s in G.nodes()], name='location')
locations = pd.concat([locations,locations.to_frame().location.str.strip("() ").str.split(',', expand=True).rename(columns={0: 'x', 1: 'y'})], axis=1)

l_p_idx = pd.merge(products.reset_index(),
         locations,
          how='cross')[['tpnb', 'gridlinear', 'location', 'x', 'y']]

n_location = len(locations)
n_products = pog_df.shape[0]

# 创建决策变量：每个商品-网格的分配布尔变量
l_p_idx['Var'] = l_p_idx.apply(lambda x: cp.boolvar(name=x['location']+'-'+x['tpnb']), axis=1)

m = cp.Model()

# 约束1：每个商品占用的网格数恰好等于需求
l_p_idx.groupby('tpnb', as_index=False).agg({'Var':cp.sum, 'gridlinear': 'unique'}).apply(lambda x: m.constraints.append(x['Var']==int(float(x["gridlinear"]))), axis=1)

# 约束2：每个网格只能分配给一个商品
l_p_idx.groupby('location', as_index=False).agg({'Var':cp.sum}).apply(lambda x: m.constraints.append(x['Var']<=1), axis=1)

# 约束3：同一个商品的所有网格必须在同一层货架
l_p_idx["y"] = l_p_idx["y"].astype("int32")
shelf_var = {tpnb: cp.intvar(0, max(l_p_idx["y"])) for tpnb in l_p_idx["tpnb"].unique()}
l_p_idx.apply(lambda row: m.constraints.append(
    (row['Var'] == 1).implies(row['y'] == shelf_var[row['tpnb']])
), axis=1)

# 处理商品-网格变量的映射
def process_group(level, data):
    return level, {eval(row['location']): row['Var'] for _, row in data.iterrows()}
    
def parallel_creator(key, idx_df):
    node_dict = {}
    with ProcessPoolExecutor() as executor:
        futures = {executor.submit(process_group, level, data): level for level, data in idx_df.groupby(key)}
        for future in as_completed(futures):
            level, var_dict = future.result()
            node_dict[level] = var_dict
    return node_dict

node_p_var_dict = parallel_creator( 'tpnb', l_p_idx)

# 约束4：同一个商品的网格必须连续（通过限制同层内的"断裂"次数不超过1）
for p in products.tpnb.values: 
    for shelf in range(shelf_count): 
        m.constraints.append(
            cp.sum([(node_p_var_dict[str(p)][(level, shelf)] != node_p_var_dict[str(p)][(level+1, shelf)])
                for level in range(section_width - 1)]) <= 1
            )

hassol = m.solve()
print("Status:", m.status())

备注：内容来源于stack exchange，提问作者Anand