Column Generation Algorithms for Nonlinear Optimization II: Numerical Investigations

García et al. present a class of column generation (CG) algorithms for nonlinear programs. Its main motivation from a theoretical viewpoint is that under some circumstances, finite convergence can be achieved, in much the same way as for the classic simplicial decomposition method; the main practical motivation is that within the class there are certain nonlinear column generation problems that can accelerate the convergence of a solution approach which generates a sequence of feasible points. This algorithm can, for example, accelerate simplicial decomposition schemes by making the subproblems nonlinear. This paper complements the theoretical study on the asymptotic and finite convergence of these methods given in [1] with an experimental study focused on their computational efficiency. Three types of numerical experiments are conducted. The first group of test problems has been designed to study the parameters involved in these methods. The second group has been designed to investigate the role and the computation of the prolongation of the generated columns to the relative boundary. The last one has been designed to carry out a more complete investigation of the difference in computational efficiency between linear and nonlinear column generation approaches. In order to carry out this investigation, we consider two types of test problems: the first one is the nonlinear, capacitated single-commodity network flow problem of which several large-scale instances with varied degrees of nonlinearity and total capacity are constructed and investigated, and the second one is a combined traffic assignment model

Remarks on methods for the computation of boundary-element integrals by co-ordinate transformation

It is well known that the evaluation of the influence matrices in the boundary-element method requires the computation of singular integrals. Quadrature formulae exist which are especially tailored to the specific nature of the singularity, i.e. log(*- x0)9 Ijx- JC0), etc. Clearly the nodes and weights of these formulae vary with the location Xo of the singular point. A drawback of this approach is that a given problem usually includes different types of singularities, and therefore a general-purpose code would have to include many alternative formulae to cater for all possible cases. Recently, several authors1"3 have suggested a type independent alternative technique based on the combination of standard Gaussian rules with non-linear co-ordinate transformations. The transformation approach is particularly appealing in connection with the p.adaptive version, where the location of the collocation points varies at each step of the refinement process. The purpose of this paper is to analyse the technique in eference 3. We show that this technique is asymptotically correct as the number of Gauss points increases. However, the method possesses a 'hidden' source of error that is analysed and can easily be removed.

PIC computation of electron current collection to a moving bare tether in the mesothermal condition

In tethered satellite technology, it is important to estimate how many electrons a spacecraft can collect from its ambient plasma by a bare electrodynamic tether. The analysis is however very difficult because of the small but significant Geo-magnetic field and the spacecraft’s relative motion to both ions and electrons. The object of our work is the development of a numerical method, for this purpose. Particle-In-Cell (PIC) method, for the calculation of electron current to a positive bare tether moving at orbital velocity in the ionosphere, i.e. in a flowing magnetized plasma under Maxwellian collisionless conditions. In a PIC code, a number of particles are distributed in phase space and the computational domain has a grid on which Poisson equation is solved for field quantities. The code uses the quasi-neutrality condition to solve for the local potential at points in the plasma which coincide with the computational outside boundary. The quasi-neutrality condition imposes ne - ni on the boundary. The Poisson equation is solved in such a way that the presheath region can be captured in the computation. Results show that the collected current is higher than the Orbital Motion Limit (OML) theory. The OML current is the upper limit of current collection under steady collisionless unmagnetized conditions. In this work, we focus on the flowing effects of plasma as a possible cause of the current enhancement. A deficit electron density due to the flowing effects has been worked and removed by introducing adiabatic electron trapping into our model.

Numerical model for the study of hydrodynamics on bays and estuaries

A nonlinear implicit finite element model for the solution of two-dimensional (2-D) shallow water equations, based on a Galerkin formulation of the 2-D estuaries hydrodynamic equations, has been developed. Spatial discretization has been achieved by the use of isoparametric, Lagrangian elements. To obtain the different element matrices, Simpson numerical integration has been applied. For time integration of the model, several schemes in finite differences have been used: the Cranck-Nicholson iterative method supplies a superior accuracy and allows us to work with the greatest time step Δt; however, central differences time integration produces a greater velocity of calculation. The model has been tested with different examples to check its accuracy and advantages in relation to computation and handling of matrices. Finally, an application to the Bay of Santander is also presented.

Numerical modeling of electromagnetic coupling phenomena in the vicinities of overhead power transmission lines.

Electromagnetic coupling phenomena between overhead power transmission lines and other nearby structures are inevitable, especially in densely populated areas. The undesired effects resulting from this proximity are manifold and range from the establishment of hazardous potentials to the outbreak of alternate current corrosion phenomena. The study of this class of problems is necessary for ensuring security in the vicinities of the interaction zone and also to preserve the integrity of the equipment and of the devices there present. However, the complete modeling of this type of application requires the three- -dimensional representation of the region of interest and needs specific numerical methods for field computation. In this work, the modeling of problems arising from the flow of electrical currents in the ground (the so-called conductive coupling) will be addressed with the finite element method. Those resulting from the time variation of the electromagnetic fields (the so-called inductive coupling) will be considered as well, and they will be treated with the generalized PEEC (Partial Element Equivalent Circuit) method. More specifically, a special boundary condition on the electric potential is proposed for truncating the computational domain in the finite element analysis of conductive coupling problems, and a complete PEEC formulation for modeling inductive coupling problems is presented. Test configurations of increasing complexities are considered for validating the foregoing approaches. These works aim to provide a contribution to the modeling of this class of problems, which tend to become common with the expansion of power grids.

Exact Numerical Processing

Paper submitted to Euromicro Symposium on Digital Systems Design (DSD), Belek-Antalya, Turkey, 2003.

3D numerical modelling of acoustic horns using the method of fundamental solutions

In the present work, a three-dimensional (3D) formulation based on the method of fundamental solutions (MFS) is applied to the study of acoustic horns. The implemented model follows and extends previous works that only considered two-dimensional and axisymmetric horn configurations. The more realistic case of 3D acoustic horns with symmetry regarding two orthogonal planes is addressed. The use of the domain decomposition technique with two interconnected sub-regions along a continuity boundary is proposed, allowing for the computation of the sound pressure generated by an acoustic horn installed on a rigid screen. In order to reduce the model discretization requirements for these cases, Green’s functions derived with the image source methodology are adopted, automatically accounting for the presence of symmetry conditions. A strategy for the calculation of an optimal position of the virtual sources used by the MFS to define the solution is also used, leading to improved reliability and flexibility of the proposed method. The responses obtained by the developed model are compared to reference solutions, computed by well-established models based on the boundary element method. Additionally, numerically calculated acoustic parameters, such as directivity and beamwidth, are compared with those evaluated experimentally.

Numerical quadrature over a rectangular domain in two or more dimensions /

"This work was supported in part by the Office of Naval Research under Contract Nonr-1834(27)."

The use of Illiac IV to solve numerical fluid dynamics problems : a status report /

Includes bibliographies (p. 50).

Evaluation of numerical viscosity effects in transonic flow calculations /

Includes bibliographies (p. 21).

Methods of mathematical analysis and computation.

Mode of access: Internet.

Using weak nonlinearity under decoherence for macroscopic entanglement generation and quantum computation

Recently, there have been several suggestions that weak Kerr nonlinearity can be used for generation of macroscopic superpositions and entanglement and for linear optics quantum computation. However, it is not immediately clear that this approach can overcome decoherence effects. Our numerical study shows that nonlinearity of weak strength could be useful for macroscopic entanglement generation and quantum gate operations in the presence of decoherence. We suggest specific values for real experiments based on our analysis. Our discussion shows that the generation of macroscopic entanglement using this approach is within the reach of current technology.

Noise thresholds for optical cluster-state quantum computation

In this paper we do a detailed numerical investigation of the fault-tolerant threshold for optical cluster-state quantum computation. Our noise model allows both photon loss and depolarizing noise, as a general proxy for all types of local noise other than photon loss noise. We obtain a threshold region of allowed pairs of values for the two types of noise. Roughly speaking, our results show that scalable optical quantum computing is possible in the combined presence of both noise types, provided that the loss probability is less than 3 X 10(-3) and the depolarization probability is less than 10(-4). Our fault-tolerant protocol involves a number of innovations, including a method for syndrome extraction known as telecorrection, whereby repeated syndrome measurements are guaranteed to agree. This paper is an extended version of Dawson.

Numerical method for determination of the NMR frequency of the single-qubit operation in a silicon-based solid-state quantum computer

A numerical method is introduced to determine the nuclear magnetic resonance frequency of a donor (P-31) doped inside a silicon substrate under the influence of an applied electric field. This phosphorus donor has been suggested for operation as a qubit for the realization of a solid-state scalable quantum computer. The operation of the qubit is achieved by a combination of the rotation of the phosphorus nuclear spin through a globally applied magnetic field and the selection of the phosphorus nucleus through a locally applied electric field. To realize the selection function, it is required to know the relationship between the applied electric field and the change of the nuclear magnetic resonance frequency of phosphorus. In this study, based on the wave functions obtained by the effective-mass theory, we introduce an empirical correction factor to the wave functions at the donor nucleus. Using the corrected wave functions, we formulate a first-order perturbation theory for the perturbed system under the influence of an electric field. In order to calculate the potential distributions inside the silicon and the silicon dioxide layers due to the applied electric field, we use the multilayered Green's functions and solve an integral equation by the moment method. This enables us to consider more realistic, arbitrary shape, and three-dimensional qubit structures. With the calculation of the potential distributions, we have investigated the effects of the thicknesses of silicon and silicon dioxide layers, the relative position of the donor, and the applied electric field on the nuclear magnetic resonance frequency of the donor.

Generalization by Computation Through Memory

Usually, generalization is considered as a function of learning from a set of examples. In present work on the basis of recent neural network assembly memory model (NNAMM), a biologically plausible 'grandmother' model for vision, where each separate memory unit itself can generalize, has been proposed. For such a generalization by computation through memory, analytical formulae and numerical procedure are found to calculate exactly the perfectly learned memory unit's generalization ability. The model's memory has complex hierarchical structure, can be learned from one example by a one-step process, and may be considered as a semi-representational one. A simple binary neural network for bell-shaped tuning is described.