摘要:

AbstractWe consider the problem of routing multiple commodities between various origin—destination pairs in a network, at minimum total cost. Economies of scale in arc flow costs are modeled using piecewise linear, concave total‐cost functions for each arc. This model applies to a variety of medium‐ and long‐term planning contexts including transportation planning, design of communication networks, plant location and capacity expansion planning, production planning, and water resource management. We formulate the general problem as a mixed‐integer program and develop a composite algorithm to generate both good lower bounds and heuristic solutions. We also report on computational results for several randomly generated general networks (with up to 40 nodes, 359 arcs, and 60 commodities) and layered neetworks (with up to 60 nodes, 372 arcs, and 60 commodities). These tests demonstrate that even for relatively large problems, the composite algorithm is very effective in generating solutions with small gaps between the upper and lower bounds (1.7% on average for general networks, and 0.4% on average for layered networks); for 19 out of the 25 layered network problems, the method generated and verified the optimal

ISSN:0028-3045    

DOI:10.1002/net.3230190202

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1989

数据来源: WILEY

摘要:

AbstractLetR(Gk) denote the probability that a subset of verticesKin the undirected graphG= (V, E) can communicate when the edge ofGfail independently with known probabilities. Suppose thatGkcontains as separting pair of vertices {u,v} such thatGk=G̃k̃∪ Ǧǩ, Ṽ ∩ V̂ ={u v}, Ẽ ∩ Ê = ø, |Ẽ| ⩾ 2, and |Ê| ⩾2. It is shown that Ĝkmay be replaced by a chain χ of at most three edges betweenuandvsuch thatR(Gk) = ΩR ((G̃ ∪ χ)k̃′) where Ω is a derived constant and K̃′ is defined by the procedure. The failure probabilities of the edges in χ and the value of Ω are shown to be computable by evaluating the reliability of one of four variants of Ĝk̂. Minimal components Ĝk̂can be efficiently found using triconnected decomposition and the above procedure embedded within a recursive factoring algorithm for computingK‐terminal reliability. Conditions are derived which guarantee the new algorithm is at least as good as a pure factoring algorithm, and an example shows that

ISSN:0028-3045    

DOI:10.1002/net.3230190203

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1989

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230190204

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1989

数据来源: WILEY

摘要:

AbstractWe study here the problem of reorienting the directed edges of mixed multigraphs so as to establish or preserve reachability, which may be destroyed by edge removal. We develop a linear time/space algorithm which tests whether reorienting designated directed edges can reestablish reachability, and which constructs such a reorientation whenever possible. We also develop a linear time/space algorithm which, when reachability has been destroyed by the removal of a single edge, optimally restores reachability through the reversal of selected edges. Finally, we show the reliability of a graph allowing reversals to be twice that of a graph for which reversals are not permitted.

ISSN:0028-3045    

DOI:10.1002/net.3230190205

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1989

数据来源: WILEY

摘要:

AbstractWe give a new bound on the number of maximal cliques in a graph, along with a bound on the length of odd antiholes that the graph can contain. Based on these bounds we then identify a family of graphs with polynomially solvable maximum weight clique problem, using the edgebicoloring approach developed in a recent paper by Balas, Chvatal, and Nesetril.

ISSN:0028-3045    

DOI:10.1002/net.3230190206

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1989

数据来源: WILEY

摘要:

AbstractWe prove that any continuous mapping from a network into itself has a fixed point if and only if the network is a tree‐networ

ISSN:0028-3045    

DOI:10.1002/net.3230190207

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1989

数据来源: WILEY

摘要:

AbstractGiven a graph in which every arc (i, j) has two numbers ρijand Cijassociated with it representing the reliability and capacity, respectively, a dynamic programming formulation is derived for finding the path from any nodeito terminal nodeNwith the largest expected capacity. It is shown that the functional equation obtained may not necessarily be governed by the principle of optimality

ISSN:0028-3045    

DOI:10.1002/net.3230190208

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1989

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230190209

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1989

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230190210

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1989

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230190211

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1989

数据来源: WILEY