Capacitated Clustering Problems by Hybrid Simulated Annealing and Tabu Search

The capacitated clustering problem (CCP) is the problem in which a given set of weighted objects is to be partitioned into clusters so that the total weight of objects in each cluster is less than a given value (cluster ‘capacity’). The objective is to minimize the total scatter of objects from the ‘centre’ of the cluster to which they have been allocated. A simple constructive heuristic, a R-interchange generation mechanism, a hybrid simulated annealing (SA) and tabu search (TS) algorithm which has computationally desirable features using a new non-monotonic cooling schedule, are developed. A classification of the existing SA cooling schedules is presented. The effects on the final solution quality of the initial solutions, the cooling schedule parameters and the neighbourhood search strategies are investigated. Computational results on randomly generated problems with size ranging from 50 to 100 customers indicate that the hybrid SA/TS algorithm out-performs previous simulated annealing algorithms, a simple tabu search and local descent algorithms.     

Geometric theory and feedback invariants of generalized linear systems: A matrix pencil approach

Generalized linear systems are classified according to their algebraic structure and their regularizability and normalizability properties under generalized state feedback are investigated. New feedback invariants are introduced in terms of the input-space restriction pencil and the Plücker matrix of the system. It is shown that the classification of subspaces of the state space of generalized linear systems is reduced to an equivalent problem of classifying the subspacesV of the domain of an ordered pair (F, G), F, Gε?^m×n. The set of strict equivalence invariants of the restriction pencil (F, G)/V provides a complete, basis-free algebraic characterization and leads to the definition of notions of geometric invariance. The key geometric notions that emerge are those of (F, G)-, (G, F)-, complete-(F, G)-, partitioned(F, G)-, cyclic-, and semicyclic-invariant subspaces. A complete set of geometric algorithms leading to the computation of the above families is also given. The above families of invariant subspaces are characterized in terms of the invariants of (F, G)/V, and this provides the links with their dynamic characterization. These results provide an “open-loop” or “feedback-free” unifying treatment of spaces of generalized systems, which for the case of proper systems is reduced to the standard geometric theory results.     

Automatically performing weak mutation with the aid of symbolic execution,concolic testing and search-based testing

Automating software testing activities can increase the quality and drastically decrease the cost of software development. Toward this direction, various automated test data generation tools have been developed. The majority of existing tools aim at structural testing, while a quite limited number aim at a higher level of testing thoroughness such as mutation. In this paper, an attempt toward automating the generation of mutation-based test cases by utilizing existing automated tools is proposed. This is achieved by reducing the killing mutants’ problem into a covering branches one. To this extent, this paper is motivated by the use of state of the art techniques and tools suitable for covering program branches when performing mutation. Tools and techniques such as symbolic execution, concolic execution, and evolutionary testing can be easily adopted toward automating the test input generation activity for the weak mutation testing criterion by simply utilizing a special form of the mutant schemata technique. The propositions made in this paper integrate three automated tools in order to illustrate and examine the method’s feasibility and effectiveness. The obtained results, based on a set of Java program units, indicate the applicability and effectiveness of the suggested technique. The results advocate that the proposed approach is able to guide existing automating tools in producing test cases according to the weak mutation testing criterion. Additionally, experimental results with the proposed mutation testing regime show that weak mutation is able to speedup the mutant execution time by at least 4.79 times when compared with strong mutation.     

Matrix pencil methodologies for computing the greatest common divisor of polynomials: hybrid algorithms and their performance

The computation of the greatest common divisor (GCD) of several polynomials is a problem that emerges in many fields of applications. The GCD computation has a non-generic nature and thus its numerical computation is a hard problem. In this paper we examine the family of matrix pencil methods for GCD computation and investigate their performance as far as their complexity, error analysis and their effectiveness for evaluating approximate solutions. The relative merits of the various variants of such methods are examined for the different cases of sets of polynomials with varying number of elements and degree. The developed algorithms combine symbolical and numerical programming and this is what we define here as hybrid computations. The combination of numerical operations with symbolical programming can improve the nature of the methods and guarantees the stability of the algorithm. Furthermore, it emphasizes the significance of hybrid computations in complex problems such as the computation of GCD. All methods are tested thoroughly for several sets of polynomials and the results are presented in tables.     

Proper invariant realizations of singular system problems

The notion of proper invariant realization of a triple for a specially defined linear space is introduced and its properties and construction are investigated. This notion of realization allows the reduction of the study of dynamic characterization of subspaces of singular systems to standard problems of linear systems theory. The proof of the results is given     

Microstructure and transport properties of porous building materials

To successfully predict the performance of building materials exposed to a degradative environment, transport properties must be either measured or estimated. The development of relationships between microstructure and transport properties for these materials should allow accurate prediction of the latter and an increased understanding of how microstructure influences transport. Here, two microstructural characterization techniques, mercury intrusion porosimetry and scanning electron microscopy, are combined with computer modelling techniques to compute the vapor diffusivity and air permeability of three building materials commonly exposed in building facades, two types of brick and a natural sandstone. In general, the computed values compare favorably to those measured experimentally, thus demonstrating the capability of employing microstructural characterization to predict transport properties.

---

Résumé Pour obtenir une prédiction fiable des performances des matériaux de construction exposés à un environnement agressif, leurs propriétés de transport doivent être soit mesurées soit estimées. Le développement de relations entre la microstructure et les propriétés de transport devrait permettre une prédiction exacte de ces dernières et une meilleure compréhension de l’influence de la microstructure sur le transfert. Dans cet article, deux techniques de caractérisation de la microstructure (porosimétrie au mercure et microscopie électronique à balayage) sont combinées avec des techniques de simulation par ordinateur pour calculer la diffusivité à la vapeur d’eau et la perméabilité à l’air de trois matériaux de construction traditionnellement utilisés en facades: deux types de brique et un grès naturel. En général, les valeurs calculées sont proches de celles mesurées expérimentalement. Ces résultats démontrent les possibilités des outils de caractérisation de la structure pour prédire les propriétés de transport.

---

---

Editorial note: Mr. Daniel Quenard is a RILEM Senior Member and a member of TC 123-MME on the Use of Microstructural Models and Expert systems for Cemenitious Materials. He and Mr. K. Xu work at the CSTB (Centre Scientifique et Technique du Batiment), France, a RILEM Titular Member. Mr. Dale P. Bentz is a RILEM Senior Member and participates in the work of TC 159-ETC (Engineering of the Interfacial Transition Zone in Cementitious Composites). He and Mr. Nicos Martys work at the National Institute of Standards and Technology (NIST), USA, a RILEM Titular Member.     

Model matching under external and input-output equivalence

The model-matching problem for systems described by external models is considered in frameworks of both external and input-output equivalence. Necessary conditions for the solvability of the problem are produced, and it is shown that in certain cases these conditions are also sufficient. In the case where necessary and sufficient conditions exist, the solutions of the problem are obtained in a constructive way and a parametrization of solutions is given.