Canary grass : variations in grain yield and other agronomically important features in response to different plant densities

p.43-55

Canary grass : variations in grain yield and other agronomically important features in response to different plant densities

p.43-55

Mesh partitioning: a multilevel balancing and refinement algorithm

Multilevel algorithms are a successful class of optimization techniques which addresses the mesh partitioning problem. They usually combine a graph contraction algorithm together with a local optimization method which refines the partition at each graph level. In this paper we present an enhancement of the technique which uses imbalance to achieve higher quality partitions. We also present a formulation of the Kernighan-Lin partition optimization algorithm which incorporates load-balancing. The resulting algorithm is tested against a different but related state-of-the-art partitioner and shown to provide improved results.

Multilevel refinement for combinatorial optimisation problems

We consider the multilevel paradigm and its potential to aid the solution of combinatorial optimisation problems. The multilevel paradigm is a simple one, which involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found (sometimes for the original problem, sometimes the coarsest) and then iteratively refined at each level. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (most notably in the form of multigrid techniques). However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial optimisation problems. In this paper we address the issue of multilevel refinement for such problems and, with the aid of examples and results in graph partitioning, graph colouring and the travelling salesman problem, make a case for its use as a metaheuristic. The results provide compelling evidence that, although the multilevel framework cannot be considered as a panacea for combinatorial problems, it can provide an extremely useful addition to the combinatorial optimisation toolkit. We also give a possible explanation for the underlying process and extract some generic guidelines for its future use on other combinatorial problems.

Multilevel refinement for the vehicle routing problem

Multilevel approaches to computational problems are pervasive across many areas of applied mathematics and scientific computing. The multilevel paradigm uses recursive coarsening to create a hierarchy of approximations to the original problem, then an initial solution is found for the coarsest problem and iteratively refined and improved at each level, coarsest to finest. The solution process is aided by the global perspective (or `global view') imparted to the optimisation by the coarsening. This paper looks at their application to the Vehicle Routing Problem.

Multilevel refinement strategies for the capacity vehicle routing problem

We discuss the application of the multilevel (ML) refinement technique to the Vehicle Routing Problem (VRP), and compare it to its single-level (SL) counterpart. Multilevel refinement recursively coarsens to create a hierarchy of approximations to the problem and refines at each level. A SL algorithm, which uses a combination of standard VRP heuristics, is developed first to solve instances of the VRP. A ML version, which extends the global view of these heuristics, is then created, using variants of the construction and improvement heuristics at each level. Finally some multilevel enhancements are developed. Experimentation is used to find suitable parameter settings and the final version is tested on two well-known VRP benchmark suites. Results comparing both SL and ML algorithms are presented.

The application of multilevel refinement to the vehicle routing problem

We discuss the application of the multilevel (ML) refinement technique to the Vehicle Routing Problem (VRP), and compare it to its single-level (SL) counterpart. Multilevel refinement recursively coarsens to create a hierarchy of approximations to the problem and refines at each level. A SL heuristic, termed the combined node-exchange composite heuristic (CNCH), is developed first to solve instances of the VRP. A ML version (the ML-CNCH) is then created, using the construction and improvement heuristics of the CNCH at each level. Experimentation is used to find a suitable combination, which extends the global view of these heuristics. Results comparing both SL and ML are presented.

Pneumatic contactless microfeeder design refinement through CFD simulation

A new contactless pneumatic microfeeder based on distributed manipulation is proposed. By cooperation of dynamically programmable microactuators, the part to be conveyed floats over an air cushion and is moved to the desired location with the desired orientation. CFD simulations are used to test the validity of the proposed concept and refine the design of the microactuators

Multilevel refinement for combinatorial optimisation: boosting metaheuristic performance

The multilevel paradigm as applied to combinatorial optimisation problems is a simple one, which at its most basic involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found, usually at the coarsest level, and then iteratively refined at each level, coarsest to finest, typically by using some kind of heuristic optimisation algorithm (either a problem-specific local search scheme or a metaheuristic). Solution extension (or projection) operators can transfer the solution from one level to another. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (for example multigrid techniques can be viewed as a prime example of the paradigm). Overview papers such as [] attest to its efficacy. However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial problems and in this chapter we discuss recent developments. In this chapter we survey the use of multilevel combinatorial techniques and consider their ability to boost the performance of (meta)heuristic optimisation algorithms.

Light emission from scanning tunnelling microscope on polycrystalline Au films - what is happening at the single-grain level?

When operated with a metallic tip and sample the scanning tunnelling microscope constitutes a nanoscale, plasmonic light source yielding broadband emission up to a photon energy determined by the applied bias. The emission is due to tunnelling electron excitation and subsequent radiative decay of localized plasmon modes, which can be on the lateral scale of a single metal grain (similar to 25 nm) or less. For a Au-tip/Au-polycrystalline sample under ambient conditions it is found that the intensity and spectral content of the emitted light are not dependent on the lateral grain dimension, but are predominantly determined by the tip geometry. However, the intensity increases strongly with increasing film thickness (grain depth) up to 20-25 nm or approximately the skin depth of the Au film. Photon maps can show less emissive grains and two classes of this occurrence are distinguished. The first is geometrical in origin - a double-tip structure in this case - while the second is due to a contamination-induced lowering of the local work function that causes the tunnel gap to increase. It is suggested that differences in work-function lowering between grains presenting different crystalline facets, combined with an exponential decay in emitted light intensity with tip - sample distance, leads to grain contrast. These results are relevant to tip-enhanced Raman scattering and the fabrication of micro/nano-scale planar, light-emitting tunnel devices.

Exploring grain size as a cause for dead-layer effects in thin film capacitors

Pulsed laser deposition was used to make a series of Au/Ba0.5Sr0.5TiO3 (BST)/SrRuO3/MgO thin film capacitors with dielectric thickness ranging from similar to15 nm to similar to1 mum. Surface grain size of the dielectric was monitored as a function of thickness using both atomic force microscopy and transmission electron microscopy. Grain size data were considered in conjunction with low field dielectric constant measurements. It was observed that the grain size decreased with decreasing thickness in a manner similar to the dielectric constant. Simple models were developed in which a functionally inferior layer at the grain boundary was considered as responsible for the observed dielectric behavior. If a purely columnar microstructure was assumed, then constant thickness grain-boundary dead layers could indeed reproduce the series capacitor dielectric response observed, even though such layers would contribute electrically in parallel with unaffected bulk- like BST. Best fits indicated that the dead layers would have a relative dielectric constant similar to40, and thickness of the order of tens of nanometers. For microstructures that were not purely columnar, models did not reproduce the observed dielectric behavior well. However, cross-sectional transmission electron microscopy indicated columnar microstructure, suggesting that grain boundary dead layers should be considered seriously in the overall dead-layer debate. (C) 2002 American Institute of Physics.