Cooperation has become an essential element in spectrum sharing between the primary and secondary networks. A new trend in cooperation is to allow the primary and secondary networks to cooperate on the node level for data forwarding. This new paradigm allows to pool network resources from both the primary and secondary networks and allows users in each network to access a much richer network infrastructure in a combined network. This paper offers an in-depth study of such node-level cooperation by explaining its optimal throughput curve—the maximum achievable throughput for both the primary and secondary users. We formulate the problem as a multicriteria optimization problem with the goal of maximizing the throughput of both the primary and secondary users. Through a novel approach based on weighted Chebyshev norm, we transform the multicriteria optimization problem into a single criteria optimization problem and find a sequence of Pareto-optimal points iteratively. Based on the Pareto-optimal points, we construct the throughput curve and show that it provides an $\varepsilon $ -approximation to the optimal curve. We prove some important properties of the optimal throughput curve. Through a case study, we show that the throughput region (the area under the throughput curve) under node-level cooperation is substantially larger than that when there is no node-level cooperation.

Recently, a new MIMO degree-of-freedom (DoF) model was proposed to allocate DoF resources for spatial multiplexing (SM) and interference cancellation (IC) in a multi-hop network. Although this DoF model promises many benefits, it hinges upon a global node ordering to keep track of IC responsibilities among all the nodes. An open question about this model is whether its global ordering property can be achieved among the nodes in the network through distributed operations. In this paper, we explore this question by studying DoF scheduling in a multi-hop MIMO network, with the objective of maximizing the minimum throughput among a set of sessions. We propose an efficient DoF scheduling algorithm to solve it and show that our algorithm only requires local operations. We prove that the resulting DoF scheduling solution is globally feasible and show that there exists a corresponding feasible global node ordering for IC, albeit such global ordering is implicit. Simulation results show that the solution values obtained by our algorithm are relatively close to the upper bound values computed by CPLEX solver, thereby indicating that our algorithm is highly competitive.

Distributed joint congestion control and routing optimization has received a significant amount of attention recently. To date, however, most of the existing schemes follow a key idea called the back-pressure algorithm. Despite having many salient features, the first-order subgradient nature of the back-pressure based schemes results in slow convergence and poor delay performance. To overcome these limitations, in this paper, we make a first attempt at developing a second-order joint congestion control and routing optimization framework that offers utility-optimality, queue-stability, fast convergence, and low delay. Our contributions in this paper are three-fold: i) we propose a new second-order joint congestion control and routing framework based on a primal-dual interior-point approach; ii) we establish utility-optimality and queue-stability of the proposed second-order method; and iii) we show how to implement the proposed second-order method in a distributed fashion.

Wireless energy transfer (WET) is a new technology that can be used to charge the batteries of sensor nodes without wires. Although wireless, WET does require a charging station to be brought to within reasonable range of a sensor node so that a good energy transfer efficiency can be achieved. On the other hand, it has been well recognized that data collection with a mobile base station has significant advantages over a static one. Given that a mobile platform is required for WET, a natural approach is to employ the same mobile platform to carry the base station for data collection. In this paper, we study the interesting problem of co-locating a wireless charger (for WET) and a mobile base station on the same mobile platform-the wireless charging vehicle (WCV). The WCV travels along a pre-planned path inside the sensor network. Our goal is to minimize energy consumption of the entire system while ensuring that 1) each sensor node is charged in time so that it will never run out of energy, and 2) all data collected from the sensor nodes are relayed to the mobile base station. We develop a mathematical model for this problem (OPT-t), which is time-dependent. Instead of solving OPT-t directly, we show that it is sufficient to study a special subproblem (OPT-s) which only involves space-dependent variables. Subsequently, we develop a provably near-optimal solution to OPT-s. Our results offer a solution on how to use a single mobile platform to address both WET and data collection in sensor networks.

Wireless energy transfer based on magnetic resonant coupling is a promising technology to replenish energy to a wireless sensor network (WSN). However, charging sensor nodes one at a time poses a serious scalability problem. Recent advances in magnetic resonant coupling show that multiple nodes can be charged at the same time. In this paper, we exploit this multi-node wireless energy transfer technology and investigate whether it is a scalable technology to address energy issues in a WSN. We consider a wireless charging vehicle (WCV) periodically traveling inside a WSN and charging sensor nodes wirelessly. Based on charging range of the WCV, we propose a cellular structure that partitions the two-dimensional plane into adjacent hexagonal cells. We pursue a formal optimization framework by jointly optimizing traveling path, flow routing, and charging time. By employing discretization and a novel Reformulation-Linearization Technique (RLT), we develop a provably near-optimal solution for any desired level of accuracy. Through numerical results, we demonstrate that our solution can indeed address the charging scalability problem in a WSN.

In this paper, we consider the problem of distributed load shedding optimization for disaster recovery in smart grids. We develop distributed second-order interior-point based load shedding algorithms that enjoy a fast quadratic convergence rate. Our main contributions are two-fold: (i) We propose a rooted spanning tree based reformulation that enables our distributed algorithm design; (ii) Based on the spanning tree reformulation, we design distributed computation schemes for our proposed second-order interior-point based load shedding. Collectively, these results serve as an important first step in load shedding and disaster recovery that uses second-order distributed techniques.

This paper addresses the static aircraft sequencing problem over a mixed-mode single runway (or closely interacting parallel runways), which commonly constitutes a critical bottleneck at airports. In contrast with disjunctive formulations, our modeling approach takes advantage of the underlying structure of an asymmetric traveling salesman problem with time-windows. This enables the development of efficient preprocessing and probing procedures, and motivates the derivation of several classes of valid inequalities along with partial convex hull representations to enhance problem solvability via tighter reformulations. The lifted model is further embedded within the framework of two proposed heuristics that are compared against the traditional first-come first-served (FCFS) heuristic with landing priority: an optimized FCFS policy (OFCFS) and a threshold-based suboptimized heuristic (TSH) with an a priori fixing of the relative order of aircraft that are sufficiently time-separated. Computational results using real data based on Doha International Airport (DOH) as well as simulated instances are reported to demonstrate the efficacy of the proposed exact and heuristic solution methods. In particular, for the DOH instances, heuristics OFCFS and TSH achieved an attractive runway utilization (4.3% and 5.0% makespan reduction, respectively, over the base FCFS policy with landing priority), while exhibiting limited aircraft position deviations (0.45 and 0.49 deviations on average, respectively, from the base FCFS positions with landing priority, with similar results being obtained for the simulated instances). The superiority of the proposed optimization models over previous disjunctive formulations is also demonstrated for challenging problem instances, resulting in over 50% CPU savings for the larger instances in our test-bed.

Network-coded cooperative communications (NC-CC) is a new paradigm for communications in wireless networks that employs network coding (NC) to improve the performance of CC. A key problem to harness the potential of NC-CC is how to put sessions into different groups, and assign a relay node for each group. In this paper, we study this joint grouping and relay node selection problem for NC-CC. We provide a formal proof of NP-hardness for this problem. Due to NP-hardness, we propose a distributed and online algorithm and show that it offers near-optimal solution to this problem. The key idea in this algorithm is to have each neighboring relay node of a new session calculate the best local group that it can offer and advertise this information; and then to have the source node of the new session select the best local group to join among all offers. We show that our distributed algorithm has polynomial time complexity. Using extensive numerical results, we show that our distributed algorithm adapts well to online network dynamics.

Due to the rapidly growing scale and heterogeneity of wireless networks, the design of distributed cross-layer optimization algorithms has received significant interest from the networking research community. So far, the standard distributed cross-layer approach in the literature is based on the first-order Lagrangian dual decomposition and the subgradient method, which suffers from a slow convergence rate. In this paper, we make the first known attempt to develop a distributed Newton's method, which is second-order and enjoys a quadratic convergence rate. However, due to the inherent interference in wireless networks, the Hessian matrix of the cross-layer problem has a non-separable structure. As a result, developing a distributed second-order algorithm is far more difficult than its counterpart for wireline networks. Our main contributions in this paper are two-fold: i) For a special network setting where all links mutually interfere, we derive closed-form expressions for the Hessian inverse, which further yield a distributed Newton's method; ii) For general wireless networks where the interference relationships are arbitrary, we propose a double matrix-splitting scheme, which also leads to a distributed Newton's method. Collectively, these results create a new theoretical framework for distributed cross-layer optimization in wireless networks. More importantly, our work contributes to a potential second-order paradigm shift in wireless networks optimization theory.

Wireless energy transfer is a promising technology to fundamentally address energy and lifetime problems in a wireless sensor network (WSN). On the other hand, it has been well recognized that a mobile base station has significant advantages over a static one. In this paper, we study the interesting problem of co-locating the mobile base station on the wireless charging vehicle (WCV). The goal is to minimize energy consumption of the entire system while ensuring none of the sensor nodes runs out of energy. We develop a mathematical model for this complex problem. Instead of studying the general problem formulation (OPT-t), which is time-dependent, we show that it is sufficient to study a special subproblem (OPT-s) which only involves space-dependent variables. Subsequently, we develop a provably near-optimal solution to OPT-s. The novelty of this research mainly resides in the development of several solution techniques to tackle a complex problem that is seemingly intractable at first glance. In addition to addressing a challenging and interesting problem in a WSN, we expect the techniques developed in this research can be applied to address other related networking problems involving time-dependent movement, flow routing, and energy consumption.

Wireless power transfer is a promising technology to fundamentally address energy problems in a wireless sensor network. To make such a technology work effectively, a vehicle is needed to carry a charger to travel inside the network. On the other hand, it has been well recognized that a mobile base station offers significant advantages over a fixed one. In this paper, we investigate an interesting problem of co-locating the mobile base station on the wireless charging vehicle. We study an optimization problem that jointly optimizes traveling path, stopping points, charging schedule, and flow routing. Our study is carried out in two steps. First, we study an idealized problem that assumes zero traveling time, and develop a provably near-optimal solution to this idealized problem. In the second step, we show how to develop a practical solution with non-zero traveling time and quantify the performance gap between this solution and the unknown optimal solution to the original problem.

The cost of energy consumption is an important concern for network operators. In this paper, we study an energy-related problem that focuses on network-wide energy consumption. In the first part of this work, we study how to maximize throughput under a network-wide energy constraint. We formulate this problem as a mixed-integer nonlinear program (MINLP). This formulation differs from prior efforts as it considers a non-zero device power, which complicates the problem. We propose a novel piece-wise linear approximation to transform the nonlinear constraints into linear constraints. We prove that the solution developed under this approach is near-optimal with a guaranteed performance bound. In the second part, we generalize the problem in the first part via a multicriteria optimization framework, which simultaneously optimizes throughput and total network energy. We show how weakly Pareto-optimal solutions can characterize an optimal throughput-energy curve. We offer some interesting properties of the optimal throughput-energy curves, which are useful to both network operators and end-users. Our results fill in some important gaps in the current understanding on optimizing total network energy.

Although femtocell deployments in residential buildings have been increasingly prevalent, femtocell deployment in commercial building environments remains in its infancy. One of the main challenges lies in the femtocell base stations (FBS) placement problem, which is complicated by the buildings' size, layout, structure, and floor/wall separations. In this paper, we investigate a joint FBS placement and power control optimization problem in commercial buildings with the aim to prolong mobile handsets' battery lives. We first construct a mathematical model that takes into account the unique floor attenuation factor (FAF) and FBS installation restrictions in building environments. Based on this model, we propose a novel two-step reformulation approach to convert the original mixed-integer nonconvex problem (MINCP) into a mixed-integer linear program (MILP), which enables the design of efficient global optimization algorithms. We then devise a global optimization algorithm by utilizing the MILP in a branch-and-bound framework. This approach guarantees finding a global optimal solution. We conduct extensive numerical studies to demonstrate the efficacy of the proposed algorithm. Our mathematical reformulation techniques and optimization algorithm offer useful theoretical insights and valuable tools for future commercial building femtocell deployments.

The fast growing scale and heterogeneity of current communication networks necessitate the design of distributed cross-layer optimization algorithms. So far, the standard approach of distributed cross-layer design is based on dual decomposition and the subgradient algorithm, which is a first-order method that has a slow convergence rate. In this paper, we focus on solving a joint multi-path routing and flow control (MRFC) problem by designing a new distributed Newton's method, which is a second-order method and enjoys a quadratic rate of convergence. The major challenges in developing a distributed Newton's method lie in decentralizing the computation of the Hessian matrix and its inverse for both the primal Newton direction and dual variable updates. By appropriately reformulating, rearranging, and exploiting the special problem structures, we show that it is possible to decompose such computations into source nodes and links in the network, thus eliminating the need for global information. Furthermore, we derive closed-form expressions for both the primal Newton direction and dual variable updates, thus significantly reducing the computational complexity. The most attractive feature of our proposed distributed Newton's method is that it requires almost the same scale of information exchange as in first-order methods, while achieving a quadratic rate of convergence as in centralized Newton methods. We provide extensive numerical results to demonstrate the efficacy of our proposed algorithm. Our work contributes to the advanced paradigm shift in cross-layer network design that is evolving from first-order to second-order methods.

Wireless energy transfer based on magnetic resonant coupling is a promising technology to replenish energy to sensor nodes in a wireless sensor network (WSN). However, charging sensor node one at a time poses a serious scalability problem. Recent advances in magnetic resonant coupling shows that multiple nodes can be charged at the same time. In this paper, we exploit this multi-node wireless energy transfer technology to address energy issue in a WSN. We consider a wireless charging vehicle (WCV) periodically traveling inside a WSN and charging sensor nodes wirelessly. We propose a cellular structure that partitions the two-dimensional plane into adjacent hexagonal cells. The WCV visits these cells and charge sensor nodes from the center of a cell. We pursue a formal optimization framework by jointly optimizing traveling path, flow routing and charging time. By employing discretization and a novel Reformulation-Linearization Technique (RLT), we develop a provably near-optimal solution for any desired level of accuracy.

While the deployment of femtocell in residential buildings has firmly positioned it as a major performance leap in wireless communications, its deployment in commercial buildings remains under-explored. In commercial building environments, the femtocell base station (FBS) placement planning is particularly challenging due to the impact of the building size, layout, structure, and wall/floor separation. In this paper, we study the problem of jointly optimizing FBS placement and power control in commercial building environments to prolong the battery life for mobile handsets. We first propose a mathematical model that captures the unique building features. Based on this model, we employ a set of novel transformation strategies to formulate the FBS placement problem as a mixed-integer convex program (MICP). Accordingly, we propose an effective global optimization algorithm based on using the convex relaxation of the formulated MICP within a branch-and-bound framework. This approach guarantees finding a global optimal solution. To demonstrate the efficacy of our algorithm, we conduct extensive numerical studies. Our proposed model and optimization approach offer useful insights into femtocell deployments in commercial buildings.

Cooperative networking is known to have significant potential in increasing network capacity and transmission reliability. Although there have been extensive studies on applying cooperative networking in multi-hop ad hoc networks, most works are limited to the basic three-node relay scheme and single-antenna systems. These two limitations are interconnected and both are due to a limited theoretical understanding of the optimal power allocation structure in MIMO cooperative networks (MIMO-CN). In this paper, we study the structural properties of the optimal power allocation in MIMO-CN with per-node power constraints. More specifically, we show that the optimal power allocations at the source and each relay follow a matching structure in MIMO-CN. This result generalizes the power allocation result under the basic three-node setting to the multi-relay setting, for which the optimal power allocation structure has been heretofore unknown. We further quantify the performance gain due to cooperative relay and establish a connection between cooperative relay and pure relay. Finally, based on these structural insights, we reduce the MIMO-CN rate maximization problem to an equivalent scalar formulation. We then propose a global optimization method to solve this simplified and equivalent problem.

It has been shown that cooperative communications (CC) has the potential to significantly increase the capacity of wireless networks. However, most of the existing results are limited to single-hop wireless networks. To explore the behavior of CC in multi-hop wireless networks, we study a joint optimization problem of relay node assignment and flow routing for a group of sessions. We develop a mathematical model and propose a solution procedure based on the branch-and-bound framework augmented with cutting planes (BB-CP). We design several novel components to speed-up the computational time of BB-CP. Via numerical results, we show the potential rate gain that can be achieved by incorporating CC in multi-hop networks.

Wireless sensor networks are constrained by limited battery energy. Thus, finite network lifetime is widely regarded as a fundamental performance bottleneck. Recent breakthrough in the area of wireless power transfer offers the potential of removing this performance bottleneck, i.e., allowing a sensor network to remain operational forever. In this paper, we investigate the operation of a sensor network under this new enabling energy transfer technology. We consider the scenario of a mobile charging vehicle periodically traveling inside the sensor network and charging each sensor node's battery wirelessly. We introduce the concept of renewable energy cycle and offer both necessary and sufficient conditions. We study an optimization problem, with the objective of maximizing the ratio of the wireless charging vehicle (WCV)'s vacation time over the cycle time. For this problem, we prove that the optimal traveling path for the WCV is the shortest Hamiltonian cycle and provide a number of important properties. Subsequently, we develop a near-optimal solution by a piecewise linear approximation technique and prove its performance guarantee.

Network-coded cooperative communications (NC-CC) is a new paradigm in wireless networks that employs network coding (NC) to improve the performance of CC. The core mechanism to harness the benefits of NC-CC is to appropriately combine sessions into separate groups, and then have each group select the most beneficial relay node for NC-CC. In this paper, we study this joint grouping and relay node selection problem for NC-CC. Due to NP-hardness of problem, we propose a distributed and online algorithm that offers near-optimal solution to this problem. The key idea in our algorithm is to have each neighboring relay node of a new session determine and offer its best local group; and then to have the source node of the new session select the best group among all offers. We show that our distributed algorithm has polynomial complexity. Using extensive numerical results, we show that our distributed algorithm adapts well to online network dynamics.

Traditional wireless sensor networks are constrained by limited battery energy. Thus, finite network lifetime is widely regarded as a fundamental performance bottleneck. Recent breakthrough in the area of wireless energy transfer offers the potential of removing such performance bottleneck, i.e., allowing a sensor network remain operational forever. In this paper, we investigate the operation of a sensor network under this new enabling energy transfer technology. We consider the scenario of a mobile charging vehicle periodically traveling inside the sensor network and charging each sensor node's battery wirelessly. We introduce the concept of renewable energy cycle and offer both necessary and sufficient conditions. We study an optimization problem, with the objective of maximizing the ratio of the wireless charging vehicle (WCV)'s vacation time over the cycle time. For this problem, we prove that the optimal traveling path for the WCV is the shortest Hamiltonian cycle and provide a number of important properties. Subsequently, we develop a near-optimal solution and prove its performance guarantee.

We study a multicast communication problem in a multi-hop ad hoc network where each node is equipped with a cognitive radio (CR). The goal is to minimize the required network-wide resource to support a set of multicast sessions, with a given bit rate requirement for each multicast session. The unique characteristics and complexity associated with CR distinguish this problem from existing multicast problems for ad hoc networks. In this paper, we formulate this problem via a cross-layer approach by taking consideration of scheduling and routing jointly. Although the problem formulation is in the form of a mixed-integer linear program, we develop a polynomial-time algorithm that offers highly competitive solutions. By comparing the solution values with a lower bound, we show that the proposed algorithm can provide a solution that is close to the optimum.

Cognitive radio networks (CRNs) have the potential to utilize spectrum efficiently and are positioned to be the core technology for the next-generation multihop wireless networks. An important problem for such networks is its capacity. We study this problem for CRNs in the SINR (signal-to-interference-and-noise-ratio) model, which is considered to be a better characterization of interference (but also more difficult to analyze) than disk graph model. The main difficulties of this problem are two-fold. First, SINR is a nonconvex function of transmission powers; an optimization problem in the SINR model is usually a nonconvex program and NP-hard in general. Second, in the SINR model, scheduling feasibility and the maximum allowed flow rate on each link are determined by SINR at the physical layer. To maximize capacity, it is essential to follow a cross-layer approach, but joint optimization at physical (power control), link (scheduling), and network (flow routing) layers with the SINR function is inherently difficult. In this paper, we give a mathematical characterization of the joint relationship among these layers. We devise a solution procedure that provides a (1- \varepsilon ) optimal solution to this complex problem, where \varepsilon is the required accuracy. Our theoretical result offers a performance benchmark for any other algorithms developed for practical implementation. Using numerical results, we demonstrate the efficacy of the solution procedure and offer quantitative understanding on the interaction of power control, scheduling, and flow routing in a CRN.

It has been shown that cooperative communications (CC) have the potential to significantly increase the capacity of wireless networks. However, most of the existing results are limited to single-hop wireless networks. To illustrate the benefits of CC in multi-hop wireless networks, we solve a joint optimization problem of relay node assignment and flow routing for concurrent sessions. We study this problem via mathematical modeling and solve it using a solution procedure based on the branch-and-cut framework. We design several novel components to speed-up the computation time of branch-and-cut. Via numerical results, we show the significant rate gains that can be achieved by incorporating CC in multi-hop networks.

In this paper, we model and solve the strategic problem of minimizing the expected loss inflicted by a hostile terrorist organization. An appropriate allocation of certain capability-related, intent-related, vulnerability-related, and consequence-related resources is used to reduce the probabilities of success in the respective attack-related actions and to ameliorate losses in case of a successful attack. We adopt a nested event tree optimization framework and formulate the problem as a specially structured nonconvex factorable program. We develop two branch-and-bound schemes based, respectively, on utilizing a convex nonlinear relaxation and a linear outer approximation, both of which are proven to converge to a global optimal solution. We also design an alternative direct mixed-integer programming model representation for this case, and we investigate a fundamental special-case variant for this scheme that provides a relaxation and affords an optimality gap measure. Several range reduction, partitioning, and branching strategies are proposed, and extensive computational results are presented to study the efficacy of different compositions of these algorithmic ingredients, including comparisons with the commercial software BARON. A sensitivity analysis is also conducted to explore the effect of certain key model parameters.

The main airline operations consist of schedule planning, fleet assignment, aircraft routing, and crew scheduling. To improve profitability, we present in this paper an integrated fleet assignment model with schedule planning by simultaneously considering optional flight legs to select along with the assignment of aircraft types to all scheduled legs. In addition, we consider itinerary-based demands for multiple fare classes. A polyhedral analysis is conducted of the proposed mixed-integer programming model to tighten its representation via several classes of valid inequalities. Solution approaches are developed by applying Benders' decomposition method to the resulting lifted model, and computational results are presented using real data obtained from a major U.S. airline to demonstrate the efficacy of the proposed procedures.

In this paper, we revisit the problem of determining the minimum-length schedule that satisfies certain traffic demands in a wireless network. Traditional approaches for the determination of minimum-length schedules are based on a collision channel model, in which neighboring transmissions cause destructive interference if and only if they are within the “interference region” of the receiving nodes. By contrast, we adopt here a more realistic model for the physical layer by requiring that a threshold be exceeded by the signal-to-interference-plus-noise ratio (SINR) for a transmission to be successful. We present a novel formulation of the problem that incorporates various power and rate adaptation schemes while seamlessly integrating the generation of “matchings” (i.e., sets of links that can be activated simultaneously) by taking into consideration the SINR constraints at the receivers. For the formulated problem, we propose a column-generation-based solution method and show that it theoretically converges to a globally optimal solution, with a potential advantage of not having to enumerate all the feasible matchings a priori. We also discuss the influence of power control, spatial reuse, and variable transmission rates on network performance. Furthermore, we include aspects of the routing problem and provide computational results for our proposed column-generation-based solution procedure.

We consider the problem of minimum-length scheduling of point-to-point links in a spatial TDMA (STDMA) based wireless network with Rayleigh fading of both desired and interference signals. The problem formulation integrates the activation of multiple sets of links in the network, while taking into account their explicit statistical variations. We assume uniform (fixed) transmission power at all nodes and propose an algorithm based on a column generation approach, which takes into consideration the signal-to-interference and noise ratio (SINR) constraints at the receivers in order to generate a link schedule that minimizes the schedule length. For the formulated problem, we show that this column generation based approach can converge to a globally optimal solution.

Broadband multi-carrier MIMO (MC-MIMO) is a promising technology that could provide significant capacity gain for wireless ad hoc networks. For MC-MIMO networks, since the capacity is affected by potential mutual interference on subcarriers, scheduling for subcarriers and algorithms for power control/allocation become key problems to harness their potential. However, due to non-convexity and large size of the underlying problem, there are few results on this important problem. In this paper, we first show that the non-convex problem for MC-MIMO networks satisfies the so-called concave perturbation condition, which gives a zero duality gap for the problem. This important result allows us to tackle the problem in the dual domain. The dual approach has the highly desirable benefit of reducing the complexity of the underlying problem, which allows us to design a near-optimal off-line algorithm. In addition to the off-line algorithm, we also devise an online adaptive algorithm (OAA) without the need of channel distribution information (CDI). We show that OAA is able to achieve the same result as the off-line algorithm.

This paper is concerned with the optimal constrained pruning of decision trees. We present a novel 0–1 programming model for pruning the tree to minimize some general penalty function based on the resulting leaf nodes, and show that this model possesses a totally unimodular structure that enables it to be solved as a shortest-path problem on an acyclic graph. Moreover, we prove that this problem can be solved in strongly polynomial time while incorporating an additional constraint on the number of residual leaf nodes. Furthermore, the framework of the proposed modeling approach renders it suitable to accommodate different (multiple) objective functions and side-constraints, and we identify various such modeling options that can be applied in practice. The developed methodology is illustrated using a numerical example to provide insights, and some computational results are presented to demonstrate the efficacy of solving generically constrained problems of this type. We also apply this technique to a large-scale transportation analysis and simulation system (TRANSIMS), and present related computational results using real data to exhibit the flexibility and effectiveness of the proposed approach.

Abstract This article examines logistical systems where it is desirable to appropriately ascertain the joint composition of the sequences of vehicles that are to be physically connected along with determining their delivery routes. Such assembly‐routing problems occur in the truck manufacturing industry, for example, where combinations of trucks to be delivered to dealerships are composed and are subsequently dispatched via appropriately optimized delivery routes, which are in turn restricted by the particular sequence in which the trucks are connected. A similar structure is exhibited in the business of shipping goods via boat‐towed barges along inland waterways, or via trains through railroad networks. We present a novel unifying model and a column generation‐based optimization approach for this challenging class of joint vehicle assembly‐routing problems. In addition, we suggest several extensions to accommodate particular industrial settings where assembly sequence‐dependent delivery routes are necessary, as well as those where driver‐ and equipment‐based restrictions are imposed. Computational experience is provided using realistic data from a case‐study involving a major truck manufacturing company to demonstrate the applicability of the proposed methodology in practice. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

Recently, researchers showed that "dirty paper coding" (DPC) achieves the capacity region of MIMO Gaussian broadcast channels (MIMO-BC). So far, there has been little study on how this fundamental information-theoretic result will impact the cross-layer design for MIMO-based ad hoc networks. To fill this gap, we consider the problem of jointly optimizing DPC power allocation at the physical layer and multihop/multipath routing at the network layer for MIMO-based ad hoc networks. This optimization problem turns out to be a challenging non-convex problem. To address this difficulty, we transform the original problem to an equivalent problem by exploiting the uplink-downlink duality. For the transformed problem, we propose a solution procedure that integrates Lagrangian dual decomposition, conjugate gradient projection based on matrix differential calculus, and cutting-plane methods.

In this paper, we investigate the maximum weighted sum-rate problem (MWSR) of MIMO Gaussian broadcast channels (MIMO-BC). We propose an efficient algorithm that employs conjugate gradient projections (CGP) to solve the MWSR problem. The proposed CGP offers provable convergence. By deflecting gradient direction to its Hessian conjugate, CGP enjoys a superlinear convergence rate. Also, CGP has a modest memory requirement. It only needs the solution information from the previous step. More importantly, CGP is able to solve the MWSR problem with arbitrary number of antennas on both sides of a MIMO-BC.

We present a new deflected subgradient scheme for generating good quality dual solutions for linear programming (LP) problems and utilize this within the context of large-scale airline crew planning problems that arise in practice. The motivation for the development of this method came from the failure of a black-box-type approach implemented at United Airlines for solving such problems using column generation in concert with a commercial LP solver, where the software was observed to stall while yet remote from optimality. We identify a phenomenon called dual noise to explain this stalling behavior and present an analysis of the desirable properties of dual solutions in this context. The proposed deflected subgradient approach has been embedded within the crew pairing solver at United Airlines and tested using historical data sets. Our computational experience suggests a strong correlation between the dual noise phenomenon and the quality of the final solution produced, as well as with the accompanying algorithmic performance. Although we observed that our deflected subgradient scheme yielded an average speed-up factor of 10 for the column generation scheme over the commercial solver, the average reduction in the optimality gap over the same number of iterations was better by a factor of 26, along with an average reduction in the dual noise by a factor of 30. The results from the column generation implementation suggest that significant benefits can be obtained by using the deflected subgradient-based scheme instead of a black-box-type or standard solver approach to solve the intermediate linear programs that arise within the column generation scheme.

Cognitive radio (CR) capitalizes advances in signal processing and radio technology and is capable of reconfiguring RF and switching to desired frequency bands. It is a frequency-agile data communication device that is vastly more powerful than recently proposed multi-channel multi-radio (MC-MR) technology. In this paper, we investigate the important problem of multi-hop networking with CR nodes. For such a network, each node has a pool of frequency bands (typically of unequal size) that can be used for communication. The potential difference in the bandwidth among the available frequency bands prompts the need to further divide these bands into sub-bands for optimal spectrum sharing. We characterize the behavior and constraints for such a multi-hop CR network from multiple layers, including modeling of spectrum sharing and sub-band division, scheduling and interference constraints, and flow routing. We develop a mathematical formulation with the objective of minimizing the required network-wide radio spectrum resource for a set of user sessions. Since the formulated model is a mixed-integer non-linear program (MINLP), which is NP-hard in general, we develop a lower bound for the objective by relaxing the integer variables and using a linearization technique. Subsequently, we design a near-optimal algorithm to solve this MINLP problem. This algorithm is based on a novel sequential fixing procedure, where the integer variables are determined iteratively via a sequence of linear programs. Simulation results show that solutions obtained by this algorithm are very close to the lower bounds obtained via the proposed relaxation, thus suggesting that the solution produced by the algorithm is near-optimal.

MIMO-based communications systems have great potential to improve network capacity for wireless ad hoc networks. Due to unique physical layer characteristics associated with MIMO, network performance is tightly coupled with mechanisms at physical, link, and routing layers. So far, research on MIMO-based wireless ad hoc networks is still in its infancy and few results are available. In this paper, we consider the problem of jointly optimizing power and bandwidth allocation at each node and multi-hop/multi-path routing in a MIMO-based wireless ad hoc network. We develop a solution procedure to this cross-layer optimization problem and use simulations to validate the efficacy of this solution.

There is growing interest in employing ultra-wideband (UWB) communication systems at the physical layer for multihop wireless networks. Recent efforts show that networking problems involving UWB systems should follow a cross-layer approach with consideration at multiple layers. Due to the nonlinear nature of the optimization problem, there are very limited theoretical results for this important problem. In this paper, we address this problem by considering a UWB-based ad hoc network. We study how to maximize capacity (in the form of a data rate utility) for a set of communication sessions. Via a cross-layer approach, we formulate this utility maximization problem into a nonlinear programming (NLP) problem, which takes into consideration routing, scheduling, and power control. We develop a solution procedure based on the so-called branch-and-bound framework. Within this framework, we employ a powerful optimization technique called reformulation linearization technique (RLT). We use numerical results to validate the efficacy of this solution procedure and offer insights on UWB-based ad hoc networks. This work provides a theoretical result for the achievable performance bound for a UWB-based ad hoc network.

Maximizing the total mutual information of multiuser multiple-input multiple-output (MIMO) systems with interference is a challenging problem. In this paper, we consider the power control problem of finding the maximum sum of mutual information for a multiuser network with mutually interfered MIMO links. We propose a new and powerful global optimization method using a branch-and-bound (BB) framework, coupled with a novel reformulation-linearization technique (RLT). The proposed BB/RLT guarantees finding a global optimum for multiuser MIMO networks with interference. To reduce the complexity of BB/RLT, we propose a modified BB variable selection strategy to accelerate the convergence process. Numerical examples are also given to demonstrate the efficacy of the proposed solution.

Software defined radio (SDR) capitalizes advances in signal processing and radio technology and is capable of reconfiguring RF and switching to desired frequency bands. It is a frequency-agile data communication device that is vastly more powerful than recently proposed multi-channel multi-radio (MC-MR) technology. In this paper, we investigate the important problem of multi-hop networking with SDR nodes. For such network, each node has a pool of frequency bands (not necessarily of equal size) that can be used for communication. The uneven size of bands in the radio spectrum prompts the need of further division into sub-bands for optimal spectrum sharing. We characterize behaviors and constraints for such multi-hop SDR network from multiple layers, including modeling of spectrum sharing and sub-band division, scheduling and interference constraints, and flow routing. We give a formal mathematical formulation with the objective of minimizing the required network-wide radio spectrum resource for a set of user sessions. Since such problem formulation falls into mixed integer non-linear programming (MINLP), which is NP-hard in general, we develop a lower bound for the objective by relaxing the integer variables and linearization. Subsequently, we develop a near-optimal algorithm to this MINLP problem. This algorithm is based on a novel sequential fixing procedure, where the integer variables are determined iteratively via a sequence of linear programming. Simulation results show that solutions obtained by this algorithm are very close to lower bounds obtained via relaxation, thus suggesting that the solution produced by the algorithm is near-optimal.

Researchers have recently shown that the dirty-paper coding (DPC) is the optimal transmission strategy for multiple-input multiple-output Gaussian broadcast channels (MIMO BC). Moreover, by the channel duality, the nonconvex MIMO BC sum rate problem can be transformed to the convex dual MIMO multiple-access channel (MIMO MAC) problem with a sum power constraint. In this paper, we design an efficient algorithm based on conjugate gradient projection (CGP) to solve the MIMO BC maximum sum rate problem. Our proposed CGP algorithm solves the dual sum power MAC problem by utilizing the powerful concept of Hessian conjugate. We also develop a rigorous algorithm to solve the projection problem. We show that CGP enjoys provable convergence, scalability, and efficiency for large MIMO BC systems.

In this paper, we consider the problem of optimal multipath routing for providing application performance guarantees in multi-hop wireless networks, using multiple description video streaming as our target application. We address this problem, which is shown to be NP-hard, with a novel reformulation-linearization technique (RLT) and branch-and-bound-based approach, and develop an algorithm that produces a pair of paths within the (1 - epsiv) range of the global optimum. The proposed algorithm is computationally efficient and this (1 - epsiv) optimal algorithm provides an elegant tradeoff between optimality and computational complexity.

MIMO-based systems have great potential to improve network capacity for wireless mesh networks (WMNs). Due to unique physical layer characteristics associated with MIMO systems, network performance is tightly coupled with mechanisms at physical layer and link layer. So far, research on MIMO-based WMNs is still in its infancy and little results are available in this important area. In this paper, we consider the problem of jointly optimizing power and bandwidth allocation at each node and multihop/multipath routing in a MIMO-based WMN where links operate in orthogonal channels. To solve this problem, we develop a mathematical solution procedure, which combines Lagrangian dual decomposition, gradient projection, and cutting-plane methods. We provide theoretical insights in deriving gradient projection and cutting plane methods. We also use simulations to verify the efficacy of our algorithm.

We consider nondifferentiable optimization problems that arise when solving Lagrangian duals of large-scale linear programs. Different from traditional subgradient-based approaches, we design two new methods that attempt to circumvent or obviate the nondifferentiability of the objective function, so that standard differentiable optimization techniques could be used. These methods, called the perturbation technique and the barrier-Lagrangian reformulation, are implemented as initialization procedures to provide a warm start to a theoretically convergent nondifferentiable optimization algorithm. Our computational study reveals that this two-phase strategy produces much better solutions with less computation in comparison with both the stand-alone nondifferentiable optimization procedure employed, and the popular Held-Wolfe-Crowder subgradient heuristic. Furthermore, the best version of this composite algorithm is shown to consume only about 3.19% of the CPU time required by the commercial linear programming solver CPLEX 8.1 (using the dual simplex option) to produce the same quality solutions. We also demonstrate that this initialization technique greatly facilitates quick convergence in the primal space when used as a warm start for ergodic-type primal recovery schemes.

Traditionally, routing is considered solely as a network layer problem and has been decoupled from application layer objectives. Although such an approach offers simplicity in the design of the protocol stack, it does not offer good performance for certain applications such as video. In this paper, we explore the problem of how to perform routing with the objective of optimizing application layer performance. Specifically, we consider how to perform multipath routing for multiple description (MD) video in a multi-hop wireless network. We formulate this problem into an optimization problem with application performance metric as the objective function and routing and link layer considerations as constraints. We develop a formal branch-and-bound framework and exploit the so-called reformulation-linearization technique (RLT) in the solution procedure. We show that this solution procedure is able to produce a set of routes whose objective value is within (1 - e) of the optimum. We use simulation results to substantiate the efficacy of the solution procedure and compare the performance with that under non-cross-layer approach.

For media streaming in ad hoc networks, service replication has been demonstrated to be a quite effective countermeasure to streaming interruptions caused by fragile paths and dynamic topology. In this paper, we study the problem of joint routing and server selection for double description (DD) video streaming in ad hoc networks. We formulate the task as a combinatorial optimization problem and present tight lower and upper bounds for the achievable distortion. The upper bound provides a feasible solution to the formulated problem. Our extensive numerical results show that the bounds are very close to each other for all the cases studied, indicating the near-global optimality of the derived upper bounding solution. Moreover, we observe significant gains in video quality achieved by the proposed approach over existing server selection schemes. This justifies the importance of jointly considering routing and server selection for optimal MD video streaming

Maximizing the total mutual information of a multiuser multiple-input multiple-output (MIMO) system with interference is a well-known and challenging problem. In this paper, we consider the power control problem of finding the maximum sum of mutual information for multiuser MIMO systems with equal power allocation at each link. A new and powerful global optimization method using a branch-and-bound framework coupled with the reformulation-linearization technique (BB/RLT) is introduced. The proposed BB/RLT is the first such method that guarantees finding a global optimum for multiuser MIMO systems with interference. In addition, we propose a modified branch-and-bound (BB) variable selection strategy to accelerate the convergence process, and apply the proposed technique to several MIMO systems in order to demonstrate its efficacy.

Video communication is an important application area for a multihop wireless network. This paper studies the problem of finding the optimal encoding rates for a number of video sessions in such network. The objective is to maximize the video quality at the receivers and the optimization space takes into consideration, the interaction among all the active video sessions. A branch-and-bound solution procedure is proposed to solve this nonconvex, non-polynomial programming problem. Using analytical and simulation results, we show that this solution procedure is an effective approach for addressing such complex cross-layer optimization problem

This paper considers ultra-wideband (UWB)-based sensor networks and studies the following problem: given a set of source sensor nodes in the network each generating a certain data rate, is it possible to relay all these rates successfully to the base station? We will show that such problem is intrinsic cross-layer, and subsequently we formulate an optimization problem, with joint consideration of link-layer scheduling, power control, and network-layer routing. For large-sized networks, we propose an efficient heuristic algorithm by partitioning the given network into a core centered around the base station and a boundary edge. For the network core, we formulate a nonlinear programming problem, which can be solved by branch-and-bound approach. For data generated at network edge, we propose an algorithm to connect it to the network core. We use simulation results to demonstrate the efficacy of the proposed solution procedure, as well as the importance of cross-layer considerations.

Abstract In this article, we consider an approach‐dependent, time‐dependent, label‐constrained shortest path problem. This is a variant of the shortest path problem defined on a transportation network comprised of a set of nodes and a set of directed arcs such that each arc has an associated label designating a mode of transportation, and an associated travel‐time function that depends on the time of arrival at the tail node, as well as on the link via which this node was approached. A label constraint is specified that controls the admissible sequence of transportation modes, and the approach‐dependent travel‐time feature models turn‐penalties and prohibitions in transportation networks, whereby the time spent at an intersection before entering the next link depends on whether we travel straight through the intersection, or make a right turn at it, or make a left turn at it, as permissible. We propose two effective algorithms to solve this problem and present related theoretical complexity results. In addition, we also explore various heuristic delay estimation and network curtailment schemes that can be used to confine the search to only the more promising subsets of the network to reduce computational effort while preserving near‐optimality. Extensive empirical results using available data for the Portland, OR, and Blacksburg, VA, transportation networks are presented to demonstrate the efficacy of the developed procedures. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(2), 57–67 2006

We study the problem of multipath routing for double description (DD) video in wireless ad hoc networks. We follow an application-centric cross-layer approach and formulate an optimal routing problem that minimizes the application layer video distortion. We show that the optimization problem has a highly complex objective function and an exact analytic solution is not obtainable. However, we find that a meta-heuristic approach such as genetic algorithms (GAs) is eminently effective in addressing this type of complex cross-layer optimization problems. We provide a detailed solution procedure for the GA-based approach. Simulation results demonstrate the superior performance of the GA-based approach versus several other approaches. Our efforts in this work provide an important methodology for addressing complex cross-layer optimization problems, particularly those involved in the application and network layers

Multiple description (MD) coding has a great potential for multimedia communications in wireless ad hoc networks. In this paper, we study the important problem of joint routing and server selection for MD video in ad hoc networks. We take a cross-layer approach to formulate the task as a combinatorial optimization problem and present tight lower and upper bounds for the achievable distortion. The upper bound also provides a feasible solution to the formulated problem. Our extensive numerical results show that the bounds are very close to each other for all the cases studied, indicating the near-global optimality of the derived upper bounding solution. Moreover, we observe significant gains in video quality achieved by the proposed approach over existing server selection schemes. This justifies the importance of jointly considering routing and server selection for optimal MD video streaming in wireless ad hoc networks. The proposed algorithms are computationally efficient and can be easily incorporated into existing routing protocols.

Real-time multimedia communication is an important service that should be supported in wireless ad hoc networks, In this paper we consider the problem of how to optimally support multiple concurrent video communication sessions in an ad hoc network. Our problem formulation follows an application-centric cross-layer approach with the objective of minimizing the average distortion for all video sessions via finding optimal paths for each session. Since this network-wide optimization problem is shown to be NP-complete, we pursue to develop competitive heuristic algorithms to address this problem. We find that genetic algorithms (GA) are eminently efficient in solving such cross-layer problems with complex objective functions and constraints. We describe a detailed solution procedure based on the GA approach and use numerical results to demonstrate its superior performance over other conventional approaches. Our efforts in this work provide an important methodology for addressing cross-layer network-wide optimal routing problems for video applications.

We consider a wireless ad hoc network where each node employs a single-beam directional antenna and is provisioned with limited energy. We are interested in an online multicast routing algorithm for successive multicast communication requests with the aim of maximizing network lifetime. The beamforming property associated with single-beam directional antenna introduces some unique problems that do not exist for omnidirectional antennas and therefore significantly increases the design space for routing algorithms. The contributions of this paper are twofold. First, we provide some important theoretical understanding on various multicast problems and deduce that even an offline version of this problem is NP-hard. Second, we develop a highly competitive online heuristic algorithm that takes network lifetime consideration directly into iterative calculations and show that an algorithm designed under this methodology provides consistently better performance than the current state-of-the-art algorithm that takes remaining energy into iterative calculations. The theoretical results and heuristic algorithm in this paper offer some important insights on algorithmic design for energy-constrained wireless ad hoc networks with directional antennas.

As developments in wireless ad hoc networks continue, there is an increasing expectation with regard to supporting content-rich multimedia communications (e.g., video) in such networks, in addition to simple data communications. The recent advances in multiple description (MD) video coding have made it highly suitable for multimedia applications in such networks. In this paper, we study the important problem of multipath routing for MD video in wireless ad hoc networks. We follow an application-centric cross-layer approach and formulate an optimal routing problem that minimizes the application layer video distortion. We show that the optimization problem has a highly complex objective function and an exact analytic solution is not obtainable. However, we find that a meta-heuristic approach such as genetic algorithms (GAs) is eminently effective in addressing this type of complex cross-layer optimization problems. We provide a detailed solution procedure for the GA-based approach, as well as a tight lower bound for video distortion. We use numerical results to demonstrate the superior performance of the GA-based approach and compare it to several other approaches. Our efforts in this work provide an important methodology for addressing complex cross-layer optimization problems, particularly those involving application and network layers.

Ultra-wideband (UWB) has great potential for wireless communications in emerging applications such as sensor networks. This paper considers UWB-based sensor networks and studies the following problem: given a set of source sensor nodes in the network each generating a certain data rate, is it possible to relay all these rates successfully to the base-station? We follow a cross-layer optimization approach, with joint consideration of link layer scheduling, power control, and network layer routing. The optimization problem is formulated as a non-linear programming problem. For small-sized networks, we develop a powerful approximation solution procedure to this problem based on the branch-and-bound approach and the novel Reformulation-Linearization Technique (RLT). For large-sized networks, we propose an efficient heuristic algorithm by partitioning the sensor network into a core centered around the base-station and an edge that is outside the core. We also provide a closed-form analysis for the maximum rate that a base-station can receive. Simulation results exhibit the efficacy of our proposed optimization solution procedure and demonstrate the importance of the cross-layer approach to UWB-based sensor networks.

Energy constraints have had a significant impact on the design and operation of wireless sensor networks. In this paper, we investigate base station selection (or anycast) problem in wireless sensor networks. We consider a wireless sensor network having multiple base stations (data sink nodes), where each source node must send all its locally generated data to only one base station. To maximize the network lifetime, it is essential to optimally match each source node to a particular base station in addition to finding an optimal routing solution. We propose a polynomial time heuristic for optimal base station selection for anycast via a sequential fixing procedure, under the assumption that the bit rate from each source node is constant. Through extensive simulation results, we show that this heuristic has excellent performance behavior and is a tight low bound that is very close to optimal solution for the original optimization problem.

Abstract — Wireless sensor networks that operate on batteries have limited network lifetime. There have been extensive recent research efforts on how to design protocols and algorithms to prolong network lifetime. However, due to energy constraint, even under the most efficient protocols and algorithms, the network lifetime may still be unable to meet the mission’s requirements. In this paper, we consider the energy provisioning problem for a two-tier wireless sensor network. In addition to provisioning additional energy on the existing nodes, we also consider deploying relay nodes (RNs) into the network to mitigate network geometric deficiency and prolong network lifetime. We formulate the joint problem of energy provisioning and relay node placement (EP-RNP) into a mixed-integer nonlinear programming (MINLP) problem. Since an MINLP problem is NP-hard in general, and even the state-of-the-art software and techniques are unable to offer satisfactory solutions, we develop a heuristic algorithm, called SPINDS, to address this problem. We show a number of novel algorithmic design techniques in the design of SPINDS that effectively transforms a complex MINLP problem into linear programming (LP) problems without losing critical points in its search space. Through numerical results, we show that SPINDS offers very attractive solution and some important insights to the EP-RNP problem. Index Terms — Energy provisioning, relay node placement, power control, network lifetime, flow routing, wireless sensor networks. I.

We consider the problem of multicasting multiple description (MD) video in wireless ad hoc networks. We follow an application-centric, cross-layer approach with the objective of minimizing video distortion. The contribution of this paper is twofold. First, we propose a practical MD video multicast scheme that uses multiple trees to achieve an improved error resilience performance. The proposed scheme also takes into account highly diverse wireless link bandwidths by using scalable coding for each description, thus further improving the overall video quality. Second, we formulate the optimized multicast routing as a combinatorial optimization problem and propose an efficient genetic algorithm (GA)-based metaheuristic solution procedure. Performance comparison with existing approaches show significant gains for a wide range of network operating conditions.

We study the network lifetime problem by considering not only the maximized time until the first node fails, but also the maximized lifetime for all the nodes in the network which we define as the lexicographic max-min (LMM) node lifetime problem. The main contributions of this paper are two-fold. First, we develop a polynomial-time algorithm to derive the LMM-optimal node lifetime vector, which effectively circumvents the computational complexity problem associated with an existing state-of-the-art approach, which is exponential. Second, we present a simple (also polynomial-time) algorithm to calculate the flow routing schedule such that the LMM-optimal node lifetime vector can be achieved. Our results in this paper advance the state-of-the-art algorithmic design to network-wide node lifetime problems.

An important performance consideration for wireless sensor networks is the amount of information collected by all the nodes in the network over the course of network lifetime. Since the objective of maximizing the sum of rates of all the nodes in the network can lead to a severe bias in rate allocation among the nodes, we advocate the use of lexicographical max-min (LMM) rate allocation for the nodes. To calculate the LMM rate allocation vector, we develop a polynomial-time algorithm by exploiting the parametric analysis (PA) technique from linear programming (LP), which we call serial LP with Parametric Analysis (SLP-PA). We show that the SLP-PA can be also employed to address the so-called LMM node lifetime problem much more efficiently than an existing technique proposed in the literature. More important, we show that there exists an elegant duality relationship between the LMM rate allocation problem and the LMM node lifetime problem. Therefore, it is sufficient to solve any one of the two problems and important insights can be obtained by inferring duality results for the other problem.

In this paper, we consider a network design problem arising in the context of deploying synchronous optical networks (SONET) using a unidirectional path switched ring architecture, a standard of transmission using optical fiber technology. Given several rings of this type, the problem is to find an assignment of nodes to possibly multiple rings, and to determine what portion of demand traffic between node pairs spanned by each ring should be allocated to that ring. The constraints require that the demand traffic between each node pair should be satisfiable given the ring capacities, and that no more than a specified maximum number of nodes should be assigned to each ring. The objective function is to minimize the total number of node-to-ring assignments, and hence, the capital investment in add-drop multiplexer equipments. We formulate the problem as a mixed-integer programming model, and propose several alternative modeling techniques designed to improve the mathematical representation of this problem. We then develop various classes of valid inequalities for the problem along with suitable separation procedures for tightening the representation of the model, and accordingly, prescribe an algorithmic approach that coordinates tailored routines with a commercial solver (CPLEX). We also propose a heuristic procedure which enhances the solvability of the problem and provides bounds within 5–13% of the optimal solution. Promising computational results are presented that exhibit the viability of the overall approach and that lend insights into various modeling and algorithmic constructs.

In this paper, we deal with a network design problem arising from the deployment of synchronous optical networks (SONET), a standard of transmission using optical fiber technology. The problem is to find an optimal clustering of traffic demands in the network such that the total number of node assignments (and, hence, add—drop multiplexer equipment requirements) is minimized, while satisfying the ring capacity and node cardinality constraints. This problem can be conceptualized as an edge-capacitated graph partitioning problem with node cardinality constraints. We formulate the problem as a mixed-integer programming model and develop a new branch-and-cut algorithm along with preprocessing routines for optimally solving the problem. We also prescribe an effective heuristic procedure. Promising computational results are obtained using the proposed method. © 2000 John Wiley & Sons, Inc.

In this paper, we examine complexity issues, models, and algorithms for the problem of finding a shortest pair of disjoint paths between two nodes of a network such that the total travel delay is minimized, given that the individual arc delays are time-dependent. Such disjoint paths address the issue of network vulnerability by prescribing alternate routes for traffic flows. Applications include the dispatching of duplicate packets of data to improve the reliability in communication networks and the diverting of traffic during congestion to reduce the chances of bottlenecks in transportation networks, in the presence of time-dependent variations in travel delays in the network. We prove that this problem, and many variations of it, are NP-hard and we develop a 0–1 linear programming model that can be used to solve this problem. This model can accommodate various degrees of disjointedness of the pair of paths, from complete to partial with respect to specific arcs. We also present some computational results obtained by solving the above models using CPLEX-MIP. © 1998 John Wiley & Sons, Inc. Networks 31: 259–272, 1998

This paper is concerned with the mathematical modeling and analysis of a radio communication system design problem that seeks an optimal location of a single transmitter, or that of multiple transmitters, in order to serve a specified distribution of receivers. The problem is modeled by discretizing the radio coverage region into a grid of receiver locations and by specifying a function that estimates the path-loss or signal attenuation for each receiver location, given a particular location for a transmitter that communicates with it. The resulting model is a nonlinear programming problem having an implicitly defined objective function of minimizing a measure of weighted path-losses. Specializations of three nonlinear optimization algorithms, namely, the Hooke and Jeeves' method, the quasi-Newton, and conjugate gradient search procedures are investigated for solving this problem. The technique described here is intended to interact with various propagation prediction models and may be used in a CAD system for radio communication system design.

A family of facets for the GUB (Generalized Upper Bound) constrained knapsack polytope that are obtainable through a lifting procedure is characterized. The sequential lifting procedure developed herein computes lifted coefficients of the variables in each GUB set simultaneously, in contrast with the usual sequential lifting procedure that lifts only one variable at a time. Moreover; this sequential lifting procedure can be implemented in polynomial time of complexity $O( nm )$, where n is the number of variables and $m( \leq n )$ is the number of GUB sets. In addition, a characterization of the facets obtainable through a simultaneous lifting procedure is derived. This characterization enables us to deduce lower and upper bounds on the lifted coefficients. In particular, for the case of the ordinary knapsack polytope, a known lower bound on the coefficients of lifted facets derived from minimal covers was further tightened.

Abstract This article is concerned with the problem of locating p capacitated facilities on a chain graph and simultaneously determining the allocation of their supplies in order to satisfy a continuum of demand. The demand is characterized by some weighted probability density functions defined on the chain graph. The objective is to minimize the total (expected) trnasportation cost. This location‐allocation problem is also referred to as the capacitated p‐median problem on a chain graph. Two unbalanced cases of this problem are considered, namely, the overcapacitated case when total supply exceeds total demand and the deficit capacity case when total supply is less than total demand. Both these problems are nonconvex and are shown to be NP‐hard even if the demand density function is piecewise uniform and positive. We provide a first‐order characterization of optimality for these two problems and prescribe an enumerative algorithm based on a partitioning of the dual space in order to optimally solve these problems. An extension of these algorithms for solving the unbalanced, capacitated 2‐median problem on a tree graph is also given.

In this paper a reformulation technique is presented that takes a given linear zero-one programming problem, converts it into a zero-one polynomial programming problem, and then relinearizes it into an extended linear program. It is shown that the strength of the resulting reformulation depends on the degree of the terms used to produce the polynomial program at the intermediate step of this method. In fact, as this degree varies from one up to the number of variables in the problem, a hierarchy of sharper representations is obtained with the final relaxation representing the convex hull of feasible solutions. The reformulation technique readily extends to produce a similar hierarchy of linear relaxations for zero-one polynomial programming problems. A characterization of the convex hull in the original variable space is also available through a projection process. The structure of this convex hull characterization (or its other relaxations) can be exploited to generate strong or facetial valid inequalities through appropriate surrogates in a computational framework. The surrogation process can also be used to study various classes of facets for different combinatorial optimization problems. Some examples are given to illustrate this point.

Abstract Given an extreme point of an assignment polytope of size m, there exist 2m−1 mm−2 alternative basis representations according to the choice of the m ‐ 1 degenerate basic variables. This note establishes the basis structure which admits the maximum degenerate pivots and that which admits the minimum degenerate pivots. It is shown that the upper bound is achieved if and only if the basis is a chain graph and that the lower bound is achieved if the degenerate basic arcs all originate at some facility or all terminate at some location.