K-adaptability in stochastic optimization
研究了目标函数和可行集均受不确定性影响的随机问题，采用K适应性方法，先计算K个解再根据实际场景选择最优，分析了问题的计算复杂性并提出了精确算法。
Abstract We consider stochastic problems in which both the objective function and the feasible set are affected by uncertainty. We address these problems using a K -adaptability approach, in which K solutions for a given problem are computed before the uncertainty dissolves and afterwards the best of them can be chosen for the realized scenario. We analyze the complexity of the resulting problem from a theoretical viewpoint, showing that, even in case the deterministic problem can be solved in polynomial time, deciding if a feasible solution exists is $$\mathcal {NP}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>NP</mml:mi> </mml:math> -hard for discrete probability distributions. Besides that, we prove that an approximation factor for the underlying problem can be carried over to our problem. Finally, we present exact approaches including a branch-and-price algorithm. An extensive computational analysis compares the performances of the proposed algorithms on a large set of randomly generated instances.