ABSTRACT Given a directed graph, the Capacitated Steiner Arborescence Problem (CSAP) aims to determine the least‐cost connection from the root node to terminal nodes requiring a demand through Steiner nodes coming with a capacity, such that there is a unique path from the root to each terminal. This paper presents a new extended formulation of the CSAP, which extends the classical multicommodity flow formulation of CSAP by introducing the notion of cardinality of terminals served by arcs. We show that our extended formulation is stronger than the classical one. We present two classes of inequalities and separation heuristics exploiting the cardinality effect of the extended formulation. The first class is a generalization of cardinality induced Cover and (1, k )‐Configuration inequalities. The second class is called the p‐ Arc Cardinality matching inequalities and is based on matching the number of commodities flowing on active arcs across a cut‐set to its composite cardinality. The computational study clearly demonstrates the superiority of the extended formulation over the classical one. In particular, it consistently provides significantly tighter lower bounds at the root node. Moreover, for all hard instances, solving CSAP to optimality requires a number of branch‐and‐bound nodes that is several orders of magnitude larger under the classical formulation than under the extended one.

Through recent technical advances, multiple resources can be connected to provide a computing grid for processing computationally intensive applications. We build on an approach, termed sequential grid computing, that takes advantage of idle processing power by routing jobs that require lengthy processing through a sequence of processors. We present two models that solve the static and dynamic versions of the sequential grid scheduling problem for a single job. In the static and dynamic versions, the model maximizes a reward function tied to the probability of completion within service-level agreement parameters. In the dynamic version, the static model is modified to accommodate real-time deviations from the plan. We then extend the static model to accommodate multiple jobs. Extensive computational experiments highlight situations (a) where the models provide improvements over scheduling the job on a single processor and (b) where certain factors affect the quality of solutions obtained.

In this paper, a model and a solution procedure is developed for the File Allocation and Join Site Selection Problem with 2-way Join [FAJSP-2], defined on a telecommunications network. This problem attempts to integrate the file allocation and query optimization aspects of a distributed computing system. By allowing for queries that require processing up to two file types, this problem is designed to determine simultaneously the number and location of file types and the location of join operations. This problem is modeled as a mixed-integer linear program, for which a fast dual-ascent approximation procedure is developed. Extensive computational results are presented which demonstrate that our dual-ascent procedure is able to solve even large-scale problems to near optimality quickly. © 1999 John Wiley & Sons, Inc. Networks 33: 109–124, 1999

Topological design of communication networks has been well examined in the literature. However, most of these studies focus on nonhierarchical networks where all nodes are considered equivalent from a routing perspective. It is well recognized, however, that hierarchical topologies offer several advantages for remote office internetworking. In this article, we provide a mixed integer programming formulation for designing hierarchical topologies. We also provide an interesting solution strategy that incorporates valid inequalities within a dual ascent framework to obtain tight lower bounds and feasible solutions to the problem. Computational experiments with a Fortran implementation of the procedure are also reported.

Presents a technique to construct efficient belief network structures for application areas where large amounts of data are available and information on the ordering of the variables can be obtained from domain experts. We identify classes of networks that are efficient for propagating beliefs. We formulate the problem as one of determining the belief network representation from a given class that best represents the data. We use the I-Divergence measure which is known to have certain desirable properties for evaluating different approximations. We present some theoretical findings that characterize the nature of solutions that are obtained. These theoretical results lead to an efficient solution procedure for finding the best network representation. We also discuss other information that may be reasonably obtained from experts, and show how such information leads to improving the efficiency of the technique to find the best network structure.