Flexible‐attribute problems

Flexible‐attribute problems

0.00 Avg rating0 Votes
Article ID: iaor20108954
Volume: 47
Issue: 3
Start Page Number: 553
End Page Number: 566
Publication Date: Nov 2010
Journal: Computational Optimization and Applications
Authors: ,
Keywords: scenario analysis and planning, uncertainty
Abstract:

Problems with significant input‐data uncertainty are very common in practical situations. One approach to dealing with this uncertainty is called scenario planning, where the data uncertainty is represented with scenarios. A scenario represents a potential realization of the important parameters of the problem. In this paper we present a new approach to coping with data uncertainty, called the flexibility approach. Here a problem is described as a set of interconnected simple scenarios. The idea is to find a solution for each scenario such that, after a change in scenario, transforming from one solution to the other one is not expensive. We define two versions of flexibility and hence two versions of the problem, which are called the sum‐flexible‐attribute problem and the max‐flexible‐attribute problem. For both problems we prove the ensuremath 𝒩𝒫 equ1 ‐hardness as well as the non‐approximability. We present polynomial time algorithms for solving the two problems to optimality on trees. Finally, we discuss the possible applications and generalizations of the new approach.

Reviews

Required fields are marked *. Your email address will not be published.