Applications of Linear Programming to Coding Theory

Maximum-likelihood decoding is often the optimal decoding rule one can use, but it is very costly to implement in a general setting. Much effort has therefore been dedicated to find efficient decoding algorithms that either achieve or approximate the error-correcting performance of the maximum-likelihood decoder. This dissertation examines two approaches to this problem. In 2003 Feldman and his collaborators defined the linear programming decoder, which operates by solving a linear programming relaxation of the maximum-likelihood decoding problem. As with many modern decoding algorithms, is possible for the linear programming decoder to output vectors that do not correspond to codewords; such vectors are known as pseudocodewords. In this work, we completely classify the set of linear programming pseudocodewords for the family of cycle codes. For the case of the binary symmetric channel, another approximation of maximum-likelihood decoding was introduced by Omura in 1972. This decoder employs an iterative algorithm whose behavior closely mimics that of the simplex algorithm. We generalize Omura's decoder to operate on any binary-input memoryless channel, thus obtaining a soft-decision decoding algorithm. Further, we prove that the probability of the generalized algorithm returning the maximum-likelihood codeword approaches 1 as the number of iterations goes to infinity.

Estimating the extent of spatial association of Mycobacterium bovis infection in badgers in Ireland

Mycobacterium bovis infects the wildlife species badgers Meles meles who are linked with the spread of the associated disease tuberculosis (TB) in cattle. Control of livestock infections depends in part on the spatial and social structure of the wildlife host. Here we describe spatial association of M. bovis infection in a badger population using data from the first year of the Four Area Project in Ireland. Using second-order intensity functions, we show there is strong evidence of clustering of TB cases in each the four areas, i.e. a global tendency for infected cases to occur near other infected cases. Using estimated intensity functions, we identify locations where particular strains of TB cluster. Generalized linear geostatistical models are used to assess the practical range at which spatial correlation occurs and is found to exceed 6 in all areas. The study is of relevance concerning the scale of localized badger culling in the control of the disease in cattle.

Survivable Lightpath Provisioning in WDM Mesh Networks Under Shared Path Protection and Signal Quality Constraints

This paper addresses the problem of survivable lightpath provisioning in wavelength-division-multiplexing (WDM) mesh networks, taking into consideration optical-layer protection and some realistic optical signal quality constraints. The investigated networks use sparsely placed optical–electrical–optical (O/E/O) modules for regeneration and wavelength conversion. Given a fixed network topology with a number of sparsely placed O/E/O modules and a set of connection requests, a pair of link-disjoint lightpaths is established for each connection. Due to physical impairments and wavelength continuity, both the working and protection lightpaths need to be regenerated at some intermediate nodes to overcome signal quality degradation and wavelength contention. In the present paper, resource-efficient provisioning solutions are achieved with the objective of maximizing resource sharing. The authors propose a resource-sharing scheme that supports three kinds of resource-sharing scenarios, including a conventional wavelength-link sharing scenario, which shares wavelength links between protection lightpaths, and two new scenarios, which share O/E/O modules between protection lightpaths and between working and protection lightpaths. An integer linear programming (ILP)-based solution approach is used to find optimal solutions. The authors also propose a local optimization heuristic approach and a tabu search heuristic approach to solve this problem for real-world, large mesh networks. Numerical results show that our solution approaches work well under a variety of network settings and achieves a high level of resource-sharing rates (over 60% for O/E/O modules and over 30% for wavelength links), which translate into great savings in network costs.

Dynamic Traffic Grooming Algorithms for Reconfigurable SONET Over WDM Networks

The emergence of wavelength-division multiplexing (WDM) technology provides the capability for increasing the bandwidth of synchronous optical network (SONET) rings by grooming low-speed traffic streams onto different high-speed wavelength channels. Since the cost of SONET add–drop multiplexers (SADM) at each node dominates the total cost of these networks, how to assign the wavelength, groom the traffic, and bypass the traffic through the intermediate nodes has received a lot of attention from researchers recently. Moreover, the traffic pattern of the optical network changes from time to time. How to develop dynamic reconfiguration algorithms for traffic grooming is an important issue. In this paper, two cases (best fit and full fit) for handling reconfigurable SONET over WDM networks are proposed. For each approach, an integer linear programming model and heuristic algorithms (TS-1 and TS-2, based on the tabu search method) are given. The results demonstrate that the TS-1 algorithm can yield better solutions but has a greater running time than the greedy algorithm for the best fit case. For the full fit case, the tabu search heuristic yields competitive results compared with an earlier simulated annealing based method and it is more stable for the dynamic case.

Survivable Traffic Grooming With Path Protection at the Connection Level in WDM Mesh Networks

Survivable traffic grooming (STG) is a promising approach to provide reliable and resource-efficient multigranularity connection services in wavelength-division-multiplexing (WDM) optical networks. In this paper, we study the STG problem in WDM mesh optical networks employing path protection at the connection level. Both dedicated-protection and shared-protection schemes are considered. Given network resources, the objective of the STG problem is to maximize network throughput. To enable survivability under various kinds of single failures, such as fiber cut and duct cut, we consider the general shared-risklink- group (SRLG) diverse routing constraints. We first resort to the integer-linear-programming (ILP) approach to obtain optimal solutions. To address its high computational complexity, we then propose three efficient heuristics, namely separated survivable grooming algorithm (SSGA), integrated survivable grooming algorithm (ISGA), and tabu-search survivable grooming algorithm (TSGA). While SSGA and ISGA correspond to an overlay network model and a peer network model, respectively, TSGA further improves the grooming results from SSGA and ISGA by incorporating the effective tabu-search (TS) method. Numerical results show that the heuristics achieve comparable solutions to the ILP approach, which uses significantly longer running times than the heuristics.

Survivable Virtual Topology Routing under Shared Risk Link Groups in WDM Networks

Network survivability is one of the most important issues in the design of optical WDM networks. In this work we study the problem of survivable routing of a virtual topology on a physical topology with Shared Risk Link Groups (SRLG). The survivable virtual topology routing problem against single-link failures in the physical topology is proved to be NP-complete in [1]. We prove that survivable virtual topology routing problem against SRLG/node failures is also NP-complete. We present an improved integer linear programming (ILP) formulation (in comparison to [1]) for computing the survivable routing under SRLG/node failures. Using an ILP solver, we computed the survivable virtual topology routing against link and SRLG failures for small and medium sized networks efficiently. As even our improved ILP formulation becomes intractable for large networks, we present a congestion-based heuristic and a tabu search heuristic (which uses the congestion-based heuristic solution as the initial solution) for computing survivable routing of a virtual topology. Our experimental results show that tabu search heuristic coupled with the congestion based heuristic (used as initial solution) provides fast and near-optimal solutions.

Survivable Traffic Grooming with Path Protection at the Connection Level in WDM Mesh Networks

Survivable traffic grooming (STG) is a promising approach to provide reliable and resource-efficient multigranularity connection services in wavelength division multiplexing (WDM) optical networks. In this paper, we study the STG problem in WDM mesh optical networks employing path protection at the connection level. Both dedicated protection and shared protection schemes are considered. Given the network resources, the objective of the STG problem is to maximize network throughput. To enable survivability under various kinds of single failures such as fiber cut and duct cut, we consider the general shared risk link group (SRLG) diverse routing constraints. We first resort to the integer linear programming (ILP) approach to obtain optimal solutions. To address its high computational complexity, we then propose three efficient heuristics, namely separated survivable grooming algorithm (SSGA), integrated survivable grooming algorithm (ISGA) and tabu search survivable grooming algorithm (TSGA). While SSGA and ISGA correspond to an overlay network model and a peer network model respectively, TSGA further improves the grooming results from SSGA and ISGA by incorporating the effective tabu search method. Numerical results show that the heuristics achieve comparable solutions to the ILP approach, which uses significantly longer running times than the heuristics.

INVESTIGATION INTO CURRENT EFFICIENCY FOR PULSE ELECTROCHEMICAL MACHINING OF NICKEL ALLOY

INVESTIGATION INTO CURRENT EFFICIENCY FOR PULSE ELECTROCHEMICAL MACHINING OF NICKEL ALLOY Yu Zhang, M.S. University of Nebraska, 2010 Adviser: Kamlakar P. Rajurkar Electrochemical machining (ECM) is a nontraditional manufacturing process that can machine difficult-to-cut materials. In ECM, material is removed by controlled electrochemical dissolution of an anodic workpiece in an electrochemical cell. ECM has extensive applications in automotive, petroleum, aerospace, textile, medical, and electronics industries. Improving current efficiency is a challenging task for any electro-physical or electrochemical machining processes. The current efficiency is defined as the ratio of the observed amount of metal dissolved to the theoretical amount predicted from Faraday’s law, for the same specified conditions of electrochemical equivalent, current, etc [1]. In macro ECM, electrolyte conductivity greatly influences the current efficiency of the process. Since there is a certain limit to enhance the conductivity of the electrolyte, a process innovation is needed for further improvement in current efficiency in ECM. Pulse electrochemical machining (PECM) is one such approach in which the electrolyte conductivity is improved by electrolyte flushing in pulse off-time. The aim of this research is to study the influence of major factors on current efficiency in a pulse electrochemical machining process in macro scale and to develop a linear regression model for predicting current efficiency of the process. An in-house designed electrochemical cell was used for machining nickel alloy (ASTM B435) by PECM. The effects of current density, type of electrolyte, and electrolyte flow rate, on current efficiency under different experimental conditions were studied. Results indicated that current efficiency is dependent on electrolyte, electrolyte flow rate, and current density. Linear regression models of current efficiency were compared with twenty new data points graphically and quantitatively. Models developed were close enough to the actual results to be reliable. In addition, an attempt has been made in this work to consider those factors in PECM that have not been investigated in earlier works. This was done by simulating the process by using COMSOL software. However, it was found that the results from this attempt were not substantially different from the earlier reported studies.