Preface [Special Issue: International Symposium on Combinatorial Optimisation (CO2000)]

Preface [Special Issue containing a selection of papers presented at the International Symposium on Combinatorial Optimisation (CO2000) held at the University of Greenwich, London, from 12-14 July 2000.

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 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.

The Use of Electrospray Mass Spectrometry to Determine Speciation in a Dynamic Combinatorial Library for Anion Recognition

The composition of a dynamic mixture of similar 2,2'-bipyridine complexes of iron(II) bearing either an amide (5-benzylamido-2,2'-bipyridine and 5-(2-methoxyethane)amido-2,2'-bipyridine) or an ester (2,2'-bipyridine-5-carboxylic acid benzylester and 2,2'-bipyridine-5-carboxylic acid 2-methoxyethane ester) side chain have been evaluated by electrospray mass spectroscopy in acetonitrile. The time taken for the complexes to come to equilibrium appears to be dependent on the counteranion, with chloride causing a rapid redistribution of two preformed heteroleptic complexes (of the order of 1 hour), whereas the time it takes in the presence of tetrafluoroborate salts is in excess of 24^^h. Similarly the final distribution of products is dependent on the anion present, with the presence of chloride, and to a lesser extent bromide, preferring three amide-functionalized ligands, and a slight preference for an appended benzyl over a methoxyethyl group. Furthermore, for the first time, this study shows that the distribution of a dynamic library of metal complexes monitored by ESI-MS can adapt following the introduction of a different anion, in this case tetrabutylammonium chloride to give the most favoured heteroleptic complex despite the increasing ionic strength of the solution. 

Characterisation of pavement profile heights using accelerometer readings and a combinatorial optimisation technique

Pavement surface profiles induce dynamic ride responses in vehicles which can potentially be used to classify road surface roughness. A novel method is proposed for the characterisation of pavement roughness through an analysis of vehicle accelerations. A combinatorial optimisation technique is applied to the determination of pavement profile heights based on measured accelerations at and above the vehicle axle. Such an approach, using low-cost inertial sensors, would provide an inexpensive alternative to the costly laser-based profile measurement vehicles. The concept is numerically validated using a half-car roll dynamic model to infer measurements of road profiles in both the left and right wheel paths.

Combinatorial Frequency Generation in Quasi-Periodic Stacks of Nonlinear Dielectric Layers

Three-wave mixing in quasi-periodic structures (QPSs) composed of nonlinear anisotropic dielectric layers, stacked in Fibonacci and Thue-Morse sequences, has been explored at illumination by a pair of pump waves with dissimilar frequencies and incidence angles. A new formulation of the nonlinear scattering problem has enabled the QPS analysis as a perturbed periodic structure with defects. The obtained solutions have revealed the effects of stack composition and constituent layer parameters, including losses, on the properties of combinatorial frequency generation (CFG). The CFG features illustrated by the simulation results are discussed. It is demonstrated that quasi-periodic stacks can achieve a higher efficiency of CFG than regular periodic multilayers.

Quasi-periodic stacks of semiconductor layers: Combinatorial frequency generation

The nonlinear scattering and combinatorial frequency generation by the quasi-periodic Fibonacci and Thue-Morse stacks of semiconductor layers have been investigated taking into account the nonlinear charge dynamics. It has been shown that the mixing processes in passive semiconductor structures are driven by the competitive effects of the collision of charges and resonance interactions of carriers with pump waves. The effects of the stack arrangements and constituent layer parameters on the efficiency of the combinatorial frequency generation are discussed. 

A novel method of microsatellite genotyping-by-sequencing using individual combinatorial barcoding

This study examines the potential of next-generation sequencing based ‘genotyping-by-sequencing’ (GBS) of microsatellite loci for rapid and cost-effective genotyping in large-scale population genetic studies. The recovery of individual genotypes from large sequence pools was achieved by PCR-incorporated combinatorial barcoding using universal primers. Three experimental conditions were employed to explore the possibility of using this approach with existing and novel multiplex marker panels and weighted amplicon mixture. The GBS approach was validated against microsatellite data generated by capillary electrophoresis. GBS allows access to the underlying nucleotide sequences that can reveal homoplasy, even in large datasets and facilitates cross laboratory transfer. GBS of microsatellites, using individual combinatorial barcoding, is potentially faster and cheaper than current microsatellite approaches and offers better and more data.

On lattices from combinatorial game theory modularity and a representation theorem: Finite case

We show that a self-generated set of combinatorial games, S, may not be hereditarily closed but, strong self-generation and hereditary closure are equivalent in the universe of short games. In [13], the question “Is there a set which will give an on-distributive but modular lattice?” appears. A useful necessary condition for the existence of a finite non-distributive modular L(S) is proved. We show the existence of S such that L(S) is modular and not distributive, exhibiting the first known example. More, we prove a Representation Theorem with Games that allows the generation of all finite lattices in game context. Finally, a computational tool for drawing lattices of games is presented.

Numerical and combinatorial applications of generalized Appell polynomials

This thesis studies properties and applications of different generalized Appell polynomials in the framework of Clifford analysis. As an example of 3D-quasi-conformal mappings realized by generalized Appell polynomials, an analogue of the complex Joukowski transformation of order two is introduced. The consideration of a Pascal n-simplex with hypercomplex entries allows stressing the combinatorial relevance of hypercomplex Appell polynomials. The concept of totally regular variables and its relation to generalized Appell polynomials leads to the construction of new bases for the space of homogeneous holomorphic polynomials whose elements are all isomorphic to the integer powers of the complex variable. For this reason, such polynomials are called pseudo-complex powers (PCP). Different variants of them are subject of a detailed investigation. Special attention is paid to the numerical aspects of PCP. An efficient algorithm based on complex arithmetic is proposed for their implementation. In this context a brief survey on numerical methods for inverting Vandermonde matrices is presented and a modified algorithm is proposed which illustrates advantages of a special type of PCP. Finally, combinatorial applications of generalized Appell polynomials are emphasized. The explicit expression of the coefficients of a particular type of Appell polynomials and their relation to a Pascal simplex with hypercomplex entries are derived. The comparison of two types of 3D Appell polynomials leads to the detection of new trigonometric summation formulas and combinatorial identities of Riordan-Sofo type characterized by their expression in terms of central binomial coefficients.

On lattices from combinatorial game theory modularity and a representation theorem: finite case

We show that a self-generated set of combinatorial games, S. may not be hereditarily closed but, strong self-generation and hereditary closure are equivalent in the universe of short games. In [13], the question "Is there a set which will give a non-distributive but modular lattice?" appears. A useful necessary condition for the existence of a finite non-distributive modular L(S) is proved. We show the existence of S such that L(S) is modular and not distributive, exhibiting the first known example. More, we prove a Representation Theorem with Games that allows the generation of all finite lattices in game context. Finally, a computational tool for drawing lattices of games is presented. (C) 2014 Elsevier B.V. All rights reserved.