Distributionally Robust Multi-Commodity Network Design Problems under Demand Ambiguity

ABSTRACT. Network design problems (NDPs) are commonplace in the development of modern society. From the installation of cables by internet service providers, to the widening of roads by the government, NDPs play an important role in ensuring that organizations are able to meet demands from their clients while ensuring that they expend as little of their resources as they reasonably can. However, with the fluctuating demands of clients, it is in the best interest of these organizations to have a network design solution that is robust enough to cope with variability in client demand and keeps operational costs minimal.

In this paper, we examine such NDPs with uncertain demand. In particular, we focus on a multi-commodity NDP, with multiple commodities sharing common arc capacities in the network. The decision maker in this problem seeks to design the arc capacities on a network to meet the demands from his clients who reside in a subset of the nodes in the network. The design of arc capacities can either be binary (the arc either has some fixed capacity, or does not exist in the network) or continuous (the arc capacity can be any non-negative value), and are increased before the realization of demand; the flow on the arcs is decided after the realization of demand.

The total cost of modifying the network and flowing commodities will fluctuate depending on the realized value of demand. Yet, the true distribution of the demand is rarely known; therefore it is important to provide some robustness to the solution of the problem, so that the solution that is finally implemented by the decision maker does not violate any demand satisfaction constraints, regardless of the true distribution of demand. Specifically, the aim is to minimize the network design cost while ensuring solution robustness with respect to ambiguous demand distributions, under either an expectation-based or chance-constrained measure of the flow recourse.

Such a type of robustness that takes into account a set of feasible distributions of demand is known as distributional robustness. In general, distributionally robust stochastic programs (DRSPs) form a “middle ground” between stochastic programs and robust optimization problems: the former assumes full knowledge of the distribution of the uncertainty, which is often unrealistic; the latter only uses extreme events to determine the most conservative solution to a problem, whereas DRSPs seek solutions that “optimize” the worst-case outcome(s) with respect to all possible uncertainty distributions that can be described by a set of historical data samples, but do not require full knowledge of the distribution of the uncertainty.

Delage and Ye (2010) proposed a data-driven framework to solving DRSPs on a set that contains all distributions whose moments “match” the first and the second moments based on a set of data observations. They used Lagrangian dual approaches and reformulated DRSPs with convex constraints as semi-definite programs, or second-order cone programs in special cases, both of which are computationally tractable. Ben-Tal et al. (2013) studied DRSPs with linear constraints including random linear coefficients that follow an unknown distribution. By constructing divergence-function-based confidence sets of the ambiguous probability functions, a related DRSP can be reformulated as a tractable linear program using the conjugate function of some divergence function that is generally convex

In this paper, we will apply the approaches described by Delage and Ye (2010) and Ben-Tal et al. (2013) particularly to variants of the NDPs. As previously described, our formulations contain two stages, referring to as the first stage of planning arc capacities and the second stage of operating flows under uncertain node demands. The corresponding DRSPs seek a capacity design to minimize the maximum flow cost and/or demand losses that may occur for all possible probability distributions of the demand uncertainty restricted in the two types of confidence sets. For NDPs with continuous capacity design and objective functions of minimizing the expected cost, we directly apply the existing DRSP methods. We develop decomposition and cutting-plane algorithms for solving NDPs with 0-1 capacity design, as well as NDPs with chance constraints that bound the worst-case probability of the joint demand loss under ambiguous demand distributions.

In our computational studies, we test both randomized networks and fixed networks with randomized parameters. The random networks will be generated with a large number of nodes and with varying arc densities; the fixed networks will be based on the Sioux Falls road network, which has 24 nodes and 76 arcs. We will benchmark our DRSP approaches and solutions of solving the NDPs against their corresponding stochastic optimization and robust optimization formulation variants, and focus on comparing (i) the computational efficiency and (ii) the sensitivity of solutions to changes in parameters between the three approaches. We aim to demonstrate “the value of data” and insights of cost-and-risk tradeoff in various NDP variants under ambiguous demand.

[1] Delage, E. and Ye, Y. “Distributionally robust optimization under moment uncertainty with application to data-driven problems.” Operations Research, 58(3), 595-612, 2010.

[2] Ben-Tal, A. and Chung, B.D. and Mandala, S.R. and Yao, T. “Robust solutions of optimization problems affected by uncertain probabilities.” Management Science, 59(2), 341-357, 2013.