论文标题
一种双门，基于逻辑的弯曲器分解方法来解决K适应性问题
A Double-oracle, Logic-based Benders decomposition approach to solve the K-adaptability problem
论文作者
论文摘要
我们提出了一种新的方法来解决凸目标和限制和整数第一阶段决策的K适应性问题。采用基于逻辑的弯曲器分解来处理主问题中的第一阶段决策，因此，子问题成为一个微小的敏捷组合稳定的组合优化问题，该问题通过迭代的双门算法解决，该算法通过迭代性地产生不利的场景和追索性决策，并通过解决ksets的ksets解决方案来解决p-pcenters问题。还提供了在第一阶段目标和第二阶段约束中处理参数不确定性的提议方法的扩展。我们表明，所提出的算法会收敛到最佳解决方案并终止有限数量的迭代。从自适应最短路径问题，常规背包问题和通用K自适应问题的基准实例上获得的实验获得的数值结果证明了与文献中的最新方法相比，提出的方法的性能优势。
We propose a novel approach to solve K-adaptability problems with convex objective and constraints and integer first-stage decisions. A logic-based Benders decomposition is applied to handle the first-stage decisions in a master problem, thus the sub-problem becomes a min-max-min robust combinatorial optimization problem that is solved via a double-oracle algorithm that iteratively generates adverse scenarios and recourse decisions and assigns scenarios to K subsets of the decisions by solving p-center problems. Extensions of the proposed approach to handle parameter uncertainty in both the first-stage objective and the second-stage constraints are also provided. We show that the proposed algorithm converges to an optimal solution and terminates in finite number of iterations. Numerical results obtained from experiments on benchmark instances of the adaptive shortest path problem, the regular knapsack problem, and a generic K-adaptability problem demonstrate the performance advantage of the proposed approach when compared to state-of-the-art methods in the literature.
