Heuristic algorithms for stochastic K-adaptability

Abstract We study stochastic optimization problems where both the objective function and the feasible set are subject to uncertainty. To address these challenges, we adopt a K -adaptability approach, in which K candidate solutions are computed prior to the realization of uncertainty, and the best among them is selected once the actual scenario is known. We introduce a simple lower bounding procedure, for which we study the worst-case performance ratio. In addition, we propose two heuristic approaches tailored to this class of problems. The first one is an iterative approach that starts from a feasible solution, progressively improves it, and applies a diversification phase to escape from local optima. The second approach is instead based on a truncated enumerative scheme applied to a mathematical formulation of the problem. Furthermore, a refinement procedure is also presented for possibly improving feasible solutions. The performance of these methods is evaluated based on their gap with respect to the lower bound on a large set of instances describing stochastic variants of the unconstrained binary problem, of the knapsack problem, and of the multidimensional knapsack problem.