带联合机会约束的集合分割整数规划及其分支定价算法

Branch-and-Price for Set-Partitioning Integer Programming with Joint Chance Constraints

摘要: 本文研究一类带路径联合机会约束的集合分割整数规划问题，各节点服务时间相互独立且服从有限离散分布。以路径变量为决策对象，在多资源约束下要求每条路径各节点时间窗同时满足的概率不低于给定阈值。针对可行路径数量庞大和概率可行性判定复杂的特点，设计分支定价算法：以列生成求解线性松弛，以资源约束初等最短路为定价子问题；通过离散卷积与时间窗投影递推未归一化概率质量，结合概率标签支配与带起点索引的弧分支，明确完整定价认证线性松弛下界的条件。数值实验表明，该方法可为30~100个服务节点的确定性算例构造经完整定价认证的线性松弛下界；消融实验中，改进策略使平均计算时间减少12.9%，根下界认证率由94.4%提高至100%。20和30个服务节点的随机算例进一步揭示可靠性阈值对可行路径集合与目标值的影响。该方法为此类整数规划提供可行解与线性松弛下界。

Abstract: This paper studies a class of set-partitioning integer programming problems with route-level joint chance constraints. Service times at different nodes are mutually independent and follow finitely supported discrete distributions. Path-selection decisions are represented by variables, and multiple resource constraints are incorporated into the model. For each selected path, the joint chance constraint requires the probability of simultaneously satisfying the time windows of all service nodes to be no lower than a prescribed threshold. To address the large number of feasible paths and the complexity of evaluating probabilistic feasibility, a branch-and-price algorithm is developed. Column generation solves the linear relaxation, with pricing formulated as an elementary shortest path problem with resource constraints. We recursively propagate unnormalized probability mass via discrete convolution and time-window projection, and combine probability-based label dominance with origin-indexed arc branching to establish the conditions under which complete pricing certifies a valid lower bound for the linear programming relaxation. Numerical experiments show that the method can construct linear-relaxation lower bounds certified by complete pricing for deterministic instances with 30 to 100 service nodes. Ablation experiments show that the improved strategies reduce mean computation time by 12.9% and increase the root-bound certification rate from 94.4% to 100%. Stochastic instances with 20 and 30 service nodes further illustrate how the reliability threshold affects the feasible path set and the objective value. The proposed method provides feasible solutions and linear relaxation lower bounds for this class of integer programs.