Abstract: The paper discusses the problem of the induction of a minimal nondeterministic finite automaton (NFA) consistent with a given set of examples and counterexamples. The main contribution of the paper is the proposal of an efficient parallel algorithm transforming the NFA induction problem into a family of constraint satisfaction problems (CSP). Two original techniques for fast CSPs evaluation are proposed and discussed. The efficacy of the parallel algorithm is evaluated experimentally on selected benchmarks. The proposed algorithm solves all analyzed benchmark examples, so called Tomita languages, in the time below half a minute, which should be considered an important achievement, as compared to our previous efforts which required minutes or hours to solve some of the aforementioned benchmarks.

Abstract: The purpose of this research is to develop a decision making tool to select aluminum billet size as well as to plan the extrusion operation to meet the required profile length with minimum waste. The decision making scheme developed includes practical constraints and considerations in the extrusion operation which are not typically considered by the optimization community. To address the variations in aluminum density, extrusion experiments to investigate the behavior of Al 6063 are performed on various cross-sectional areas (products) with different process parameters as well as desired lengths. The range of aluminum density is determined. The range of weight per lengths of the new aluminum profile is predicted from the curve fitting scheme. Maximum density is used in the optimization tool to ensure that the extruded profile is always sufficient for the number of workpieces determined. The billet size can be reduced incrementally if the extruded profile is longer than expected. Even with modest problem sizes, solving the ILP formulation is time-consuming. The solutions for non-linear integer programming for the case of multiple billets per extrusion are not obtainable. Otherwise the optimal solutions from the ILP are compared with the solutions from heuristic algorithms developed. For online billet cutting case, it is found that the solutions from ILP usually call for the use of more billet sizes than those obtained from the heuristic algorithm. However, the solutions from ILP lead to better material utilization than those from the algorithm by 1-4%. The tradeoff between cutting and extruding more billets and 4% difference in waste should be examined by the end user. In the standard billet size case, the heuristic algorithms perform well as compared to those obtained from solving the ILP. The solutions from both sources are almost identical. Solutions obtained from both ILP and heuristic methods are equal or better than the manual calculation employed by the company. The actual implementation of the program developed is now underway. It is expected that the solution methodology developed in this research can improve material utilization up to 10% over the current approach used (manual calculation) in some cases.

Abstract: This paper describes our on-going work to accelerate ZENO, a software tool based on Monte Carlo methods (MCMs), used for computing material properties at nanoscale. ZENO employs three main algorithms: (1) Walk on Spheres (WoS), (2) interior sampling, and (3) surface sampling. We have accelerated the first two algorithms. For the sake of brevity, the paper will discuss our work on the first one only as it is the most commonly used and the acceleration techniques were similar in both cases. WoS is a Brownian motion MCM for solving a class of partial differential equations (PDEs). It provides a stochastic solution to a PDE by estimating the probability that a random walk, which started at infinity, will hit the surface of the material under consideration. WoS is highly effective when the problem's geometry is additive, as this greatly reduces the number of walk steps needed to achieve accurate results. The walks start on the surface of an enclosing sphere and can make much larger jumps than in a direct simulation of Brownian motion. Our current implementation represents the molecular structure of nanomaterials as a union of possibly overlapping spheres. The core processing bottleneck in WoS is a Computational Geometry one, as the algorithm repeatedly determines the distance from query point to the material surface in each step of the random walk. In this paper, we present results from benchmarking spatial data structures, including several open-source implementations of k-D trees, for accelerating WoS algorithmically. The paper also presents results from our multicore and cluster parallel implementation to show that it exhibits linear strong scaling with the number of cores and compute nodes; this implementation delivers up to 4 orders of magnitude speedup compared to the original FORTRAN code when run on 8 nodes (each with dual 6-core Intel Xeon CPUs) with 24 threads per node.

Abstract: The node-depth encoding is a representation for evolutionary algorithms applied to tree prob-lems. Its represents trees by storing the nodes and their depth in a proper ordered list. Theoriginal formulation of the node-depth encoding has only mutation operators as the searchmechanism. Although the representation has this restriction, it has obtained good results withlow convergence. Then, this work proposes a specic recombination operator to improve theconvergence of the node-depth encoding representation. These operators are based on recom-bination for permutation representations. An investigation into the bias and heritability of theproposed recombination operator shows that it has a bias towards stars and low heritability.The performance of node-depth encoding with the proposed operator is investigated for theoptimal communication spanning tree problem. The results are presented for benchmark in-stances in the literature. The use of the recombination operator results in a faster convergencethan with only mutation operators.

Abstract: Typically, the performance of swarm and evolutionary methods is assessed by comparing their results when applied to some known finite benchmarks. In general, these metaheuristics depend on many parameter values and many possible exchangeable sub-steps, which yields a huge number of possible algorithm configurations. In this paper we argue that this high setup versatility lets developers expressively tune the method, in an ad-hoc way, to the target inputs to be solved, and hence to those in the benchmark under consideration. However, this does not imply properly solving any other input not considered in the benchmark. Several subtle ways to support that tuning (which can be consciously noticed by the developer, but can also be unconscious) are presented and discussed in the paper. Besides, as a posible alternative to using known finite benchmarks, we discuss the pros and cons of using random input generators, and we illustrate how to use such generators in a specific problem, MAX-3SAT. A general protocol to support the fair development of comparisons of metaheuristics based on random input generators is presented.