Abstract In telecommunication networks, full connectivity resilience to multiple link failures is too costly as it requires a network topology with too many redundant links. Alternatively, the connectivity resilience of a telecommunications network can be improved by resorting to available third‐party networks for temporary additional connectivity until the failing links are restored. In this approach, some nodes of the network must be selected in advance to act as gateway nodes to the third‐party networks when a multiple link failure event occurs. For a given network topology and a cost associated with each node to turn it into a gateway node to each of the third‐party networks, the aim is to select the gateway nodes providing maximum connectivity resilience at minimum cost. The Gateway Node Selection is defined as a bi‐objective optimization problem such that its Pareto‐optimal solutions represent different trade‐offs between cost and connectivity resilience. In this work, the connectivity resilience is modeled by the Critical Link Detection optimization problem. An exact optimization algorithm is proposed, based on a row generation algorithm and on set cover cuts. The computational results demonstrate the effectiveness of the proposed algorithm on four well‐known telecommunication network topologies.

We consider a class of min-max robust problems in which the functions that need to be “robustified” can be decomposed as the sum of arbitrary functions. This class of problems includes many practical problems, such as the lot-sizing problem under demand uncertainty. By considering a Lagrangian relaxation of the uncertainty set, we derive a tractable approximation, called the dual Lagrangian approach, that we relate with both the classical dualization approximation approach and an exact approach. Moreover, we show that the dual Lagrangian approach coincides with the affine decision rule approximation approach. The dual Lagrangian approach is applied to a lot-sizing problem, in which demands are assumed to be uncertain and to belong to the uncertainty set with a budget constraint for each time period. Using the insights provided by the interpretation of the Lagrangian multipliers as penalties in the proposed approach, two heuristic strategies, a new guided iterated local search heuristic, and a subgradient optimization method are designed to solve more complex lot-sizing problems in which additional practical aspects, such as setup costs, are considered. Computational results show the efficiency of the proposed heuristics that provide a good compromise between the quality of the robust solutions and the running time required in their computation. Summary of Contribution: The paper includes both theoretical and algorithmic contributions for a class of min-max robust optimization problems where the objective function includes the maximum of a sum of affine functions. From the theoretical point of view, a tractable Lagrangian dual model resulting from a relaxation of the well-known adversarial problem is proposed, providing a new perspective of well-known models, such as the affinely adjustable robust counterpart (AARC) and the dualization technique introduced by Bertsimas and Sim. These results are particularized to lot-sizing problems. From the algorithm point of view, efficient heuristic schemes—which exploit the information based on the interpretation of the Lagrangian multipliers to solve large size robust problems—are proposed, and their performance is evaluated through extensive computational results based on the lot-sizing problem. In particular, a guided iterated local search and a subgradient optimization method are proposed and compared against the dualization approach proposed by Bertsimas and Sim and with several heuristics based on the AARC approach, which include an iterated local search heuristic and a Benders decomposition approach. Computational results show the efficiency of the proposed heuristics, which provide a good compromise between the quality of the robust solutions and the running time.

Abstract This paper addresses two related problems in the context of transparent optical networks. In the network design problem, the aim is to identify a set of fiber links to connect a given set of nodes. In the network upgrade problem, the aim is to identify a set of new fiber links to add to a given network topology. For a given fiber length budget, the aim in both problems is to maximize the network resilience to the simultaneous failure of its critical nodes. The resilience is evaluated by the average 2‐terminal reliability (A2TR) against a set of critical node failures and the critical nodes are the ones that minimize the A2TR of the network. So, the design/upgrade problem is a bi‐level max‐min optimization problem. Recently, a multi‐start greedy randomized heuristic was proposed for both problems. Here, we propose an alternative method based on a greedy deterministic algorithm and we provide computational results showing that the new method obtains better solutions. The results show that the resiliency difference between existing network topologies and the best network design solutions is very high but this difference can be significantly reduced by network upgrades with small fiber length budgets.

We consider a stochastic single item production‐inventory‐routing problem with a single producer, multiple clients, and multiple vehicles. At the clients, demand is allowed to be backlogged incurring a penalty cost. Demands are considered uncertain. A recourse model is presented, and valid inequalities are introduced to enhance the model. A new general approach that explores the sample average approximation (SAA) method is introduced. In the sample average approximation method, several sample sets are generated and solved independently in order to obtain a set of candidate solutions. Then, the candidate solutions are tested on a larger sample, and the best solution is selected among the candidates. In contrast to this approach, called static, we propose an adjustable approach that explores the candidate solutions in order to identify common structures. Using that information, part of the first‐stage decision variables is fixed, and the resulting restricted problem is solved for a larger size sample. Several heuristic algorithms based on the mathematical model are considered within each approach. Computational tests based on randomly generated instances are conducted to test several variants of the two approaches. The results show that the new adjustable SAA heuristic performs better than the static one for most of the instances.

As client demands grow, optical network operators are required to introduce lightpaths of higher line rates in order to groom more demand into their network capacity. For a given fiber network and a given set of client demands, the minimum cost network design is the task of assigning routing paths and wavelengths for a minimum cost set of lightpaths able to groom all client demands. The variant of the optical network design problem addressed in this paper considers a transparent optical network, single hop grooming, client demands of a single interface type, and lightpaths of two line rates. We discuss two slightly different mixed integer linear programming models that define the network design problem combining grooming, routing, and wavelength assignment. Then, we propose a parameters increase rule and three types of additional constraints that, when applied to the previous models, make their linear relaxation solutions closer to the integer solutions. Finally, we use the resulting models to derive a hybrid heuristic method, which combines a relax-and-fix approach with an integer linear programming-based local search approach. We present the computational results showing that the proposed heuristic method is able to find solutions with cost values very close to the optimal ones for a real nation-wide network and considering a realistic fiber link capacity of 80 wavelengths. Moreover, when compared with other approaches used in the problem variants close to the one addressed here, our heuristic is shown to compute solutions, on average, with better cost values and/or in shorter runtimes.

Abstract A single‐product maritime inventory routing problem (MIRP) is studied in which the production and consumption rates vary over the planning horizon. The problem involves a heterogeneous fleet and multiple production and consumption ports with limited storage capacity. Two discrete time formulations are developed: an original model and a reformulated model that is a pure fixed charge network flow (FCNF) model with side constraints. Mixed integer sets arising from the decomposition of the formulations are identified. In particular, several lot‐sizing relaxations are derived for the formulations and used to establish valid inequalities to strengthen the proposed formulations. Until now, the derivation of models and valid inequalities for MIRPs has mainly been inspired by the developments in the routing community. Here, we have developed a new model leading to new valid inequalities for MIRPs obtained by generalizing valid inequalities from the recent lot‐sizing literature. Considering a set of instances based on real data, a computational study is conducted to test the formulations and the effectiveness of the valid inequalities. The FCNF formulation is generally much stronger than the original formulation. The developed valid inequalities reduce the integrality gap significantly for both formulations. By using a branch‐and‐bound scheme based on the strengthened FCNF formulation, most of our test instances are solved to optimality. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 62(4), 297–314 2013