.png){kind=icon}
.png){kind=icon}
Return
Heuristic algorithms for stochastic K-adaptability
.png){kind=icon}
PRE
AI
DOI：10.1007/s11590-026-02292-y.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Stochastic programming
K-adaptability
Heuristic algorithms
Computational experiments
Journal
O
IF:
1.1
Papers:
72
Citations:
2.4K