Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Over the last years, professionals dealing with real-world optimization problems have increased their interest in embedding uncertainty in their decision process, showing particular attention to tractable robust optimization (RO) techniques. The goal of RO is to find an optimal solution that is deterministically protected against the worst coefficient deviations specified by an uncertainty set (we refer the reader to [3, 4] for a comprehensive introduction to theory and applications of RO). Among the RO models proposed over the years, the \(\varGamma \)-robustness model of Bertsimas and Sim (\(\varGamma \)-Rob) [5] was a breakthrough in the development of tractable robust counterparts and has without doubt been the most successful and widely applied model. However, as pointed out by its authors, the assumptions at the basis of \(\varGamma \)-Rob may sensibly limit the possibility of modeling arbitrary-shaped distributions of the uncertainty that are commonly found in real-world problems, and lead to overconservative robust solutions (for a more detailed discussion of the limits of \(\varGamma \)-Rob, we refer the reader to [2, 6, 7]). Starting with the work [6], we have studied the possibility of refining \(\varGamma \)-Rob by exploiting a very simple operation: partitioning the single deviation band into multiple bands, each with its own parameters. This operation is at the basis of the general theoretical study that we have started to fill the gap of knowledge about the use of a multiband uncertainty set in RO.

2 Multiband Uncertainty

We consider a generic uncertain mixed-integer linear program (MILP):

$$\begin{aligned} \max ~ \sum _{j\in J} c_{j} ~ x_{j} \quad \text{ s.t. } ~~&\sum _{j\in J}a_{ij}~x_{j}\le b_{i}~, ~~ i \in I=\{1,\ldots ,m\},\\&x_{j} \ge 0 \quad , ~~ j\in J=\{1,\ldots ,n\}, \quad x_{j} \in \mathbb {Z}^+, ~~ j \in J^{\mathbb {Z}} \subseteq J. \end{aligned}$$

where we assume without loss of generality that uncertainty only affects the coefficients \(a_{ij}\). We model the uncertainty through a multiband uncertainty set \(\mathcal {S}_{M}\), a natural generalization of \(\varGamma \)-Rob (see [6, 7] for a comparison between the two models). Specifically, we assume that for each coefficient \(a_{ij}\) we are given its nominal value \(\overline{a}_{ij}\) and maximum negative and positive deviations \(d_{ij}^{K^{-}},d_{ij}^{K^{+}}\) from \(\overline{a}_{ij}\). The actual value \(a_{ij}\) then lies in the interval \([\bar{a}_{ij}+d_{ij}^{K^{-}},\bar{a}_{ij}+d_{ij}^{K^{+}}]\). We derive the generalization of \(\varGamma \)-Rob by partitioning the single deviation band \([d_{ij}^{K-},d_{ij}^{K+}]\) for each coefficient \(a_{ij}\) into \(K\) bands, defined on the basis of \(K\) deviation values: \(-\infty < {d_{ij}^{K^{-}}<\cdots <d_{ij}^{-1} ~<~d_{ij}^{0}=0~<~ d_{ij}^{1}<\cdots <d_{ij}^{K^{+}}} <+\infty .\) We use these deviation values to define: (1) a set of positive deviation bands, such that each band \(k\in \{1,\ldots ,K^{+}\}\) corresponds to the range \((d_{ij}^{k-1},d_{ij}^{k}]\); (2) a set of negative deviation bands, such that each band \(k \in \{K^{-}+1,\ldots ,-1,0\}\) corresponds to the range \((d_{ij}^{k-1},d_{ij}^{k}]\) and band \(k = K^{-}\) corresponds to the single value \(d_{ij}^{K^{-}}\) (note that the interval of each band except \(k =K^{-}\) is therefore open on the left). With a slight abuse of notation, we denote a generic deviation band by the index \(k\), with \(k \in K = \{K^{-},\ldots ,-1,0,1,\ldots ,K^{+}\}\) and the corresponding range by \((d_{ij}^{k-1}, d_{ij}^{k}]\).

In order to complete the description of the uncertainty set, for each band \(k\in K\), we introduce two values \(l_k, u_{k} \in \mathbb {Z}^{+}\): \(0 \le l_k \le u_{k} \le n\), which respectively represent a lower bound and an upper bound on the number of deviations that may fall in \(k\). As additional assumptions, we do not limit the number of coefficients that may take their nominal value, i.e. \(u_{0}=n\), and we impose that \(\sum _{k \in K} l_k \le n\), to ensure the existence of a feasible realization of the coefficient matrix.

The robust counterpart of the program MILP can be defined by inserting in each constraint \(i \in I\) the term \(DEV_i(x,\mathcal {S}_{M})\) that represents the maximum deviation allowed by the multiband uncertainty set for a solution \(x \), (i.e., a robust constraint looks like \(\sum _{j\in J}a_{ij}x_{j} \,+\, DEV_i(x,\mathcal {S}_{M}) \le b_{i}\)). The term \(DEV_i(x,\mathcal {S}_{M})\) is equal to the optimal value of a 0–1 linear maximization program that finds the worst coefficient distribution over the deviation bands for \(x\) (see [6] for details). The resulting robust counterpart is thus non-linear. However, using duality theory, we proved that this problem can be reformulated as a compact and linear problem, as stated in the following theorem (we refer the reader to [6, 7] for the formal complete statements and proofs of the theorems presented in this section).

Theorem 1

[Büsing and D’Andreagiovanni, 2012] The robust counterpart of MILP under the multiband uncertainty set is equivalent to a compact mixed-integer linear program, which includes \(K \cdot m \,+\, n \cdot m\) additional variables and \(K \cdot n \cdot m\) additional constraints.

In the case of large uncertain programs, the increase in size of the robust counterpart may represent an issue for obtaining a robust optimal solution quickly. We have thus investigated the possibility of developing a cutting-plane algorithm based on the separation of robustness cuts, that is, cuts that impose robustness. The basic question is simple: we are given a solution to the considered problem and we desire to check whether the solution is robust and feasible. If this is not the case, we separate a robustness cut and we add it to the problem, solving the new resulting problem. This step can be iterated as in a typical cutting-plane approach, until no robustness cut is needed and thus the generated solution is robust and optimal. In the case of \(\varGamma \)-Rob, the separation of a robustness cut is trivial and just consists in sorting the deviations and choosing the worst \(\varGamma > 0\) [11]. This straightforward approach is not valid for multiband uncertainty, but we proved anyway that the separation can be done efficiently (see [6, 7] for the formal statement and the detailed description of how the min-cost flow instance is built):

Theorem 2

[Büsing and D’Andreagiovanni, 2012] Under multiband uncertainty, the separation of a robustness cut for a constraint of MILP can be done in polynomial time by solving a min-cost flow problem.

3 Multiband Robustness for 0–1 Programs

We now focus attention on the following 0-1 linear program:

$$\begin{aligned} \max&\sum _{j\in J} c_{j} ~ x_{j}&\text{(BP) }\\&x_{j} \in X \subseteq \{0,1\}^n&j\in J, \end{aligned}$$

in which the cost coefficients \(c_j\) are supposed to be non-negative (important optimization problems, like the shortest path problem and the minimum spanning tree problem, present this structure). Furthermore, we assume that the cost coefficients are subject to uncertainty and that uncertainty is modeled by a multiband set as follows: for each cost coefficient, we are given the nominal cost \(\bar{c}_{j}\) and a sequence of \(K^{+} + 1\) deviation values \(d_{j}^{k}\), with \(k\in K=\{0,\ldots ,K^{+}\}\), such that \(0 = d_{j}^{0} <d_{j}^{1}<\cdots <d_{j}^{K+}<\infty \) (we remark that in contrast to the previous section, we consider here without loss of generality only positive deviations). Through these values, we define: (1) the zero-deviation band corresponding to the single value \(d_{j}^{0}=0\); (2) a set \(K^{+}\) of positive deviation bands, such that each band \(k\in K \backslash \{0\}\) corresponds to the range \((d_{j}^{k-1},d_{j}^{k}]\). Finally, we introduce values \(l_k,u_k \in \mathbb {Z}\), with \(0 \le l_k \le u_k \le n\), to represent the lower and upper bounds on the number of deviations falling in each band \(k \in K\).

As BP is a special case of MILP, by Theorem 1, the compact and linear robust counterpart of BP is (see [7] for details):

$$\begin{aligned} \max&\sum _{j\in J} c_{j} ~ x_{j} + \sum _{k \in K} \theta _{k} ~ w_{k} + \sum _{j\in J} z_{j}&\text{(Rob-BP) } \nonumber \\&w_k + z_{j} \ge d_{j}^{k} ~ x_{j}&j\in J, k \in K\end{aligned}$$
(1)
$$\begin{aligned}&w_k, ~ z_{j} \ge 0&j\in J, k \in K \\&x_{j} \in X \subseteq \{0,1\}^n&j\in J \; , \nonumber \end{aligned}$$
(2)

in which we note (i) the presence of additional non-negative variables (1); (ii) the presence of additional constraints (1); (iii) the insertion of additional terms in the objective function. The coefficients \(\theta _{k} \ge 0\) constitute the so-called profile of the multiband uncertainty set and are equal to the number of coefficients that must fall in the band \(k\) to maximize the deviation (the values \(\theta _{k}\) are derived from the values \(l_k,u_k\) exploiting domination between feasible realizations of the uncertainty set [7]).

A robust optimal solution can be computed by solving Rob-BP or by adopting the cutting-plane approach based on robustness cuts and presented in the previous section. Anyway, as an alternative to these two general approaches, we proved the following special result (see [7] for details):

Theorem 3

The robust optimal solution of BP with cost uncertainty modeled through a multiband set can be computed by solving a polynomial number of nominal problems BP with modified objective function, if the number of bands is constant. Tractability and approximability of BP are maintained.

In addition to these results, we characterized a new family of valid inequalities for the robust counterpart of BP, by adopting a proof strategy similar to that of Atamtürk for \(\varGamma \)-Rob [1] (see [10] for the proof).

Proposition 1

For any \(k\in K\) and subset \(T=\{j_1, j_2, \ldots , j_t\} \subseteq J\) with \(0=d_{j_0}^k\le d_{j_1}^k \le \cdots \le d_{j_t}^k\), the following inequality is valid for problem (Rob-BP):

$$\begin{aligned} \sum _{j_l \in T}\left( d_{j_l}^k-d_{j_{l-1}}^k\right) x_{j_l} \le w_{k}+\sum _{j\in T}z_{j} \end{aligned}$$

Additionally, if \(\quad 0=d_{j_0}<\cdots <d_{j_t}\), then the previous inequalities are facet-defining.

4 Robust Wireless Network Design

We used our new results about uncertain 0–1 programs in a set of preliminary experiments considering a central problem in wireless network design: the power assignment problem (PAP). The PAP considers the design of a wireless network made up of a set of transmitters \(T\) providing a telecommunication service to a set of users \(U\). It essentially consists of setting power emissions of the transmitters, while minimizing a function of emitted powers. For an exhaustive introduction to the wireless network design problem and to the PAP, we refer the reader to [8, 12]. The PAP has recently regained attention, due to ongoing switches from analog to digital television that have taken place in many countries over the last years. Here, we consider a variant of the PAP that has been recently brought to our attention from our partners in former industrial cooperations: instead of minimizing the simple summation of the power emission, we multiply the power of each transmitter by the price paid to buy the power (big network operator can indeed profit from special energy fees, which usually vary from transmitter to transmitter). This variant of the PAP can be modeled as follows: we use a vector of non-negative continuous variables \(p\) to represent the power emissions of transmitters. Then we introduce (1) a vector \(\pi \) to represent the price of a energy unit for each transmitter, (2) a matrix \(A\) to represent signal attenuation for each transmitter-user pair, (3) a vector \(\delta \) to represent the minimum power that guarantees service coverage for a user (signal-to-interference threshold). Using these elements, the PAP can be written in the following matrix form:   \( \min _{p} ~ \{ ~ \pi ' p: ~ A p \ge \delta , ~ p \ge 0^{|U|} \} \). Because of the presence of the attenuation coefficients that may vary in a very wide range, this formulation is known to lead to numerical instability in the solution process, which may greatly reduce the effectiveness of commercial optimization solvers. As a remedy, in our computational study, we have considered a tighter pure 0–1 formulation, the so-called power-indexed formulation, based on the use of discrete power variables and of a special family of generalized upper bound cover inequalities (see [8, 9] for details).

The energy price coefficients of the objective function are supposed to be subject to uncertainty: a big wireless operator can indeed establish energy contracts based on favorable prices that may however fluctuate (within limits) due to load conditions of the energy network and to variability of price formation dynamics of the energy market. Under these conditions, professionals would be interested in getting robust solutions to the PAP, namely power configurations satisfying the coverage constraints, while minimizing the total power expense and taking into account price deviations specified by an uncertainty set reflecting their risk aversion. If the uncertainty is modeled by a multiband set, the resulting robust counterpart of the problem can be solved by adopting the sequential solution approach sketched in Theorem 3: indeed, we face a (pure binary) power-indexed formulation of the PAP, where the uncertainty only affects the price coefficients in the objective function. Based on a series of discussions with experts, we suppose that each price coefficient is distributed according to a histogram resembling the shape of an exponential distribution. The adoption of the Bertsimas-Sim \(\varGamma \)-robustness model would provide a low-resolution modeling of such histogram. The multiband uncertainty model grants in contrast a more accurate representation that reduces conservatism. Based on discussions aimed at pointing out the risk aversion of the professionals, we adopted a system of 5 deviation bands. Our experiments considered a set of 15 realistic network instances of increasing size (including up to 150 users and 10 transmitters), all based on the WiMAX technology. All the experiments were made on a 2.70 GHz machine with 8 GB RAM and using IBM ILOG Cplex 12.1 as optimization solver.

The main purpose of our tests was to compare the efficiency of solving directly the compact formulation (Rob-BP) with that of the sequential approach sketched in Theorem 3 and formalized in [7]. The sequential approach performed slower in the case of 5 instances, while in all the other cases it reduced the solution time of 12 % on average. Taking into account the computational challenge of a power-indexed PAP, we consider this reduction significative and we believe that it could be enhanced by a smart exploitation of the new family of (strong) valid inequalities identified in Proposition 1, which will be the object of future experimentation. From the point of view of the price of robustness, the refined representation of the uncertainty granted by the multiband set guaranteed a reduction of up to 15 % in the conservatism of the robust optimal solution with respect to \(\varGamma \)-robustness (thus sensibly reducing the increase in power expense that a network operator must face to protect against price fluctuations).