ABSTRACT This article deals with the recoverable robust shortest path problem under interval uncertainty representations. In this problem, a first‐stage path is computed, which can be modified to some extent after observing changes in the cost structure. The uncertain second‐stage arc costs are modeled by intervals, and the robust min–max criterion is used to compute an optimal solution. The problem is known to be strongly NP‐hard and also hard to approximate in general digraphs. However, until now its complexity for acyclic digraphs was unknown. In this article, it is shown that the problem in acyclic digraphs can be solved in polynomial time for the traditional interval uncertainty and all natural neighborhoods known from the literature. More efficient algorithms for layered and arc series‐parallel digraphs are constructed. Hardness results for general digraphs are also strengthened. Finally, some exact and approximate methods of solving the problem under interval budgeted uncertainty are proposed.

In this paper, an optimization problem with uncertain objective function coefficients is considered. The uncertainty is specified by providing a discrete scenario set containing possible realizations of the objective function coefficients. The concept of belief function in the traditional and possibilistic setting is applied to define a set of admissible probability distributions over the scenario set. The generalized Hurwicz criterion is then used to compute a solution. In this paper, the complexity of the resulting problem is explored. Some exact and approximation methods of solving it are proposed.

In this paper a class of optimization problems with uncertain constraint coefficients is discussed. Namely, for each ill-known coefficient a possibility distribution, being a membership function of a fuzzy interval, is specified. In a possibilistic interpretation, the induced possibility distribution in the set of constraint coefficient realizations encodes a family of probability distributions in this set. The distributionally robust approach is then used to transform imprecise constraints into crisp counterparts. An extension of the model is proposed, in which individual risk aversion of decision makers is taken into account.

In this paper a robust optimization problem with uncertain objective function is considered. The uncertainty is modeled by specifying a scenario set, containing a finite number of objective function coefficients, called scenarios. Additional knowledge in scenario set can be represented by using a mass function defined on the power set of scenarios. This mass function defines a belief function, which in turn induces a family of probability distributions in scenario set. One can then use a generalized Hurwicz criterion, i.e. a convex combination of the upper and lower expectations, to solve the uncertain problem. Recently, possibility theory has been applied to extend the model of uncertainty based on belief functions. Namely, belief function can be induced by a random fuzzy set. In this paper we show how this generalized model can be applied to robust optimization.

This paper deals with a linear optimization problem with uncertain objective function coefficients modeled by possibility distributions. The fuzzy robust optimization framework is applied to compute a solution. Namely, the necessity degree that the objective value is lower than a given threshold is maximized. The aim of this paper is to take the knowledge on dependencies between the objective coefficients into account by means of a family of copula functions. It is shown that this new approach limits the conservatism of fuzzy robust optimization, better evaluates possibility distributions for the values of the objective function and do not increase the complexity of the problem.

The paper deals with a production planning problem, that is a version of the capacitated single-item lot sizing problem with backordering, under uncertain cumulative demands, modeled by fuzzy intervals centered around the cumulative demand nominal values. Their membership functions are regarded as possibility distributions for the values of the unknown cumulative demands. Furthermore, the budgeted uncertainty model is assumed, in which at most a specified number of cumulative demands can deviate from their nominal values at the same time. In order to choose a robust production plan that optimizes against plausible cumulative demand scenarios, under the model assumed, possibilistic criteria are adopted. Polynomial linear programming based methods for finding such robust production plans are proposed, showing in this way that the problem under consideration is not much computationally harder than its deterministic counterpart. Some results of computational tests are presented.

In this paper a class of combinatorial optimization problems is discussed. It is assumed that a solution can be constructed in two stages. The current first-stage costs are precisely known, while the future second-stage costs are only known to belong to an uncertainty set, which contains a finite number of scenarios with known probability distribution. A partial solution, chosen in the first stage, can be completed by performing an optimal recourse action, after the true second-stage scenario is revealed. A solution minimizing the Conditional Value at Risk (CVaR) measure is computed. Since expectation and maximum are boundary cases of CVaR, the model generalizes the traditional stochastic and robust two-stage approaches, previously discussed in the existing literature. In this paper some new negative and positive results are provided for basic combinatorial optimization problems such as the selection or network problems.

This paper discusses a linear programming problem and a general combinatorial optimization problem with uncertain parameters, whose unknown distributions are modeled by fuzzy intervals. The fuzzy intervals have possibilistic interpretation. Some criteria for choosing robust solutions to the problems under consideration, resulting from the use of possibilistic decision theory, are proposed. It is shown that the fuzzy problems constructed are computationally tractable if their deterministic counterparts are polynomially solvable. The algorithms for finding the robust solutions are provided. Some computational experiments are performed.

In this paper the following selection problem is discussed. A set of n items is given and we wish to choose a subset of exactly p items of the minimum total cost. This problem is a special case of 0–1 knapsack in which all the item weights are equal to 1. Its deterministic version has an O(n)-time algorithm, which consists in choosing p items of the smallest costs. In this paper it is assumed that the item costs are uncertain. Two robust models, namely two-stage and recoverable ones, under discrete and interval uncertainty representations, are discussed. Several positive and negative complexity results for both of them are provided.

In this paper a class of discrete optimization problems with uncertain costs is discussed. The uncertainty is modeled by providing a discrete scenario set, in which each scenario represents a possible realization of the element costs (the problem parameters). It is assumed that a partial information about scenario occurrence probabilities is also available. Namely, each such a probability is known to belong to a given closed interval. Several criteria for choosing a solution, such as the expected value, the value at risk, the conditional value at risk, and the tail α-mean are considered. A solution minimizing one of these criteria for the worst possible probability distribution in scenario set is computed. The computational complexity of the problems under consideration is explored. Some exact and approximation algorithms for them are proposed.

The paper deals with a single-item production planning problem with uncertain demands modeled by fuzzy intervals whose membership functions are possibility distributions for the values of the uncertain demands. Optimization criteria, in the setting of possibility theory, that lead to choose robust production plans under fuzzy demands are given. Algorithms for determining optimal robust production plans with respect to the proposed criteria are provided and some computational experiments are presented.

This paper deals with a class of combinatorial optimization problems with uncertain costs. The uncertainty is modeled by specifying a scenario set containing a finite number of possible realizations of the costs called scenarios. Additionally, a possibility distribution on the scenario set can be defined. Two robust models, namely the min-max and two-stage, for hedging against uncertainty of the costs in the possibilistic setting are considered. A general framework for solving the problems is proposed. For the linear sum objective a mixed integer proggraming formulation is shown. For the bottleneck objective, an algorithm is constructed which runs in polynomial time if the deterministic problem, i.e. the one with a single scenario, is polynomially solvable.

In this paper, a class of sequencing problems with uncertain parameters is discussed. The uncertainty is modeled by the usage of fuzzy intervals, whose membership functions are regarded as possibility distributions for the values of unknown parameters. It is shown how to use possibility theory to find robust solutions under fuzzy parameters; this paper presents a general framework, together with applications, to some classical sequencing problems. First, the interval sequencing problems with the minmax regret criterion are discussed. The state of the art in this area is recalled. Next, the fuzzy sequencing problems, in which the classical intervals are replaced with fuzzy ones, are investigated. A possibilistic interpretation of such problems, solution concepts, and algorithms for the computation of a solution are described. In particular, it is shown that every fuzzy problem can be efficiently solved if a polynomial algorithm for the corresponding interval problem with the minmax regret criterion is known. Some methods to deal with NP-hard problems are also proposed, and the efficiency of these methods is explored.

In this paper a combinatorial optimization problem with fuzzy weights is discussed. In order to choose a solution the concept of a necessary soft optimality is adopted. It is shown that the fuzzy problem can be reduced to solving a family of interval problems with the maximal regret criterion. Two general methods of solving the interval problems are presented. The first one is based on a branch and bound technique and the second method is based on a mixed integer programming formulation. Both techniques are general and can be applied if the underlying interval problem is NP-hard.

This paper deals with a general combinatorial optimization problem with uncertain element weights modeled by fuzzy intervals. A fuzzy interval is regarded as a possibility distribution describing the set of more or less plausible values of an element weight. In order to choose a “best” solution the concept of a necessary optimality and the concept of a necessary soft optimality are adopted. It is shown that the use of possibility theory leads to finding robust solutions under fuzzy weights. Some general algorithms that compute the degrees of necessary and necessary soft optimality of a given solution and find an optimal solution according to the introduced concepts are provided.

This paper deals with a general combinatorial optimization problem with fuzzy costs. The set of nondominated solutions with respect to an assumed fuzzy preference relation, according to the Orlovski's concept, is supposed to be the solution of the problem. A special attention is paid to the unfuzzy nondominated solutions (the solutions which are nondominated to the degree one). The main results of the paper are several new, weakened conditions on a fuzzy preference relation that allow to reduce the problem of determining unfuzzy nondominated solutions to the underling problem with deterministic costs. These solutions can be obtained by means of classical algorithms for the underling crisp problem, avoiding a construction of the special ones for the fuzzy problem. Moreover, it is shown that several known from literature fuzzy preference relations fulfill the proposed conditions. The approach is illustrated by a computational example.

The notion of the necessary criticality (both with respect to path and to activity) of a network with imprecisely defined (by means of intervals or fuzzy intervals) activity duration times is introduced and analyzed. It is shown, in the interval case, that both the problem of asserting whether a given path is necessarily critical and the problem of determining an arbitrary necessarily critical path (more exactly, a subnetwork covering all the necessarily critical paths) are easy. The corresponding solution algorithms are proposed. However, the problem of evaluating whether a given activity is necessarily critical does not seem to be so easy. Certain conditions are formulated which, in some situations (but not in all possible situations), allow the necessary criticality of activities to be evaluated. The results obtained for networks with interval activity duration times are generalized to the case of networks with fuzzy activity duration times. Two effective algorithms for calculating the degree of necessary criticality of a fixed path, as well as an algorithm for determining the paths that are necessarily critical to the maximum degree, are proposed.