基于线性阈值模型的候选中间节点部署：一种分支与贝恩斯割方法

《Mathematics》：Candidate Intermediary Node Deployment Under the Linear Threshold Model: A Branch-and-Benders-Cut Approach

　　**摘要**本文研究在线性阈值模型（LTM）下影响传播的候选中介节点部署问题。给定固定的传播源节点、目标节点和预算，决策者需要选择候选中介节点以最大化被激活目标节点的期望总权重。候选节点一旦被部署，其关联的潜在弧中另一端点属于有效网络的那些弧将被激活。利用LTM的活弧表示方法，我们建立了如下分布等价性：在潜在图上采样后对每个情景进行有效网络诱导子图的限制，与直接在部署后的网络上采样是分布等价的。基于此，我们提出了一个基于规范活路径的有限情景样本均值逼近（SAA）混合整数规划模型。所得的部署目标函数是单调且超模的，但通常不是次模的，因此经典的单调次模最大化贪心近似保证一般不适用。由于紧凑的SAA模型包含大量的情景-目标变量和覆盖约束，直接求解该模型计算代价高昂。因此，我们提出了一种情景分解的分支-Benders割算法，以最优性求解有限情景SAA模型。每个情景子问题可按目标节点分离且具有闭式对偶最优解，因此Benders割通过扫描所需节点集合来分离，而非在回调中求解线性规划。在五个真实网络和225个SAA实例上，该算法在一小时内解决了所有实例，平均耗时27.46秒；而紧凑SAA模型仅解决了172个实例，平均受限时间为1444.11秒。