摘要:

AbstractIn this paper we examine an integer programming formulation of the resource constrained shortest path problem. This is the problem of a traveller with a budget of various resources who has to reach a given destination as quickly as possible within the resource constraints imposed by his budget. A lagrangean relaxation of the integer programming formulation of the problem into a minimum cost network flow problem (which in certain circumstances reduces to an unconstrained shortest path problem) is developed which provides a lower bound for use in a tree search procedure. Problem reduction tests based on both the original problem and this lagrangean relaxation are given. Computational results are presented for the solution of problems involving up to 500 vertices, 5000 arcs, and 10 resources.

ISSN:0028-3045    

DOI:10.1002/net.3230190402

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

年代:1989

数据来源: WILEY

摘要:

AbstractGiven a network having costs and upper bound constraints on the flows in its arcs, the minimum‐cost network flow problem is that of finding flows which satisfy a flow‐conservation constraint at each node and minimize the total cost of the flow. If the arc capacities vary as functions of time, and storage is permitted at the nodes of the network, then the problem becomes an infinitedimensional linear program with a network structure. We describe an algorithm to solve such problems. This algorithm is a continuuous‐time version of the network simplex algo

ISSN:0028-3045    

DOI:10.1002/net.3230190403

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

年代:1989

数据来源: WILEY

摘要:

AbstractIn satellite communications networks, distinctive facilities called homing stations perform special transmission functions. Local demand nodes clustered around each homing station communicate with each other via a local switch at the homing station; demand nodes in different cluster communicate with each other via satellite earth stations at the homing stations. Designing such a communication network requires choices on the locations of the earth stations and on the assignments of demand nodes to the local clusters at the earth stations. We formulate this problem as a zero‐one quadratic facility location problem and transform it into an equivalent zero‐one integer linear program. Computational experience on real data shows that a branch and bound procedure is effective in solving problems with up to 40 demand nodes (major cities) and that the solutions that this algorithm finds improve considerably upon management generated solutions. We also show that a greedy add heuristic, as implemented on an IBM PC, consistently generates optimal or near‐optimal solu

ISSN:0028-3045    

DOI:10.1002/net.3230190404

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

年代:1989

数据来源: WILEY

摘要:

AbstractThemean distance, μ(G), of a graphGis the arithmetic mean of the distances inG. Upper and lower bounds for the mean distance of a self‐complementary graph of given order are obtained and the extremal grpahs are determined. It is shown that ift≥ 2 is rational, then there exist (1) graphs with arbitrarily low or high edge density, (2) bipartite graphs and (3) oriented graphs with mean distance equal tot, and also (4) trees and (5) tournaments with mean distance arbitrarily close tot. A number of open problems are menti

ISSN:0028-3045    

DOI:10.1002/net.3230190405

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

年代:1989

数据来源: WILEY

摘要:

AbstractWe describe a new algorithm for minimum cost perfect matching problems in arbitrary (nonbipartite) graphs based on an active constraint set strategy on the whole set of constraints defining the matching polytope (the so‐called Edmonds' constraints or blossom inequalities). At each step, the resulting subproblem reduces to a minium cost network flow problem which may be solved either via classical network flow algorithms, or via primal network flow algorithms. Finite convergence of the algorithm is proved under a nondegeneracy assumption and an anticycling procedure is defined for ensuring finite termination in degenerate cases. Computer experiments using a primal code for the network flow subproblems show that this approach appears to be competitive even with respect to the most efficient general matching codes currently described in the literatur

ISSN:0028-3045    

DOI:10.1002/net.3230190406

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

年代:1989

数据来源: WILEY

摘要:

AbstractThe problem fo estimating branch flows and total network flow in a directed acyclic network is important in diverse applications, such as: (1) in the measurement of rainfall and water run off and (2) in cash control as cash receipts move through an accounting system. In this paper, a variety of network flow estimation problems are examined, where the measurement errors of the observed branch flows may be correlated. Procedures are presented which produce branch flow estimates that conserve flow when observations of flow are available on all network branches and which produce total network flow estimates when observations of flow are available on only a subset of network branches. The latter procedure uses observed flows through proper cut sets. Also included is a discussion of a tractable method of computing biased total network flow estimates. These biased estimates have the potential advantage of having a relatively small variance. All of the estimation procedures presented derive estimates from the solution of appropriately formaulated mathematical programs whose objective function is a quadratic form. An example is included to illustrate the ease of use of the proposed estimation procedures.

ISSN:0028-3045    

DOI:10.1002/net.3230190407

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

年代:1989

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230190408

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

年代:1989

数据来源: WILEY