Institute for Systems Research Technical Reports

In this report, we first introduce belief networks in the light of knowledge representation under uncertainty, then in the remainingsections we give the descriptions of the semantics, inference mechanisms and some issues related to learning belief networks, respectively. This report is not intended to be a tutorial for beginners. Rather it aims to point out some important aspects of belief networks and summarize some important algorithms.

Since each cable has an associated capacity (bandwidth), enough capacity must be installed on the links of the network to satisfy the demand, using possibly different types of cables. Starting with a network with no capacity or some capacity already installed, a tabu search heuristic is designed to find a solution that minimizes the cost of installing any additional capacity on the network. This tabu search applies a k-shortest path algorithm to find alternative paths from the gateway to the demand vertices. Numerical results are presented on different types of networks with up to 200vertices and 100 demand vertices.

We(i) present a new directed formulation for the unitary NDC problemthat is stronger than a natural undirected formulation,(ii) project out several classes of valid inequalities---partitioninequalities, odd-hole inequalities, and combinatorial designinequalities---that generalize known classes of valid inequalitiesfor the Steiner tree problem to the unitary NDC problem, and(iii) show how to strengthen and direct nonunitary problems.

Our results provide a unifying framework forstrengthening formulations for NDC problems, and demonstratethe strength and power of flow-based formulations fornetwork design problems with connectivity requirements.

In this dissertation we propose a new model and associated algorithms to solve a VC-rerouting problem in real time. This model takes advantage of the distributed network data and computational resources by decomposing the problem at an early stage and then performing the computations in a decentralized mode.

In order to solve the fault tolerant VP layout problem, we formulate a bi-criteria optimization model reflecting the tradeoff between throughput and certain QOS requirements. The model involves a piece-wise linear approximation to the capacity allocation rule for variable bit rate connections statistically multiplexed over a VP.

Both models are formulated as integer programs. The solution method developed employ relaxation and aggregation of variables, feasible solution heuristics and valid inequalities. The results of the computational experiments presented indicate that the methods developed are efficient and produce accurate solutions.