Lagrangean Based Methods for Solving Large-Scale Cellular Network Design Problems

The cellular network design (CND) problem is formulated as a comprehensive linear mixed integer programming model integrating the base station location (BSL) problem, the frequency channel assignment (FCA) problem and the topological network design (TND) problem. A solution algorithm based on Lagrangean relaxation is proposed for solving this complex cellular network design problem. Pursuing the optimum solution through exact algorithms to this problem appears to be unrealistic considering the large scale nature and NP-hardness of the problem. Therefore, the solution algorithm strategy consists in computing effective lower and upper bounds for the problem. Lower bounds are evaluated through a Lagrangean relaxation technique and subgradient method. A Lagrangean heuristic is developed to compute upper bounds based on the Lagrangean solution. The bounds are improved through a customized branch and bound algorithm which takes in account specific knowledge of the problem to improve its efficiency. Thirty two random test instances are solved using the proposed algorithm and the CPLEX optimization package. The results show that the duality gap is excessive, so it cannot guarantee the quality of the solution. However, the proposed algorithm provides optimal or near optimal solutions for the problem instances for which CPLEX also provides the optimal solution. It further suggests that the proposed algorithm provides optimal or near optimal solutions for the other instances too. Finally, the results demonstrate that the proposed algorithm is superior to CPLEX as a solution approach for the CND problem.     

A system for routing and capacity assignment in computercommunication networks

The combined problem of selecting a primary route for each communicating pair and a capacity value for each link in computer communication networks is considered. The network topology and traffic characteristics are given: a set of candidate routes and of candidate capacities for each link are also available. The goal is to obtain the least costly feasible design where the costs include both capacity and queuing components. Lagrangean relaxation and subgradient optimization techniques were used to obtain verifiable solutions to the problem. The method was tested on several topologies, and in all cases good feasible solutions, as well as tight lower bounds, were obtained. The model can be generalized to deal with different classes of customers, characterized by different priorities, message lengths, and/or delay requirements     

A Lagrangean relaxation and subgradient framework for the routing and wavelength assignment problem in WDM networks

Unlike traditional heuristics, we provide in this paper an optimization framework for the routing and wavelength assignment (RWA) problems with the objective of minimizing the rejection penalty of the connection demands in an all-optical wavelength-division-multiplexing (WDM) network. Our new link-based formulation takes the fairness issue and the limited wavelength conversion into consideration. The framework employs a decomposition approach to decide on the rejection/selection of the route and wavelength assignment for a semilightpath, by appropriately relaxing some of the constraints in the Lagrangean relaxation (LR) method. At the higher level, we update Lagrange multipliers iteratively with the subgradient method. At the lower level, we propose the modified minimum cost semilightpath (MMCSLP) algorithm to solve all the subproblems. A heuristic algorithm is also proposed to generate a feasible RWA scheme based on the solution to the dual problem. When compared with some latest methodology in the literature, we demonstrate that our framework can achieve better performance in terms of the computation time and the number of connection demands rejected. The much shorter computation time is due to the polynomial time complexity of our framework. In addition to achieving a very good (near-optimal) solution, the influence from the change of the number of converters is studied. Finally, we demonstrate that our framework produces fairer routing decisions by adjusting some design parameters in our framework.     

Routing in a network with unreliable components

A new approach to the joint selection of primary and secondary routes in a network with unreliable components is presented. The mathematical model captures the changes in the operational characteristics of the network as it adapts to failures. Lagrangian relaxation and subgradient optimization techniques are used to obtain good heuristic solutions to the problem, as well as lower bounds to be used as benchmarks against which the quality of the solution is assessed. Results of numerical experiments are reported, and directions for further enhancements of the model are discussed     

A Lagrangean relaxation approach for QoS networks CFA problems

This paper is about design methodologies for packet networks, under the constraints of end-to-end quality of service (QoS) metrics. The network modeling also considers the dynamics of today's packet networks. We are particularly considering the problem of capacity and flow assignment where the routing assignments and capacities are considered to be decision variables. An efficient Lagrangean relaxation-based heuristic procedure is developed to find bounds and solutions for a corporate virtual private network (VPN), where the traffic is mostly based on TCP connections. Numerical results for a variety of problem instances are reported.     

Distributed resource allocation with fairness for cognitive radios in wireless mobile ad hoc networks

Both spectrum sensing and power allocation have crucial effects on the performance of wireless cognitive ad hoc networks. In order to obtain the optimal available subcarrier sets and transmission powers, we propose in this paper a distributed resource allocation framework for cognitive ad hoc networks using the orthogonal frequency division multiple access (OFDMA) modulation. This framework integrates together the constraints of quality of service (QoS), maximum powers, and minimum rates. The fairness of resource allocation is guaranteed by introducing into the link capacity expression the probability that a subcarrier is occupied. An incremental subgradient approach is applied to solve the optimization problems that maximize the weighted sum capacities of all links without or with fairness constraints. Distributed subcarrier selection and power allocation algorithms are presented explicitly. Simulations confirm that the approach converges to the optimal solution faster than the ordinary subgradient method and demonstrate the effects of the key parameters on the system performance. It has been observed that the algorithms proposed in our paper outperform the existing ones in terms of the throughput and number of secondary links admitted and the fairness of resource allocation.     

A Lagrangean relaxation-based approach for routing and wavelength assignment in multigranularity optical WDM networks

Optical wavelength-division multiplexed (WDM) networks often include optical cross-connects with multigranularity switching capability, such as switching on a single lambda, a waveband, or an entire fiber basis. In addition, it has been shown that routing and wavelength assignment (RWA) in an arbitrary mesh WDM network is an NP-complete problem. In this paper, we propose an efficient approximation approach, called Lagrangean relaxation with heuristics (LRH), aimed to resolve RWA in multigranularity WDM networks particularly with lambda and fiber switches. The task is first formulated as a combinatorial optimization problem in which the bottleneck link utilization is to be minimized. The LRH approach performs constraint relaxation and derives a lower-bound solution index according to a set of Lagrangean multipliers generated through subgradient-based iterations. In parallel, using the generated Lagrangean multipliers, the LRH approach employs a new heuristic algorithm to arrive at a near-optimal upper-bound solution. With lower and upper bounds, we conduct a performance study on LRH with respect to accuracy and convergence speed under different parameter settings. We further draw comparisons between LRH and an existing practical approach via experiments over randomly generated and several well-known large sized networks. Numerical results demonstrate that LRH outperforms the existing approach in both accuracy and computational time complexity, particularly for larger sized networks.     

Bounds from noisy linear measurements

An estimation problem in which a finite number of linear measurements of an unknown function is available, and in which the only prior information available concerning the unknown function consists of inequality constraints on its magnitude, is ill-posed in that insufficient information is available from which point estimates of the unknown function can be made with any reliability, even with exact measurements. An alternative to point estimation involves the computation of bounds on linear functionals of the unknown function in terms of the measurements. A generalization is described of the bounding technique to problems in which the measurements are inexact. The bounds are defined in terms of a primal optimization problem. A deterministic interpretation of the bounds is given, as well as a probabilistic one for the case of additive Gaussian measurement noise. An unconstrained dual optimization problem is derived that has an interesting data-adaptive filtering interpretation and provides an attractive basis for computation. Several aspects of the primal and dual optimization problems are investigated that have important implications for the reliable computation of the bounds.     

A Lagrangian-Relaxation Based Network Profit Optimization For Mesh SONET-Over-WDM Networks

In Wavelength Division Multiplexing (WDM) networks, the huge capacity of wavelength channels is generally much larger than the bandwidth requirement of individual traffic streams from network users. Traffic grooming techniques aggregate low-bandwidth traffic streams onto high-bandwidth wavelength channels. In this paper, we study the optimization problem of grooming the static traffic in mesh Synchronous Optical Network (SONET) over WDM networks. The problem is formulated as a constrained integer linear programming problem and an innovative optimization objective is developed as network profit optimization. The routing cost in the SONET and WDM layers as well as the revenue generated by accepting SONET traffic demands are modelled. Through the optimization process, SONET traffic demands will be selectively accepted based on the profit (i.e., the excess of revenue over network cost) they generate. Consiering the complexity of the network optimization problem, a decomposition approach using Lagrangian relaxation is proposed. The overall relaxed dual problem is decomposed into routing and wavelength assignment and SONET traffic routing sub-problems. The subgradient approach is used to optimize the derived dual function by updating the Lagrange multipliers. To generate a feasible network routing scheme, a heuristic algorithm is proposed based on the dual solution. A systematic approach to obtain theoretical performance bounds is presented for an arbitrary topology mesh network. This is the first time that such theoretical performance bounds are obtained for SONET traffic grooming in mesh topology networks. The optimization results of sample networks indicate that the roposed algorithm achieves good sub-optimal solutions. Finally, the influence of various network parameters is studied.     

Designing multi-hour hierarchical communications networks with fixed charge and piecewise linear costs

An algorithm is presented for the problem of sizing link capacities in an alternate routing telecommunications network with time-varying demands. Several algorithms have been developed since 1977 for this problem, where costs are linear and the existing network is ignored. We consider the case of per-trunk (communications channel) costs for adding and disconnecting trunks from an existing network, and fixed costs for the first trunk added or disconnected on each link. A branch and bound procedure is developed to solve the problem. Lower bounds in the search tree are obtained through the use of Lagrangian relaxation and subgradient optimization. Several tests are employed to detect infeasibility of subproblems generated in the tree search. Computational results are presented, including comparisons of results using different tolerances for pruning the search tree.     

A Lagrangean relaxation based near-optimal algorithm for advance lightpath reservation in WDM networks

Advance lightpath reservation is a new research topic for connecting high-speed computer servers in lambda grid applications and for dynamic lightpath provisioning in the future optical internet. In such networks, users make call requests in advance to reserve network resources for communications. The challenge of the problem comes from how to jointly determine call admission control, lightpath routing, and wavelength assignment. In this paper, we propose an efficient Lagrangean relaxation (LGR) approach to resolve advance lightpath reservation for multi-wavelength optical networks. The task is first formulated as a combinatorial optimization problem in which the revenue from accepting call requests is to be maximized. The LGR approach performs constraint relaxation and derives an upper-bound solution index according to a set of Lagrangean multipliers generated through subgradient-based iterations. In parallel, using the generated Lagrangean multipliers, the LGR approach employs a new heuristic algorithm to arrive at a near-optimal solution. By upper bounds, we assess the performance of LGR with respect to solution accuracy. We further draw comparisons between LGR and three heuristic algorithms—Greedy, First Come First Serve, and Deadline First, via experiments over the widely-used NSFNET network. Numerical results demonstrate that LGR outperforms the other three heuristic approaches in gaining more revenue by receiving more call requests.     

Branch-and-bound redundancy optimization for a series system withmultiple-choice constraints

This paper considers a redundancy optimization problem in which multiple-choice and resource constraints are incorporated. The problem is expressed as a nonlinear integer programming problem and is characterized as an NP-hard problem. The purpose of the paper is to develop a SSRP (solution space reduction procedure). Therefore, the problem is analyzed first to characterize some solution properties. An iterative SSRP is then derived using those solution properties. Finally, the iterative SSRP is used to define an efficient B&BP (branch-and-bound procedure) algorithm. Experimental tests show how dramatically the SSRP can work on removing any intermediately-found unnecessary decision variables from further consideration in solution search, and how efficient this B&BP is     

Multiterminal net routing for partial crossbar-based multi-FPGA systems

Multi-FPGA (field-programmable gate arrays) systems are used as custom computing machines to solve compute-intensive problems and also in the verification and prototyping of large circuits. In this paper, we address the problem of routing multiterminal nets in a multi-FPGA system that uses partial crossbars as interconnect structures. First, we model the multiterminal routing problem as a partitioned bin-packing problem and formulate it as an integer linear programming problem where the number of variables is exponential. A fast heuristic is applied to compute an upper bound on the routing solution. Then, a column generation technique is used to solve the linear relaxation of the initial master problem in order to obtain a lower bound on the routing solution. This is followed by an iterative branch-and-price procedure that attempts to find a routing solution somewhere between the two established bounds. In this regard, the proposed algorithm guarantees an exact-routing solution by searching a branch-and-price tree. Due to the tightness of the bounds, the branch-and-price tree is small resulting in shorter execution times. Experimental results are provided for different netlists and board configurations in order to demonstrate the algorithms performance. The obtained results show that the algorithm finds an exact routing solution in a very short time.     

Design of robust envelope-constrained filter with orthonormal bases

In the continuous-time envelope-constrained (EC) filtering problem using an orthonormal filter structure, the aim is to synthesize an orthonormal filter such that the noise enhancement is minimized while the noiseless output response of the filter with respect to a specified input signal stays within the upper and lower bounds of the envelope. The noiseless output response of the optimum filter to the prescribed input signal touches the output boundaries at some points. Consequently, any disturbance in the prescribed input signal or error in the implementation of the optimal filter will result in the output constraints being violated. In this paper, we review a semi-infinite envelope-constrained filtering problem in which the constraint robustness margin of the filter is maximized, subject to a specified allowable increase in the optimal noisy power gain. Using a smoothing technique, it is shown that the solution of the optimization problem can be obtained by solving a sequence of strictly convex optimization problems with integral cost. An efficient optimization algorithm is developed based on a combination of the golden section search method and the quasi-Newton method     

Capacity reservation optimization for distributed satellite cluster networks

We investigate the problem of link capacity reservation in distributed satellite cluster networks. In the optimization problem, the objective is to minimize the link reservation cost under the link capacity constraints. The original optimization problem can be formulated as a set of the linear programs. For the small‐scale networks, the general linear program solvers have the capability to solve the problem within an acceptable time. To solve the problem in the large‐scale network, we propose a heuristic method on the basis of the alternating direction method of multipliers, in which the original problem is decoupled to parallel small problems that can be solved simply. In the heuristic, the upper and lower bounds are computed iteratively. When the upper and lower bounds are close enough, then the optimal value can be obtained approximately. The simulation results show that the proposed method is comparatively exact when the stopping criterion is properly chosen.     

The dual parameterization approach to optimal least square FIRfilter design subject to maximum error constraints

This paper is concerned with the design of linear-phase finite impulse response (FIR) digital filters for which the weighted least square error is minimized, subject to maximum error constraints. The design problem is formulated as a semi-infinite quadratic optimization problem. Using a newly developed dual parameterization method in conjunction with the Caratheodory's dimensional theorem, an equivalent dual finite dimensional optimization problem is obtained. The connection between the primal and the dual problems is established. A computational procedure is devised for solving the dual finite dimensional optimization problem. The optimal solution to the primal problem can then be readily obtained from the dual optimal solution. For illustration, examples are solved using the proposed computational procedure     

Capacity Planning of DiffServ Networks with Best-Effort and Expedited Forwarding Traffic

For networks providing a specific level of service guarantees, capacity planning is an imperative part of network management. Accurate dimensioning is especially important in DiffServ networks, where no per-flow signaling or control exists. In this paper, we address the problem of capacity planning for DiffServ networks with only Expedited Forwarding (EF) and best effort (BE) traffic classes. The problem is formulated as an optimization problem, where the total link cost is minimized, subject to the performance constraints of both EF and BE classes. The edge to edge EF demand pairs and the BE demands on each link are given. The variables to be determined are the non-bifurcated routing of EF traffic, and the discrete link capacities. We show that Lagrangian relaxation and subgradient optimization methods can be used to effectively solve the problem. Computational results show that the solution quality is verifiably good while the running time remains reasonable on practical-sized networks. This represents the first work for capacity planning of multi-class IP networks with non-linear performance constraints and discrete link capacity constraints.     

On the Gaussian MIMO Relay Channel With Full Channel State Information

This paper addresses the problem of source and relay transmit covariance optimization on the Gaussian MIMO relay channel with full channel state information (CSI), i.e., assuming perfect knowledge of all channels. For full-duplex relaying, we show that the cut-set bound on capacity can be computed as the solution of a convex problem, thus providing a tighter bound than previously published. For time division duplex (TDD) relaying, both upper and lower bounds on capacity are derived, and the transmit covariance matrices are optimized for decode-and-forward (DF) strategies with either partial or full decoding at the relay. A generic procedure is introduced to formulate these problems into a standard convex form, and to solve them efficiently. Suboptimum precoders are also proposed which have a specific matrix structure that either leads to a closed-form expression or at least reduces the dimension of the optimization problem. Practical aspects related to transmit power constraints and CSI availability are then discussed. Finally, simulations in a cellular downlink scenario show that the partial DF strategy can achieve a rate very close to capacity for realistic values of the source to relay SNR, and that the rate loss due to suboptimum precoder structures remains small for typical antenna configurations.      

Some approaches to solving a multihour broadband network capacity design problem with single-path routing

In this paper, we consider solution approaches to a multihour combined capacity design and routing problem which arises in the design of dynamically reconfigurable broadband communication networks that uses the virtual path concept. We present a comparative evaluation of four approaches, namely: a genetic algorithm, a Lagrangian relaxation based subgradient optimization method, a generalized proximal point algorithm with subgradient optimization, and, finally, a hybrid approach where the subgradient based method is combined with a genetic algorithm. Our computational experience on a set of test problems of varying network sizes services) shows that the hybrid approach often is the desirable choice in obtaining the minimum cost network while the genetic algorithm based approach has the most difficulty in solving large scale problems. This revised version was published online in June 2006 with corrections to the Cover Date.     

Hybrid Wireless-Optical Broadband Access Network (WOBAN): Network Planning Using Lagrangean Relaxation

The concept of a hybrid wireless-optical broadband access network (WOBAN) is a very attractive one. This is because it may be costly in several situations to run fiber to every home (or equivalent end-user premises) from the telecom central office (CO); also, providing wireless access from the CO to every end user may not be possible because of limited spectrum. Thus, running fiber as far as possible from the CO toward the end user and then having wireless access technologies take over may be an excellent compromise. How far should fiber penetrate before wireless takes over is an interesting engineering design and optimization problem, which we address in this paper. We propose and investigate the characteristics of an analytical model for network planning, namely optimum placements of base stations (BSs) and optical network units (ONUs) in a WOBAN (called the primal model, or PM). We develop several constraints to be satisfied: BS and ONU installation constraints, user assignment constraints, channel assignment constraints, capacity constraints, and signal-quality and interference constraints. To solve this PM with reasonable accuracy, we use “Lagrangean relaxation” to obtain the corresponding “Lagrangean dual” model. We solve this dual problem to obtain a lower bound (LB) of the primal problem. We also develop an algorithm (called the primal algorithm) to solve the PM to obtain an upper bound (UB). Via simulation, we compare this PM to a placement heuristic (called the cellular heuristic) and verify that the placement problem is quite sensitive to a set of chosen metrics.