naa a22 4500 510809081 CHVBK 20180411083433.0 cr unu---uuuuu 180411e20131201xx s 000 0 eng 10.1007/s12532-013-0058-3 doi (NATIONALLICENCE)springer-10.1007/s12532-013-0058-3 Branch-and-cut approaches for chance-constrained formulations of reliable network design problems [Elektronische Daten] [Yongjia Song, James Luedtke] We study solution approaches for the design of reliably connected networks. Specifically, given a network with arcs that may fail at random, the goal is to select a minimum cost subset of arcs such the probability that a connectivity requirement is satisfied is at least $$1 - \epsilon $$ 1 - ϵ , where $$\epsilon $$ ϵ is a risk tolerance. We consider two types of connectivity requirements. We first study the problem of requiring an $$s$$ s - $$t$$ t path to exist with high probability in a directed graph. Then we consider undirected graphs, where we require the graph to be fully connected with high probability. We model each problem as a stochastic integer program with a joint chance constraint, and present two formulations that can be solved by a branch-and-cut algorithm. The first formulation uses binary variables to represent whether or not the connectivity requirement is satisfied in each scenario of arc failures and is based on inequalities derived from graph cuts in individual scenarios. We derive additional valid inequalities for this formulation and study their facet-inducing properties. The second formulation is based on probabilistic graph cuts, an extension of graph cuts to graphs with random arc failures. Inequalities corresponding to probabilistic graph cuts are sufficient to define the set of feasible solutions and violated inequalities in this class can be found efficiently at integer solutions, allowing this formulation to be solved by a branch-and-cut algorithm. Computational results demonstrate that the approaches can effectively solve instances on large graphs with many failure scenarios. In addition, we demonstrate that, by varying the risk tolerance, our model yields a rich set of solutions on the efficient frontier of cost and reliability. Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society, 2013 Reliable network design nationallicence Chance constraints nationallicence Integer programming nationallicence Song Yongjia Department of Industrial and Systems Engineering, University of Wisconsin-Madison, 53706, Madison, WI, USA aut Luedtke James Department of Industrial and Systems Engineering, University of Wisconsin-Madison, 53706, Madison, WI, USA aut Mathematical Programming Computation Springer Berlin Heidelberg 5/4(2013-12-01), 397-432 1867-2949 5:4<397 2013 5 12532 https://doi.org/10.1007/s12532-013-0058-3 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s12532-013-0058-3 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Song Yongjia Department of Industrial and Systems Engineering, University of Wisconsin-Madison, 53706, Madison, WI, USA aut NATIONALLICENCE 700 1- Luedtke James Department of Industrial and Systems Engineering, University of Wisconsin-Madison, 53706, Madison, WI, USA aut NATIONALLICENCE 773 0- Mathematical Programming Computation Springer Berlin Heidelberg 5/4(2013-12-01), 397-432 1867-2949 5:4<397 2013 5 12532 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer