论文标题
与本地预算的不确定性相关的强大组合优化
Robust Combinatorial Optimization with Locally Budgeted Uncertainty
论文作者
论文摘要
预算不确定性集已被确定为对强大优化问题的不确定性建模的主要影响。这种集合的缺点是，预算约束仅限制了对手可以分配的全球成本增加。本地限制虽然对许多应用程序很重要，但不能以这种方式建模。 我们介绍了预算不确定性集的新变体，称为本地预算不确定性。在这种情况下，不确定的参数被分配，因此每个分区（称为区域）适用于经典的预算不确定性集。 在理论分析中，我们表明，如果在多项式时间内也可以解决潜在的标称问题，那么在多项式时间内，恒定区域的此类问题的强大对应仍然可以解决。如果区域的数量无限，我们表明可靠的选择问题在多项式时间内仍然可以解决，同时也为其他组合问题提供硬度结果。 在使用随机和现实世界数据的计算实验中，我们表明，使用本地预算的不确定性集比经典预算的不确定性集具有相当大的优势。
Budgeted uncertainty sets have been established as a major influence on uncertainty modeling for robust optimization problems. A drawback of such sets is that the budget constraint only restricts the global amount of cost increase that can be distributed by an adversary. Local restrictions, while being important for many applications, cannot be modeled this way. We introduce new variant of budgeted uncertainty sets, called locally budgeted uncertainty. In this setting, the uncertain parameters become partitioned, such that a classic budgeted uncertainty set applies to each partition, called region. In a theoretical analysis, we show that the robust counterpart of such problems for a constant number of regions remains solvable in polynomial time, if the underlying nominal problem can be solved in polynomial time as well. If the number of regions is unbounded, we show that the robust selection problem remains solvable in polynomial time, while also providing hardness results for other combinatorial problems. In computational experiments using both random and real-world data, we show that using locally budgeted uncertainty sets can have considerable advantages over classic budgeted uncertainty sets.
