Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion

Abstract

In this paper a class of bottleneck combinatorial optimization problems with uncertain costs is discussed. The uncertainty is modeled by specifying a discrete scenario set containing a finite number of cost vectors, called scenarios. In order to choose a solution the Ordered Weighted Averaging aggregation operator (OWA for short) is applied. The OWA operator generalizes traditional criteria in decision making under uncertainty such as the maximum, minimum, average, median, or Hurwicz criterion. New complexity and approximation results in this area are provided. These results are general and remain valid for many problems, in particular for a wide class of network problems.

Introduction

In a combinatorial optimization problem we are given a finite set of elements $E=\{e_1,\dots ,e_n\}$ and a set of feasible solutions $\Phi \subseteq 2^E$. In a deterministic case, each element $e_i\in E$ has some nonnegative cost $c_i$ and we seek a feasible solution $X\in \Phi$ for which a given cost function $F\left(X\right)$ attains the minimum. Two types of the cost function are commonly used. The first one, called a linear sum cost function, is defined as $F\left(X\right)={\sum }_{e_i\in X}{c}_i$, and the second, called a bottleneck cost function, is defined as $F\left(X\right)={max}_{e_i\in X}{c}_i$. In this paper, we focus on the bottleneck cost function and we consider the following bottleneck combinatorial optimization problem:

$$\mathcal{BP}:\underset{X\in \Phi }{min}F\left(X\right)=\underset{X\in \Phi }{min}\underset{e_i\in X}{max}{c}_i\text{.}$$

Formulation (1) encompasses a large class of problems. In this paper we will consider an important class of network problems, where $E$ is a set of arcs of a given graph $G$ and $\Phi$ contains the subsets of the arcs forming some object in $G$ such as $s-t$ paths (Bottleneck Path), spanning trees (Bottleneck Spanning Tree), $s-t$ cuts (Bottleneck Cut), or perfect matchings (Bottleneck Assignment). All these network problems are polynomially solvable and were discussed, for example, in  [8], [9], [16], [17].

Because the size of the set $\Phi$ is typically exponential in $n$, we provide with $E$ an efficient description of $\Phi$, for example a set of constraints that define $\Phi$ or a polynomial time algorithm, which decides whether a given subset of the elements belongs to $\Phi$. We will also consider the following problem $\mathcal{FBP}$ associated with $\mathcal{BP}$: given a set of elements $E$ and an efficient description of $\Phi$, check if $\Phi$ is nonempty and if so, return any solution from $\Phi$. For instance, in Bottleneck Path, the $\mathcal{FBP}$ problem consists in checking if there is at least one path between two distinguished nodes of a network encoded in some standard way and if so, returning any such a path. It is easy to verify that $\mathcal{BP}$ can always be reduced to solving at most $n$ problems $\mathcal{FBP}$ and an algorithm works as follows. We first order the elements of $E$ with respect to nonincreasing costs and remove them one by one in this order, each time solving the resulting $\mathcal{FBP}$ problem with the modified description of $\Phi$. We stop when $\Phi$ becomes empty and the last feasible solution enumerated must minimize the bottleneck cost. This method is general and implies that $\mathcal{BP}$ is polynomially solvable if only $\mathcal{FBP}$ is polynomially solvable. We will make use of this idea later in this paper. Let us, however, point out that for some particular problems faster algorithms exist and for descriptions of them we refer the reader to  [8], [9], [16], [17].

The assumption that the element costs are precisely known in advance is often unrealistic. In many cases decision makers can rather provide a set of possible realizations of the element costs. This set is called a scenario set and will be denoted by $\Gamma$. Each vector $c=(c_1,\dots ,c_n)\in \Gamma$ is called a scenario and represents a realization of the element costs which may occur with a positive but perhaps unknown probability. Several methods of describing a scenario set $\Gamma$ were proposed in the existing literature. Among the most popular are the discrete and interval uncertainty representations  [13]. In the discrete uncertainty representation, which will be used in this paper, $\Gamma =\{c_1,\dots ,c_K\}$ contains $K\ge 1$ explicitly given cost scenarios. In the interval uncertainty representation, it is assumed that each element cost may fall within some closed interval and $\Gamma$ is the Cartesian product of all these intervals. In the discrete uncertainty representation, each scenario can model some event that has a global influence on the element costs. On the other hand, the interval uncertainty representation is appropriate when each element cost may vary within some range independently on the values of the other costs. Some other methods of defining scenario sets were described, for instance, in  [4], [6], [7].

When scenario set $\Gamma$ contains more than one scenario, an additional criterion is required to choose a solution. If no probability distribution in $\Gamma$ is provided, then the robust optimization framework is widely used  [6], [13]. The idea of robust optimization is to choose a solution minimizing a worst case performance over $\Gamma$. A typical robust criterion is the maximum, i.e. we seek a solution minimizing the largest cost over all scenarios. It turns out that for the linear sum cost function the minmax problems are typically NP-hard for two scenarios even if the underlying deterministic problem is polynomially solvable. This is the case for the minmax versions of the shortest path  [13], selecting items  [3] and other classical problems described, for instance, in  [1], [13]. On the other hand, for the bottleneck cost function the situation is quite different. If the deterministic $\mathcal{BP}$ problem is polynomially solvable, then its minmax version with $K$ scenarios is also polynomially solvable (a straightforward proof of this fact can be found in  [1]). Interestingly, a similar result holds for the interval uncertainty representation and the minmax regret criterion  [2]. In consequence, the robust bottleneck problems are easier to solve than their corresponding versions with the linear sum cost function.

The robust (minmax) approach is often regarded as too conservative or pessimistic. It follows from the fact that the minmax criterion takes into account only one, the worst-case scenario, ignoring the information connected with the remaining scenarios. This fact is well known in decision theory and sample problems in which the minmax criterion seems to be not appropriate can be found, for example, in  [14].

In this paper, we consider the discrete scenario uncertainty representation, so we assume that the scenario set $\Gamma$ contains $K$ distinct cost scenarios. In order to choose a solution we use theOrdered Weighted Averaging aggregation operator (OWA for short) proposed by Yager in  [18]. The key element of the OWA operator are weights whose number equals the number of scenarios. Namely, the $j$th weight expresses the importance of the $j$th largest solution cost over all scenarios. By using various weight distributions one can obtain different criteria such as the maximum, minimum, average, median or Hurwicz. The weights can model an attitude of decision makers towards the risk and allow them to take more information into account while computing a solution. The OWA operator is typically used in multiobjective decision problems (see, e.g.,  [10], [11], [15]). However, it is natural to use it also under uncertainty by treating each scenario as a criterion. In this paper we explore the computational properties of the problem of minimizing the OWA criterion in bottleneck combinatorial optimization problems for various weight distributions.