Scholarlink

<p>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 <i>K</i>-adaptability approach, in which <i>K</i> 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Heuristic algorithms for stochastic K-adaptability

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年4月7日

查看全文
  • Enrico Malaguti,
  • Michele Monaci,
  • Jonas Pruente

摘要

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.