满足间距与数量约束的广告牌曝光最大化线性规划模型咨询

你这个场景是带基数约束的最大权重独立集问题，属于标准的0-1整数线性规划（0-1 ILP）范畴，模型结构简单清晰，用成熟的整数规划求解器就能落地，完全不需要搞复杂的定制算法。 #

变量与参数定义 #

• 决策变量：对18000个广告牌逐一设置0-1变量x_i，x_i=1代表选中第i块广告牌，x_i=0代表不选
• 固定参数：
  • w_i：第i块广告牌的月曝光量（Impacts），即目标权重
  • d_ij：提前计算好的广告牌i、j之间的直线距离
  • D_min：用户设定的入选广告牌最小间距阈值
  • K：用户指定的需要选取的广告牌总数量

目标函数 #

直接最大化入选广告牌总曝光量：

max  Σ(i=1到18000) w_i * x_i

约束条件 #

就两类，完全覆盖你的需求：

1. 选取总数约束：所有选中的广告牌数量等于用户指定值

   Σ(i=1到18000) x_i = K
   

2. 最小间距约束：对任意一对距离小于阈值的广告牌，最多只能选其中一块

   x_i + x_j ≤ 1  （所有满足d_ij < D_min的i<j对）
   

别直接照搬教科书给全量点对加约束，18000个点的全量两两对超过3.2亿条，直接加会撑爆求解器内存，按下面的方式优化即可：

• 只给实际距离小于D_min的冲突点对加间距约束，只要D_min不是设得特别夸张，冲突对数量会比全量点对少2~3个数量级，规模完全可控
• 求解器直接选成熟的MIP（混合整数规划）求解器就行：商用可选Gurobi、CPLEX，开源可选SCIP、HiGHS，这类问题结构非常规整，求解器自带的预处理、割平面、分支定界优化效率极高，要是允许1%以内的最优性误差，开个小的MIPGap阈值，通常几分钟就能出结果
• 如果筛完冲突对规模还是偏大，可以提前把广告牌的邻接网络拆成互不连通的独立子块，每个子块单独求解再合并结果，能进一步压缩求解时间

不推荐一上来就用遗传算法、模拟退火这类无最优性保证的启发式算法，调参成本高，结果稳定性差，远不如用成熟MIP求解器跑标准整数规划模型性价比高。

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