PuLP线性规划聚类问题：约束设置技术支持请求

背景 #

某产品标签空间随尺寸固定，每个标签对应一组国家-语言的聚类（聚类数量可调整，理想状态下需最少聚类数）。不同语言占用标签空间不同，同时每个国家有三类硬性需求：

• 特定BBD（最佳食用日期）格式
• 特定生产日期格式（含无需标注的情况）
• 原产地声明要求

核心需求 #

已实现国家分组与标签空间约束，但无法保证聚类内国家需求一致，需添加约束确保：

1. 每个国家仅归属一个聚类（已实现）
2. 需求不一致的国家不能被分到同一聚类：
   • 如US与CA因BBD格式不同，不能同簇
   • IN与GB因生产日期要求不同（IN需标注、GB无需），不能同簇
   • SG与AT因原产地声明不同，即使其他维度一致也不能同簇

约束实现思路 #

1. 预处理需求冲突对：遍历所有国家对，只要在BBD格式、生产日期要求、原产地声明任一维度存在差异，标记为冲突对。
2. 添加冲突约束：对每一对冲突国家(r1, r2)，添加约束：任意聚类c中，r1和r2不能同时被选中，即x_cr[(c, r1)] + x_cr[(c, r2)] ≤ 1。
3. 修正空间约束：原代码中聚类空间约束未限定最大值，需补充≤ max_language_space，同时修正重复计算语言空间的问题（同一聚类标签只需包含独特语言）。

代码修改示例 #

import pulp as lp
import numpy as np

# 原始数据定义
CTY=["SG", "AT", "BE", "BG", "CH", "CY", "CZ", "DE", "DK", "DO", "ES", "FI", "FR", "GR", "HR", "HU", "IE", "IS", "IT", "LT", "LV", "NL", "NO", "PL", "PT", "RO", "RS", "SE", "SI", "SK", "RU", "US", "PR", "CA", "AU", "NZ", "JP", "IN", "PH", "GB", "CN"]
max_language_space=5 # 标签最大允许空间
clusters=np.arange(1, 12) # 预设聚类范围，可调整

# 需求映射字典
CTY_BBD={"SG":"DD-MM-YYYY", "AT":"DD-MM-YYYY", "BE":"DD-MM-YYYY", "BG":"DD-MM-YYYY", "CH":"DD-MM-YYYY", "CY":"DD-MM-YYYY", "CZ":"DD-MM-YYYY", "DE":"DD-MM-YYYY", "DK":"DD-MM-YYYY", "DO":"DD-MM-YYYY", "ES":"DD-MM-YYYY", "FI":"DD-MM-YYYY", "FR":"DD-MM-YYYY", "GR":"DD-MM-YYYY", "HR":"DD-MM-YYYY", "HU":"DD-MM-YYYY", "IE":"DD-MM-YYYY", "IS":"DD-MM-YYYY", "IT":"DD-MM-YYYY", "LT":"DD-MM-YYYY", "LV":"DD-MM-YYYY", "NL":"DD-MM-YYYY", "NO":"DD-MM-YYYY", "PL":"DD-MM-YYYY", "PT":"DD-MM-YYYY", "RO":"DD-MM-YYYY", "RS":"DD-MM-YYYY", "SE":"DD-MM-YYYY", "SI":"DD-MM-YYYY", "SK":"DD-MM-YYYY", "RU":"DD-MM-YYYY", "US":"DD-ABC-YYYY", "PR":"DD-ABC-YYYY", "CA":"YYYY/AB/DD", "AU":"DD-MM-YYYY", "NZ":"DD-MM-YYYY", "JP":"YYYY-MM-DD", "IN":"DD-MM-YYYY", "PH":"DD-ABC-YYYY", "GB":"DD-MM-YYYY", "CN":"YYYY-MM-DD"}
CTY_production_date={"SG":"DD-MM-YYYY", "AT":"DD-MM-YYYY", "BE":"DD-MM-YYYY", "BG":"DD-MM-YYYY", "CH":"DD-MM-YYYY", "CY":"DD-MM-YYYY", "CZ":"DD-MM-YYYY", "DE":"DD-MM-YYYY", "DK":"DD-MM-YYYY", "DO":"DD-MM-YYYY", "ES":"DD-MM-YYYY", "FI":"DD-MM-YYYY", "FR":"DD-MM-YYYY", "GR":"DD-MM-YYYY", "HR":"DD-MM-YYYY", "HU":"DD-MM-YYYY", "IE":"DD-MM-YYYY", "IS":"DD-MM-YYYY", "IT":"DD-MM-YYYY", "LT":"DD-MM-YYYY", "LV":"DD-MM-YYYY", "NL":"DD-MM-YYYY", "NO":"DD-MM-YYYY", "PL":"DD-MM-YYYY", "PT":"DD-MM-YYYY", "RO":"DD-MM-YYYY", "RS":"DD-MM-YYYY", "SE":"DD-MM-YYYY", "SI":"DD-MM-YYYY", "SK":"DD-MM-YYYY", "RU":"DD-MM-YYYY", "US":"NO", "PR":"NO", "CA":"NO", "AU":"NO", "NZ":"NO", "JP":"NO", "IN":"DD-MM-YYYY", "PH":"NO", "GB":"NO", "CN":"YYYY-MM-DD"}
CTY_origin={"SG":"FP", "AT":"PI", "BE":"PI", "BG":"PI", "CH":"PI", "CY":"PI", "CZ":"PI", "DE":"PI", "DK":"PI", "DO":"PI", "ES":"PI", "FI":"PI", "FR":"PI", "GR":"PI", "HR":"PI", "HU":"PI", "IE":"PI", "IS":"PI", "IT":"PI", "LT":"PI", "LV":"PI", "NL":"PI", "NO":"PI", "PL":"PI", "PT":"PI", "RO":"PI", "RS":"PI", "SE":"PI", "SI":"PI", "SK":"PI", "RU":"NO", "US":"FP", "PR":"FP", "CA":"FP", "AU":"NO", "NZ":"NO", "JP":"FP", "IN":"NO", "PH":"NO", "GB":"NO", "CN":"FP"}
language_space={"EN_GB":1, "BG_BG":1, "CS_CZ":1, "DA_DK":1, "DE_DE":1, "EL_GR":1, "EN_GB":1, "ES_ES":1, "FI_FI":1, "FR_FR":1, "HR_HR":1, "HU_HU":1, "IT_IT":1, "LT_LT":1, "LV_LV":1, "NL_NL":1, "NO_NO":1, "PL_PL":1, "PT_PT":1, "RO_RO":1, "SK_SK":1, "SL_SI":1, "SR_RS":1, "SV_SE":1, "RU_RU":3, "EN_US":1, "EN_CA":1, "FR_CA":1, "EN_AU":1, "JA_JP":3, "EN_AU":1, "EN_IN":1, "EN_PH":1, "ZH_CN":2}
CTY_language={"SG":["EN_GB"], "AT":["DE_DE"], "BE":["FR_FR", "NL_NL"], "BG":["BG_BG"], "CH":["DE_DE", "FR_FR"], "CY":["EL_GR"], "CZ":["CS_CZ"], "DE":["DE_DE"], "DK":["DA_DK"], "DO":["ES_ES"], "ES":["ES_ES"], "FI":["FI_FI"], "FR":["FR_FR"], "GR":["EL_GR"], "HR":["HR_HR"], "HU":["HU_HU"], "IE":["EN_GB"], "IS":["FI_FI", "SV_SE"], "IT":["IT_IT"], "LT":["LT_LT"], "LV":["LV_LV"], "NL":["NL_NL"], "NO":["NO_NO"], "PL":["PL_PL"], "PT":["PT_PT"], "RO":["RO_RO"], "RS":["SR_RS"], "SE":["SV_SE"], "SI":["SL_SI"], "SK":["SK_SK"], "RU":["RU_RU"], "US":["EN_US"], "PR":["EN_US"], "CA":["EN_CA", "FR_CA"], "AU":["EN_AU"], "NZ":["EN_AU"], "JP":["JA_JP"], "IN":["EN_IN"], "PH":["EN_PH"], "GB":["EN_GB"], "CN":["ZH_CN"]}

# 初始化问题
prob = lp.LpProblem('Cluster_Optimization', lp.LpMaximize)
# 定义决策变量：x(c,r)=1表示国家r属于聚类c
x_cr = lp.LpVariable.dicts('x', [(c, r) for c in clusters for r in CTY], 0, 1, lp.LpBinary)

# 目标函数：示例为最大化聚类覆盖的国家销量/份额（需自行补充销量数据）
# 假设每个国家有销量数据sales[r]，则目标函数为：
# prob += lpSum([sales[r] * x_cr[(c, r)] for c in clusters for r in CTY])

# 约束1：每个国家仅属于一个聚类
for r in CTY:
    prob += lpSum(x_cr[(c, r)] for c in clusters) == 1

# 约束2：每个聚类的标签空间不超过最大值
all_languages = set()
for r in CTY:
    all_languages.update(CTY_language[r])

for c in clusters:
    # 计算聚类c的总空间：汇总该聚类所有独特语言的空间
    prob += lpSum([
        language_space[l] * lp.lpSum([x_cr[(c, r)] for r in CTY if l in CTY_language[r]])
        for l in all_languages
    ]) <= max_language_space

# 约束3：需求不一致的国家不能同属一个聚类
# 预处理所有冲突国家对
conflicting_pairs = []
for i in range(len(CTY)):
    r1 = CTY[i]
    for j in range(i+1, len(CTY)):
        r2 = CTY[j]
        # 检查三个需求维度是否有差异
        if (CTY_BBD[r1] != CTY_BBD[r2] 
            or CTY_production_date[r1] != CTY_production_date[r2]
            or CTY_origin[r1] != CTY_origin[r2]):
            conflicting_pairs.append((r1, r2))

# 添加冲突约束
for r1, r2 in conflicting_pairs:
    for c in clusters:
        prob += x_cr[(c, r1)] + x_cr[(c, r2)] <= 1

# 求解
prob.solve()

# 输出结果
print("聚类结果：")
for c in clusters:
    cluster_countries = [r for r in CTY if lp.value(x_cr[(c, r)]) == 1]
    if cluster_countries:
        print(f"聚类{c}: {cluster_countries}")

补充说明 #

• 空间约束修正：原代码重复计算了同一语言的空间，实际标签只需包含聚类内所有国家的独特语言，因此代码中调整为汇总独特语言的空间之和。
• 聚类数量优化：若需自动寻找最少聚类数，可先设置较大的聚类范围，求解后统计实际使用的聚类数，或通过多阶段优化（先最小化聚类数，再最大化目标指标）实现。

内容的提问来源于stack exchange，提问作者Andmi