Biblio

Real-world problems are usually composed of two or more (potentially NP-Hard) problems that are interdependent on each other. Such problems have been recently identified as "multi-hard problems" and various strategies for solving them have been proposed. One of the most successful of the strategies is based on a decomposition approach, where each of the components of a multi-hard problem is solved separately (by state-of-the-art solver) and then a negotiation protocol between the sub-solutions is applied to mediate a global solution. Multi-hardness is, however, not the only crucial aspect of real-world problems. Many real-world problems operate in a dynamically-changing, uncertain environment. Special approaches such as risk analysis and minimization may be applied in cases when we know the possible variants of constraints and criteria, as well as their probabilities. On the other hand, adaptive algorithms may be used in the case of uncertainty about criteria variants or probabilities. While such approaches are not new, their application to multi-hard problems has not yet been studied systematically. In this paper we extend the benchmark problem for multi-hardness with the aspect of uncertainty. We adapt the decomposition-based approach to this new setting, and compare it against another promising heuristic (Monte-Carlo Tree Search) on a large publicly available dataset. Our comparisons show that the decomposition-based approach outperforms the other heuristic in most cases.