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.

Vanishing of Ext and Tor over complete intersections

Let (R,m) be a local complete intersection, that is, a local ring whose m-adic completion is the quotient of a complete regular local ring by a regular sequence. Let M and N be finitely generated R-modules. This dissertation concerns the vanishing of Tor(M, N) and Ext(M, N). In this context, M satisfies Serre's condition (S_{n}) if and only if M is an nth syzygy. The complexity of M is the least nonnegative integer r such that the nth Betti number of M is bounded by a polynomial of degree r-1 for all sufficiently large n. We use this notion of Serre's condition and complexity to study the vanishing of Tor_{i}(M, N). In particular, building on results of C. Huneke, D. Jorgensen and R. Wiegand [32], and H. Dao [21], we obtain new results showing that good depth properties on the R-modules M, N and MtensorN force the vanishing of Tor_{i}(M, N) for all i>0. We give examples showing that our results are sharp. We also show that if R is a one-dimensional domain and M and MtensorHom(M,R) are torsion-free, then M is free if and only if M has complexity at most one. If R is a hypersurface and Ext^{i}(M, N) has finite length for all i>>0, then the Herbrand difference [18] is defined as length(Ext^{2n}(M, N))-(Ext^{2n-1}(M, N)) for some (equivalently, every) sufficiently large integer n. In joint work with Hailong Dao, we generalize and study the Herbrand difference. Using the Grothendieck group of finitely generated R-modules, we also examined the number of consecutive vanishing of Ext^{i}(M, N) needed to ensure that Ext^{i}(M, N) = 0 for all i>>0. Our results recover and improve on most of the known bounds in the literature, especially when R has dimension two.

SimSight: A Virtual Machine Based Dynamic Call Graph Generator

One problem with using component-based software development approach is that once software modules are reused over generations of products, they form legacy structures that can be challenging to understand, making validating these systems difficult. Therefore, tools and methodologies that enable engineers to see interactions of these software modules will enhance their ability to make these software systems more dependable. To address this need, we propose SimSight, a framework to capture dynamic call graphs in Simics, a widely adopted commercial full-system simulator. Simics is a software system that simulates complete computer systems. Thus, it performs nearly identical tasks to a real system but at a much lower speed while providing greater execution observability. We have implemented SimSight to generate dynamic call graphs of statically and dynamically linked functions in x86/Linux environment. A case study illustrates how we can use SimSight to identify sources of software errors. We then evaluate its performance using 12 integer programs from SPEC CPU2006 benchmark suite.

Selection of Switching Sites in All-Optical Nework Topology Design

In this paper, we consider the problem of topology design for optical networks. We investigate the problem of selecting switching sites to minimize total cost of the optical network. The cost of an optical network can be expressed as a sum of three main factors: the site cost, the link cost, and the switch cost. To the best of our knowledge, this problem has not been studied in its general form as investigated in this paper. We present a mixed integer quadratic programming (MIQP) formulation of the problem to find the optimal value of the total network cost. We also present an efficient heuristic to approximate the solution in polynomial time. The experimental results show good performance of the heuristic. The value of the total network cost computed by the heuristic varies within 2% to 21% of its optimal value in the experiments with 10 nodes. The total network cost computed by the heuristic for 51% of the experiments with 10 node network topologies varies within 8% of its optimal value. We also discuss the insight gained from our experiments.

Um Modelo de otimização inteira mista na programação de produção de mangueiras hidráulicas

This work deals with a problem of mixed integer optimization model applied to production planning of a real world factory that aims for hydraulic hose production. To optimize production planning, a mathematic model of MILP Mixed Integer Linear Programming, so that, along with the Analytic Hierarchy process method, would be possible to create a hierarchical structure of the most import criteria for production planning, thus finding through a solving software the optimum hose attribution to its respective machine. The hybrid modeling of Analytic Hierarchy Process along with Linear Programming is the focus of this work. The results show that using this method we could unite factory reality and quantitative analysis and had success on improving performance of production planning efficiency regarding product delivery and optimization of the production flow

One-dimensional point interaction with Griffiths' boundary conditions

Griffiths proposed a pair of boundary conditions that define a point interaction in one dimensional quantum mechanics. The conditions involve the nth derivative of the wave function where n is a non-negative integer. We re-examine the interaction so defined and explicitly confirm that it is self-adjoint for any even value of n and for n = 1. The interaction is not self-adjoint for odd n > 1. We then propose a similar but different pair of boundary conditions with the nth derivative of the wave function such that the ensuing point interaction is self-adjoint for any value of n.

Integrated pulp and paper mill planning and scheduling

This article describes a real-world production planning and scheduling problem occurring at an integrated pulp and paper mill (P&P) which manufactures paper for cardboard out of produced pulp. During the cooking of wood chips in the digester, two by-products are produced: the pulp itself (virgin fibers) and the waste stream known as black liquor. The former is then mixed with recycled fibers and processed in a paper machine. Here, due to significant sequence-dependent setups in paper type changeovers, sizing and sequencing of lots have to be made simultaneously in order to efficiently use capacity. The latter is converted into electrical energy using a set of evaporators, recovery boilers and counter-pressure turbines. The planning challenge is then to synchronize the material flow as it moves through the pulp and paper mills, and energy plant, maximizing customer demand (as backlogging is allowed), and minimizing operation costs. Due to the intensive capital feature of P&P, the output of the digester must be maximized. As the production bottleneck is not fixed, to tackle this problem we propose a new model that integrates the critical production units associated to the pulp and paper mills, and energy plant for the first time. Simple stochastic mixed integer programming based local search heuristics are developed to obtain good feasible solutions for the problem. The benefits of integrating the three stages are discussed. The proposed approaches are tested on real-world data. Our work may help P&P companies to increase their competitiveness and reactiveness in dealing with demand pattern oscillations. (C) 2012 Elsevier Ltd. All rights reserved.

Asynchronous teams for joint lot-sizing and scheduling problem in flow shops

The integrated production scheduling and lot-sizing problem in a flow shop environment consists of establishing production lot sizes and allocating machines to process them within a planning horizon in a production line with machines arranged in series. The problem considers that demands must be met without backlogging, the capacity of the machines must be respected, and machine setups are sequence-dependent and preserved between periods of the planning horizon. The objective is to determine a production schedule to minimise the setup, production and inventory costs. A mathematical model from the literature is presented, as well as procedures for obtaining feasible solutions. However, some of the procedures have difficulty in obtaining feasible solutions for large-sized problem instances. In addition, we address the problem using different versions of the Asynchronous Team (A-Team) approach. The procedures were compared with literature heuristics based on Mixed Integer Programming. The proposed A-Team procedures outperformed the literature heuristics, especially for large instances. The developed methodologies and the results obtained are presented.

Quantum oscillations of spin polarization in a GaAs/AlGaAs double quantum well

5 We employ the circular-polarization-resolved magnetophotoluminescence technique to probe the spin character of electron and hole states in a GaAs/AlGaAs strongly coupled double-quantum-well system. The photoluminescence (PL) intensities of the lines associated with symmetric and antisymmetric electron states present clear out-of-phase oscillations between integer values of the filling factor. and are caused by magnetic-field-induced changes in the population of occupied Landau levels near to the Fermi level of the system. Moreover, the degree of circular polarization of these emissions also exhibits the oscillatory behavior with increasing magnetic field. Both quantum oscillations observed in the PL intensities and in the degree of polarizations may be understood in terms of a simple single-particle approach model. The k . p method was used to calculate the photoluminescence peak energies and the degree of circular polarizations in the double-quantum-well structure as a function of the magnetic field. These calculations prove that the character of valence band states plays an important role in the determination of the degree of circular polarization and, thus, resulting in a magnetic-field-induced change of the polarization sign.

Three time-based scale formulations for the two-stage lot sizing and scheduling in process industries

In this paper, we propose three novel mathematical models for the two-stage lot-sizing and scheduling problems present in many process industries. The problem shares a continuous or quasi-continuous production feature upstream and a discrete manufacturing feature downstream, which must be synchronized. Different time-based scale representations are discussed. The first formulation encompasses a discrete-time representation. The second one is a hybrid continuous-discrete model. The last formulation is based on a continuous-time model representation. Computational tests with state-of-the-art MIP solver show that the discrete-time representation provides better feasible solutions in short running time. On the other hand, the hybrid model achieves better solutions for longer computational times and was able to prove optimality more often. The continuous-type model is the most flexible of the three for incorporating additional operational requirements, at a cost of having the worst computational performance. Journal of the Operational Research Society (2012) 63, 1613-1630. doi:10.1057/jors.2011.159 published online 7 March 2012

Symmetry insights for design of supercomputer network topologies: roots and weights lattices

We present a family of networks whose local interconnection topologies are generated by the root vectors of a semi-simple complex Lie algebra. Cartan classification theorem of those algebras ensures those families of interconnection topologies to be exhaustive. The global arrangement of the network is defined in terms of integer or half-integer weight lattices. The mesh or torus topologies that network millions of processing cores, such as those in the IBM BlueGene series, are the simplest member of that category. The symmetries of the root systems of an algebra, manifested by their Weyl group, lends great convenience for the design and analysis of hardware architecture, algorithms and programs.

A spatial stochastic model for rumor transmission

We consider an interacting particle system representing the spread of a rumor by agents on the d-dimensional integer lattice. Each agent may be in any of the three states belonging to the set {0,1,2}. Here 0 stands for ignorants, 1 for spreaders and 2 for stiflers. A spreader tells the rumor to any of its (nearest) ignorant neighbors at rate lambda. At rate alpha a spreader becomes a stifler due to the action of other (nearest neighbor) spreaders. Finally, spreaders and stiflers forget the rumor at rate one. We study sufficient conditions under which the rumor either becomes extinct or survives with positive probability.

Magneto-optical probe of quantum Hall states in a wide parabolic well modulated by random potential

Polarized photoluminescence from weakly coupled random multiple well quasi-three-dimensional electron system is studied in the regime of the integer quantum Hall effect. Two quantum Hall ferromagnetic ground states assigned to the uncorrelated miniband quantum Hall state and to the spontaneous interwell phase coherent dimer quantum Hall state are observed. Photoluminescence associated with these states exhibits features caused by finite-size skyrmions: dramatic reduction of the electron spin polarization when the magnetic field is increased past the filling factor nu = 1. The effective skyrmion size is larger than in two-dimensional electron systems.

Multibrane solutions in cubic superstring field theory

Using the elements of the so-called KBc gamma subalgebra, we study a class of analytic solutions depending on a single function F(K) in the modified cubic superstring field theory. We compute the energy associated to these solutions and show that the result can be expressed in terms of a contour integral. For a particular choice of the function F(K), we show that the energy is given by integer multiples of a single D-brane tension.