K-adaptability in stochastic optimization
成果类型：
Article
署名作者：
Malaguti, Enrico; Monaci, Michele; Pruente, Jonas
署名单位：
University of Bologna; Dortmund University of Technology
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-021-01767-3
发表日期：
2022
页码：
567-595
关键词：
摘要：
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 NP-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.