Wireless Local Area Networks (WLANs) are widely deployed for internet access. Multiple interfering Access Points (APs) lead to a significant increase in collisions, that reduces throughput and affects media traffic. Thus, interference mitigation among different APs becomes a crucial issue in Multi-Cell WLAN systems. One solution to this issue is to assign a different frequency channel to each AP so as to prevent neighboring cells from operating on the same channel. However, most of the existing WLANs today operate in the unlicensed 2.4GHz Industrial, Scientific and Medical (ISM) band, which suffers from lack of the available channels. Therefore, effective channel assignment to minimize the interference in Multi-Cell WLANs is necessary. In this article, we formulate the channel assignment problem as a mixed integer linear programming (MILP) problem that minimizes the worst case total interference power. The main advantage of this algorithm is that it provides a global solution and at the same time guarantees a non-overlapping channel assignment. We also propose a Lagrangian relaxation approach to transform the MILP into a low complexity linear program which can be solved efficiently in real time, even for large sized networks. Simulation results reveal that both the MILP algorithm and the Lagrangian relaxation approach provide a total interference reduction below the default setting of having all APs assigned the same channel. In addition, simulation results on cumulative density function (CDF) of the SINR at the user level prove the validity of the proposed algorithms.

In this paper we study the problem of how to identify multiple disjoint paths that have the minimum total cost OPT and satisfy a delay bound D in a graph G. This problem has lots of applications in networking such as fault-tolerant quality of service (QoS) routing and network-flow load balancing. Recently, several approximation algorithms have been developed for this problem. Here, we propose a new approximation algorithm for it by using the Lagrangian Relaxation method. We then present a simple approximation algorithm for finding multiple link-disjoint paths that satisfy the delay constraints at a reasonable total cost. If the optimal solution under delay-bound D has a cost OPT, then our algorithm can find a solution whose delay is bounded by (1+)D and the cost is no more than (1+k)OPT. The time complexity of our algorithm is much better than the previous algorithms.

This paper presents a fuzzy optimization based scheduling method for the manufacturing systems with uncertain production capacities. To address the uncertainties efficiently, the fuzzy optimization technique is used in defining the scheduling problem. Based on the symmetric approach of fuzzy optimization and Lagrangian relaxation technique, a practical fuzzy-optimization based algorithm is developed. The computational experiments based on the real factory data demonstrate that the proposed method provides robust scheduling to hedge against uncertainties.

In this paper, we consider the working VP and backup VP routing problems jointly and employ the integer programming based approach to maximize the system resource utilization and the network survivability. The VP planning problem is formulated as a nonlinear combinatorial optimization problem. The objective function minimizes the resource usage while maximizing the network survivability. By proper transformation of the objective function and applying cutting plane method, the original formulation is transformed into an integer linear programing formulation which is suitable for applying Lagrangian relaxation techniques. After Lagrangian relaxation, the problem is further decomposed into several tractable subproblems. Unlike others' work, the candidate path set does not need to be prepared in advance and the best paths are generated while solving subproblems in our approach. Heuristic algorithms based on the solving procedure of the Lagrangian relaxation are developed. Closely examining the gap between the heuristic upper bounds and the Lagrangian lower bounds reveals that the proposed algorithm can efficiently provide a nearly optimal solution for the survivable VP layout design in ATM networks.