Competitive Memetic Algorithms for Arc Routing Problems

The Capacitated Arc Routing Problem or CARP arises in applications like waste collection or winter gritting. Metaheuristics are tools of choice for solving large instances of this NP-hard problem. The paper presents basic components that can be combined into powerful memetic algorithms (MAs) for solving an extended version of the CARP (ECARP). The best resulting MA outperforms all known heuristics on three sets of benchmark files containing in total 81 instances with up to 140 nodes and 190 edges. In particular, one open instance is broken by reaching a tight lower bound designed by Belenguer and Benavent, 26 best-known solutions are improved, and all other best-known solutions are retrieved.     

Multilevel Iterative Algorithms for Accelerating Spectral Approximations of Integral Equations

In this paper, spectral collocation and Nyström methods for integral equations are discussed. Some multilevel correction schemes are presented for infinitely accelerating the covergence even if the exact solution is not so smooth.     

On-line k-Truck Problem and Its Competitive Algorithms

In this paper, based on the Position Maintaining Strategy (PMS for short), on-line scheduling of k-truck problem, which is a generalization of the famous k-server problem, is originally presented by our team. We proposed several competitive algorithms applicable under different conditions for solving the on-line k-truck problem. First, a competitive algorithm with competitive ratio 2k+1/ is given for any 1. Following that, if (c+1)/(c-1) holds, then there must exist a (2k-1)-competitive algorithm for k-truck problem, where c is the competitive ratio of the on-line algorithm about the relevant k-server problem. And then a greedy algorithm with competitive ratio 1+/, where lambda is a parameter related to the structure property of a given graph, is given. Finally, competitive algorithms with ratios 1+1/ are given for two special families of graphs.     

Convergence Estimates of Multilevel Additive and Multiplicative Algorithms for Non-symmetric and Indefinite Problems

New uniform estimates for multigrid algorithms are established for certain non-symmetric indefinite problems. In particular, we are concerned with the simple additive algorithm and multigrid (V(1,0)-cycle) algorithms given in [5]. We prove, without full elliptic regularity assumption, that these algorithms have uniform reduction per iteration, independent of the finest mesh size and number of refinement levels, provided that the coarsest mesh size is sufficiently small.     

Parallel Smoothed Aggregation Multilevel Schwarz Preconditioned Newton-Krylov Algorithms for Poisson-Boltzmann Problems

We study a multilevel Schwarz preconditioned Newton-Krylov algorithm to solve the Poisson-Boltzmann equation with applications in multi-particle colloidal simulation. The smoothed aggregation-type coarse mesh space is introduced in collaboration with the one-level Schwarz method as a composite preconditioner for accelerating the convergence of a Krylov subspace method for solving the Jacobian system at each Newton step. The important feature of the proposed solution algorithm is that the geometric mesh information needed for constructing the multilevel preconditioner is the same as the one-level Schwarz method on the fine mesh. Other components, such as the definition of the coarse mesh, all the mesh transfer operators, and the coarse mesh problem, are taken care of by the Trillinos/ML packages of the Sandia National Laboratories in the United States. After algorithmic parameter tuning, we show that the proposed smoothed aggregation multilevel Newton-Krylov-Schwarz (NKS) algorithm numerically outperforms than smoothed aggregation multigrid method and one-level version of the NKS algorithm with satisfactory parallel performances up to a few thousand cores. Besides, we investigate how the electrostatic forces between particles for the separation distance depend on the radius of spherical colloidal particles and valence ratios of cation and anion in a cubic system.     

Relaxed Quasimonotone Operators and Relaxed Quasiconvex Functions

In this paper, we introduce the class of multivalued relaxed μ quasimonotone operators and establish the existence of solutions of variational inequalities for such operators. This result is compared with a recent result of Bai et al. on densely relaxed pseudomonotone operators. A similar comparison regarding an existence result of Luc on densely pseudomonotone operators is provided. Also, we introduce a broad class of functions, called relaxed quasiconvex functions, and show that they are characterized by the relaxed μ quasimonotonicity of their subdifferentials. The results strengthen a variety of other results in the literature. This work is supported by NNSF of China (10571046) and by the GSRT of Greece (06FR-062).     

A New Method,the Fusion Fission,for the Relaxed <Emphasis Type="Italic">k</Emphasis>-way Graph Partitioning Problem,and Comparisons with Some Multilevel Algorithms

In this paper a new graph partitioning problem is introduced, the relaxed k-way graph partitioning problem. It is close to the k-way, also called multi-way, graph partitioning problem, but with relaxed imbalance constraints. This problem arises in the air traffic control area. A new graph partitioning method is presented, the Fusion Fission, which can be used to resolve the relaxed k-way graph partitioning problem. The Fusion Fission method is compared to classical Multilevel packages and with a Simulated Annealing algorithm. The Fusion Fission algorithm and the Simulated Annealing algorithm, both require a longer computation time than the Multilevel algorithms, but they also find better partitions. However, the Fusion Fission algorithm partitions the graph with a smaller imbalance and a smaller cut than Simulated Annealing does.     

General Strongly Nonlinear Quasivariational Inequalities with Relaxed Lipschitz and Relaxed Monotone Mappings

In this paper, we introduce and study a new class of general strongly nonlinear quasivariational inequalities and construct a general iterative algorithm by using the projection method. We establish the existence of a unique solution for general strongly nonlinear quasivariational inequalities involving relaxed Lipschitz, relaxed monotone, and strongly monotone mappings; we obtain the convergence and stability of the iterative sequences generated by the algorithm. Our results extend, improve, and unify many known results due to Bose, Noor, Siddiqi-Ansari, Verma, Yao, Zeng, and others.     

Relaxed dirichlet problem for the subellipticp-laplacian

We consider a relaxed Dirichlet problem for a subelliptic p-Laplacian. We define the regular points for our problem and we prove a Wiener type criterion (in terms of the μ-capacity related to the problem) for the regularity of a point. As consequence of our result we obtain also a Wiener criterion for the regularity of boundary points. Entrata in Redazione il 30 dicembre 1998. The first Author has been partially supported by the MURST Research Project: “Non-Euclidean structures: Dirichlet forms and Fractals”.     

Relaxed and stabilized incomplete factorizations for non-self-adjoint linear systems

Two classes of incomplete factorization preconditioners are considered for nonsymmetric linear systems arising from second order finite difference discretizations of non-self-adjoint elliptic partial differential equations. Analytic and experimental results show that relaxed incomplete factorization methods exhibit numerical instabilities of the type observed with other incomplete factorizations, and the effects of instability are characterized in terms of the relaxation parameter. Several stabilized incomplete factorizations are introduced that are designed to avoid numerically unstable computations. In experiments with two-dimensional problems with variable coefficients and on nonuniform meshes, the stabilized methods are shown to be much more robust than standard incomplete factorizations.The work presented in this paper was supported by the National Science Foundation under grants DMS-8607478, CCR-8818340, and ASC-8958544, and by the U.S. Army Research Office under grant DAAL-0389-K-0016.     

Relaxed extragradient iterative methods for variational inequalities

In this paper, we suggest and analyze some new relaxed extragradient iterative methods for finding a common element of the solution set of a variational inequality, the solution set of a general system of variational inequalities and the set of fixed points of a strictly pseudo-contractive mapping defined on a real Hilbert space. Strong convergence of the proposed methods under some mild conditions is established.     

Relaxed Newton-like methods for stiff differential systems

Newton-like methods are commonly used to solve the nonlinear equations arising in the numerical solution of stiff differential equations. We show that easily calculable relaxation factors may be used to improve the convergence properties of such methods. The technique is also applicable when partitioning methods are used.     

Relaxed Multifunctions and Young Multimeasures

Young-measure type limits of multifunctions are examined. The relaxed limit via selections is a multimeasure, while the relaxation as a set-valued point function yields a Young measure on sets. The paper verifies that the two processes are equivalent in the sense that the limit multimeasure consists of all the distributions selectionable with respect to the Young measure on sets. The main tool is the characterization of selectionable distributions. An illustrative application of the equivalence result is provided.     

Relaxed energy densities for large deformations of membranes

Tension field theory can be incorporated into the ordinary theoryof finite deformations of membranes by replacing the strainenergy function W with a certain relaxed energy density W_r.If W is a convex function of the strain, W_r is the largest convexand increasing function that does not exceed W, and W_r is aconvex function of the deformation gradient. Minimum energyand minimum complementary energy theorems are proved for thetheory based on W_r.     

Relaxed Controls for Nonlinear Fractional Impulsive Evolution Equations

In this paper, we study optimal relaxed controls and relaxation of nonlinear fractional impulsive evolution equations. Firstly, existence of piecewise continuous mild solutions for the original fractional impulsive control system is presented. Secondly, fractional impulsive relaxed control system is constructed by using a regular countably additive measure and making the original control system convexified. Thirdly, optimal relaxed controls and relaxation theorems are obtained. Finally, application to initial-boundary value problem of fractional impulsive parabolic control system is considered.     

Relaxed energy densities for small deformations of membranes

The theory of plane stress for infinitesimal deformations ofelastic membranes commonly yields solutions that are unstablewith respect to out-of-plane perturbations. This can be remediedby replacing the elastic strain energy by a certain relaxedenergy density. This procedure yields tension field theory whenit is appropriate. Minimum energy and minimum complementaryenergy theorems, based on the relaxed energy density, are proved.     

Relaxed loading conditions for higher order homogenisation approaches

The present paper deals with the formulation of minimal loading conditions for the application of numerical homogenisation techniques, namely the FE² methodology. Based on the set of volume averaging rules connecting the heterogeneous micro and the homogeneous macro scale, the minimal constraints on the deformation of a micro volume are derived for a classical Cauchy continuum as well as for a micromorphic continuum theory. For both cases, numerical studies are included highlighting the main aspects of the proposed procedure within the context of small deformations. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Relaxed Steepest Descent and Cauchy-Barzilai-Borwein Method

The negative gradient direction to find local minimizers has been associated with the classical steepest descent method which behaves poorly except for very well conditioned problems. We stress out that the poor behavior of the steepest descent methods is due to the optimal Cauchy choice of steplength and not to the choice of the search direction. We discuss over and under relaxation of the optimal steplength. In fact, we study and extend recent nonmonotone choices of steplength that significantly enhance the behavior of the method. For a new particular case (Cauchy-Barzilai-Borwein method), we present a convergence analysis and encouraging numerical results to illustrate the advantages of using nonmonotone overrelaxations of the gradient method.