Robust optimization models and algorithms for the problems in telecommunication and logistics

Abstract

We consider several optimization problems in the telecommunication network and logistics subject to data uncertainty. To handle the uncertainty of data efficiently, we adopt the robust optimization methodology. The goal of the robust optimization is to obtain a solution which is feasible for all possible realizations of input data. We present formulations of the problems and propose exact solution algorithms for the robust solution. First, we consider the network design problem without flow bifurcations. We need to determine the capacity configuration for the edges of the network, which minimizes the sum of total transportation and installation cost while respecting the demand requirements. The demand data are assumed to be uncertain, so we define an uncertainty set for each demand data and a parameter to control the degree of robustness. The goal of the problem is to find an optimal solution which is immune to all possible demand data variations defined by the uncertainty sets and the given parameter. With a mathematical formulation, we propose a solution algorithm for this robust version of the network design problem. We propose a branch-and-price-and-cut algorithm to solve the problem exactly, which enables us to transfer the difficulties arising from data uncertainty to the column generation subproblem. In our algorithm, the column generation subproblem is represented as the robust knapsack problem, and we also present a solution algorithm to solve it. Additionally, we show that we can obtain a complete description of the robust knapsack polytope for each edge of the network. Consequently, we show that the robustness of the solution can be achieved via classical deterministic solution algorithm with small modifications. The results from computational experiments indicate that the robust optimization approach can provide much robust solution at a rather small penalty in the objective value. Next, we consider a network design problem with flow bifur...