Least-cost network topology design for a new service

We describe an implementation of the tabu search metaheuristic that effectively finds a low-cost topology for a communications network to provide a centralized new service. Our results are compared to those of a greedy algorithm which applies corresponding decision rules, but without the guidance of the tabu search framework. These problems are difficult computationally, representing integer programs that can involve as many as 10,000 integer variables and 2000 constraints in practical applications. The tabu search results approach succeeded in obtaining significant improvements over the greedy approach, yielding optimal solutions to problems small enough to allow independent verification of optimality status and, more generally, yielding both absolute and percentage cost improvements that did not deteriorate with increasing problem size.This research was partially supported by the Air Force Office of Scientific Research and the Office of Naval Research Contract No. F49629-90-C-0033.     

Hybrid meta-heuristic algorithms for solving network design problem

Network design problem has been, and is, an important problem in transportation. Following an earlier effort in designing a meta-heuristic search technique by an ant system, this paper attempts to hybridize this concept with other meta-heuristic concepts such as genetic algorithm, simulated annealing, and tabu search. Seven hybrids have been devised and tested on the network of Sioux Falls. It has been observed that the hybrids are more effective to solve the network design problem than the base ant system. Application of the hybrid containing all four concepts on a real network of a city with over 2 million population has also proved to be more effective than the base network, in the sense of finding better solutions sooner.     

Tree knapsack approaches for local access network design

In the process of solving many forms of the local access network design problem, the basic model of the tree knapsack problem (TKP) is used as a building block for the search engine of the solution strategy. Various solution strategies can be used to solve this problem. An approach that use standard software coupled with enhanced modelling is presented for the TKP. Enhanced modelling is used to partition the TKP into sub-problems that is easier to solve using standard off the shelve software. The basic approach is described and empirical work is presented. Empirical comparisons are also given relating this approach with some algorithms suggested by other authors.     

Two new bidirectional search algorithms

Computational Optimization and Applications - This paper presents two new bidirectional heuristic search algorithms for solving the shortest path problem on graphs: consistent-heuristic...     

GRASP algorithms for the robust railway network design problem

This paper analyzes the solvability of a railway network design problem and its robust version. These problems are modeled as integer linear programming problems with binary variables, and their solutions provide topological railway networks maximizing the trip coverage in the presence of a competing mode, both assuming that the network works fine and that links can fail, respectively. Since these problems are computationally intractable for realistic sizes, GRASP heuristics are proposed for finding good feasible solutions. The results obtained in a computational experience indicate that our GRASP algorithms are suitable for railway network design problems.     

Numerical comparison of network design algorithms for regionalized variables

The technique of kriging has a fundamental importance in applied sciences such as hydrology, meteorology, soil sciences, and mining. By using kriging, not only can the estimates of the natural phenomena be determined, but the estimation variances reflect the uncertainty of the estimation process. The sampling points for kriging should be selected to minimize the uncertainty, that is, to minimize the estimation variance of the kriging estimator. In this paper four algorithms for optimal observation network design are compared. Two of the algorithms give global optima, while the others give only suboptimal solutions. The computer time required for using the heuristic algorithms, giving only suboptimal solutions, is much less than that of the optimizing procedures. It is also shown on the basis of our experiments that the suboptimal solutions are either optimal or very close to optimal; consequently on the basis of our simulated examples, the heuristic algorithms are highly recommended for practical applications.     

Two algorithms for matroids

A matroid may be characterized by the collection of its bases or by the collection of its circuits. Along with any matroid is a uniquely determined dual matroid. Given the bases of a matroid, it is possible to show that base complements are precisely the bases of the dual. So it is easy to construct bases of the dual given the bases of the original matroid.This paper provides two results. The first enables construction of all circuits of the dual matroid from circuits of the original matroid. The second constructs all bases of a matroid from its circuits.     

Two new variants of nonlinear inexact Uzawa algorithms for saddle-point problems

Summary. In this paper, we consider some nonlinear inexact Uzawa methods for iteratively solving linear saddle-point problems. By means of a new technique, we first give an essential improvement on the convergence results of Bramble-Paschiak-Vassilev for a known nonlinear inexact Uzawa algorithm. Then we propose two new algorithms, which can be viewed as a combination of the known nonlinear inexact Uzawa method with the classical steepest descent method and conjugate gradient method respectively. The two new algorithms converge under very practical conditions and do not require any apriori estimates on the minimal and maximal eigenvalues of the preconditioned systems involved, including the preconditioned Schur complement. Numerical results of the algorithms applied for the Stokes problem and a purely linear system of algebraic equations are presented to show the efficiency of the algorithms. Received December 8, 1999 / Revised version received September 8, 2001 / Published online March 8, 2002 RID="*" ID="*" The work of this author was partially supported by a grant from The Institute of Mathematical Sciences, CUHK RID="**" ID="**" The work of this author was partially supported by Hong Kong RGC Grants CUHK 4292/00P and CUHK 4244/01P     

A new method for topology design of electromagnetic antennas in hyperthermia therapy

The topological derivative concept has been proved to be useful in many relevant applications such as topology optimization, inverse problems, image processing, multi-scale constitutive modeling, fracture mechanics and damage evolution modeling. In this work, we develop a new optimization method based on the topological derivative concept applied to the cancer treatment by hyperthermia. Hyperthermia therapy is a non-invasive medical treatment in which body tissue is artificially heated through electromagnetic waves, focusing the heat in cancerous cells undergoing apoptosis. The basic idea, therefore, consists in finding a distribution of heat source generated by electromagnetic antenna aiming to increase the temperature in the region occupied by the tumor, while keeping the temperature in the remainder part of the body. Numerical results are presented illustrating possible application of the proposed methodology to treatment of cancer by hyperthermia.     

Two algorithms for global optimization

In this paper, we develop and compare two methods for solving the problem of determining the global maximum of a function over a feasible set. The two methods begin with a random sample of points over the feasible set. Both methods then seek to combine these points into “regions of attraction” which represent subsets of the points which will yield the same local maximums when an optimization procedure is applied to points in the subset. The first method for constructing regions of attraction is based on approximating the function by a mixture of normal distributions over the feasible region and the second involves attempts to apply cluster analysis to form regions of attraction. The two methods are then compared on a set of well-known test problems.     

A new Branch and Bound method for a discrete truss topology design problem

Our paper considers a classic problem in the field of Truss Topology Design, the goal of which is to determine the stiffest truss, under a given load, with a bound on the total volume and discrete requirements in the cross-sectional areas of the bars. To solve this problem we propose a new two-stage Branch and Bound algorithm. In the first stage we perform a Branch and Bound algorithm on the nodes of the structure. This is based on the following dichotomy study: either a node is in the final structure or not. In the second stage, a Branch and Bound on the bar areas is conducted. The existence or otherwise of a node in this structure is ensured by adding constraints on the cross-sectional areas of its incident bars. In practice, for reasons of stability, free bars linked at free nodes should be avoided. Therefore, if a node exists in the structure, then there must be at least two incident bars on it, unless it is a supported node. Thus, a new constraint is added, which lower bounds the sum of the cross-sectional areas of bars incident to the node. Otherwise, if a free node does not belong to the final structure, then all the bar area variables corresponding to bars incident to this node may be set to zero. These constraints are added during the first stage and lead to a tight model. We report the computational experiments conducted to test the effectiveness of this two-stage approach, enhanced by the rule to prevent free bars, as compared to a classical Branch and Bound algorithm, where branching is only performed on the bar areas.     

UMTS radio network evaluation and optimization beyond snapshots

A new evaluation scheme for universal mobile telecommunications system (UMTS) radio networks is introduced. The approach takes the complex coupling of coverage and capacity through interference into account. Cell load estimates, otherwise obtained through Monte-Carlo simulation, can now be approximated without time-consuming iterative simulations on user snapshots. The two cornerstones are the generalization of interference coupling matrices from user snapshots to average load and the emulation of load control by an analytical scaling scheme. Building on the new evaluation scheme, two novel radio network optimization algorithms are presented: an efficient local search procedure and a mixed integer program that aims at designing the coupling matrix. Computational experiments for optimizing antenna tilts show that our new approaches outperform traditional snapshot models     

Multicommodity network design with survivability constraints: Some models and algorithms

We survey the main results presented by the author in his PhD thesis, supervised by F. Malucelli, and defended on the 15th March 2003. The thesis is written in English and is available on the Web page http: //www.elet.polimi.it/upload/belotti/thesis.pdf.gz. We investigate three problems, arising in the field of Telecommunication, of networks design with survivability constraints, and solve them through different approaches on a number of real-world network topologies with up to 40 nodes.Received: April 2004MSC classification: 90B10, 90C57     

Two new algorithms for the Min-Power Broadcast problem in static ad hoc networks

In this paper we address the Min-Power Broadcast problem in wireless ad hoc networks. Given a network with an identified source node w, the Min-Power Broadcast (MPB) problem is to assign transmission range to each node such that communication from w to other nodes is possible and the total energy consumption is minimized.

As the problem is NP-Hard we first propose a simulated annealing algorithm for the MPB problem. Utilizing a special node selection mechanism in its neighborhood structure the algorithm is designed in a way enabling an efficient power consumption evaluation and search for neighboring solutions. We then combine the algorithm with a decomposition approach to enhance its performance. This is achieved by decomposing the master problem and performing metropolis chain of the simulated annealing only on the much smaller subproblems resulting from decomposition. Results from a comprehensive computational study indicate the efficiency and effectiveness of the proposed algorithms.     

New algorithms for generalized network flows

This paper, of which a preliminary version appeared in ISTCS'92, is concerned with generalized network flow problems. In a generalized network, each edgee = (u, v) has a positive flow multipliera _e associated with it. The interpretation is that if a flow ofx _e enters the edge at nodeu, then a flow ofa _e x _e exits the edge atv. The uncapacitated generalized transshipment problem (UGT) is defined on a generalized network where demands and supplies (real numbers) are associated with the vertices and costs (real numbers) are associated with the edges. The goal is to find a flow such that the excess or deficit at each vertex equals the desired value of the supply or demand, and the sum over the edges of the product of the cost and the flow is minimized. Adler and Cosares [Operations Research 39 (1991) 955–960] reduced the restricted uncapacitated generalized transshipment problem, where only demand nodes are present, to a system of linear inequalities with two variables per inequality. The algorithms presented by the authors in [SIAM Journal on Computing, to appear result in a faster algorithm for restricted UGT.Generalized circulation is defined on a generalized network with demands at the nodes and capacity constraints on the edges (i.e., upper bounds on the amount of flow). The goal is to find a flow such that the excesses at the nodes are proportional to the demands and maximized. We present a new algorithm that solves the capacitated generalized flow problem by iteratively solving instances of UGT. The algorithm can be used to find an optimal flow or an approximation thereof. When used to find a constant factor approximation, the algorithm is not only more efficient than previous algorithms but also strongly polynomial. It is believed to be the first strongly polynomial approximation algorithm for generalized circulation. The existence of such an approximation algorithm is interesting since it is not known whether the exact problem has a strongly polynomial algorithm.Corresponding author. Research was done while the first author was attending Stanford University and IBM Almaden Research Center. Research partially supported by ONR-N00014-91-C-0026 and by NSF PYI Grant CCR-8858097, matching funds from AT&T and DEC.Research partially supported by ONR-N00014-91-C-0026.