Search

A novel iterative combinatorial nanoscale search based on the application of cross-sectional synchrotron X-ray nanodiffraction and cross-sectional nanoindentation is used to refine the relationship between deposition conditions, microstructure and properties of nanostructured TiAlN thin films. Using three iterative steps, a nanolamellar TiAlN thin film with a maximal hardness of ∼36 GPa is developed., Because of the tremendous variability of crystallite sizes and shapes in nano­materials, it is challenging to assess the corresponding size–property relationships and to identify microstructures with particular physical properties or even optimized functions. This task is especially difficult for nanomaterials formed by self-organization, where the spontaneous evolution of microstructure and properties is coupled. In this work, two compositionally graded TiAlN films were (i) grown using chemical vapour deposition by applying a varying ratio of reacting gases and (ii) subsequently analysed using cross-sectional synchrotron X-ray nanodiffraction, electron microscopy and nanoindentation in order to evaluate the microstructure and hardness depth gradients. The results indicate the formation of self-organized hexagonal–cubic and cubic–cubic nanolamellae with varying compositions and thicknesses in the range of ∼3–15 nm across the film thicknesses, depending on the actual composition of the reactive gas mixtures. On the basis of the occurrence of the nanolamellae and their correlation with the local film hardness, progressively narrower ranges of the composition and hardness were refined in three steps. The third film was produced using an AlCl3/TiCl4 precursor ratio of ∼1.9, resulting in the formation of an optimized lamellar microstructure with ∼1.3 nm thick cubic Ti(Al)N and ∼12 nm thick cubic Al(Ti)N nanolamellae which exhibits a maximal hardness of ∼36 GPa and an indentation modulus of ∼522 GPa. The presented approach of an iterative nanoscale search based on the application of cross-sectional synchrotron X-ray nanodiffraction and cross-sectional nanoindentation allows one to refine the relationship between (i) varying deposition conditions, (ii) gradients of microstructure and (iii) gradients of mechanical properties in nanostructured materials prepared as thin films. This is done in a combinatorial way in order to screen a wide range of deposition conditions, while identifying those that result in the formation of a particular microstructure with optimized functional attributes.

BackgroundHealth promotion can be tailored by combining ecological momentary assessments (EMA) with time series analysis. This combined method allows for studying the temporal order of dynamic relationships among variables, which may provide concrete indications for intervention. However, application of this method in health care practice is hampered because analyses are conducted manually and advanced statistical expertise is required. ObjectiveThis study aims to show how this limitation can be overcome by introducing automated vector autoregressive modeling (VAR) of EMA data and to evaluate its feasibility through comparisons with results of previously published manual analyses. MethodsWe developed a Web-based open source application, called AutoVAR, which automates time series analyses of EMA data and provides output that is intended to be interpretable by nonexperts. The statistical technique we used was VAR. AutoVAR tests and evaluates all possible VAR models within a given combinatorial search space and summarizes their results, thereby replacing the researcher’s tasks of conducting the analysis, making an informed selection of models, and choosing the best model. We compared the output of AutoVAR to the output of a previously published manual analysis (n=4). ResultsAn illustrative example consisting of 4 analyses was provided. Compared to the manual output, the AutoVAR output presents similar model characteristics and statistical results in terms of the Akaike information criterion, the Bayesian information criterion, and the test statistic of the Granger causality test. ConclusionsResults suggest that automated analysis and interpretation of times series is feasible. Compared to a manual procedure, the automated procedure is more robust and can save days of time. These findings may pave the way for using time series analysis for health promotion on a larger scale. AutoVAR was evaluated using the results of a previously conducted manual analysis. Analysis of additional datasets is needed in order to validate and refine the application for general use.

In the past few decades, although people have conducted in-depth research on community detection in one-mode networks, community detection in bipartite networks has not been extensively researched. In this paper, we propose an improved artificial bee colony algorithm named IABC-BN, which is used to detect the communities in two-mode graphs (i.e. bipartite graphs) with two kinds of vertices in the cluster (i.e. community). Firstly, this paper proposed a novel population initialization process of artificial bee colony (ABC) method for two-mode graph cluster identification. This initialization method can improve the diversity of initial population of ABC and speed up its convergence rate. Secondly, in the employed bee search step of the algorithm, a new combinatorial search equation is proposed. This equation is guided by the global optimal solution and the better neighbour solution of the current solution. By using this combination equation and the increased parameter perturbation frequency, the exploitation ability of the algorithm is further enhanced. Thirdly, in the onlooker bees step, another new combination search equation is also proposed. This equation improves the exploitation level of the algorithm, and an opposition based studying method is employed to promote the exploitation ability of the algorithm. Lastly, in scout bee stage, a probability threshold $\beta $ is introduced to enhance the exploration ability of the algorithm and improve the population diversity of the algorithm. To our knowledge, the IABC-BN method presented in this paper is the first ABC method used to cluster identification in two-mode graphs with two kinds of vertices in the cluster. For verifying the accuracy of the results of the proposed method, a large number of experiments are carried out making use of synthetic bipartite graphs and real bipartite graphs. The test outcomes show that this algorithm is an excellent algorithm for cluster discovery in two-mode graph.

This paper addresses the distributed limited-buffer flowshop scheduling problem with makespan minimization criterion for the first time. The manufacturing layout consists of multiple homogeneous factories and each one is set as a permutation flowshop with limited buffers between any two adjacent machines. Compared with traditional single shop scheduling, this problem is more realistic because of the distribution and limited buffer constraints. Given that the NP-hardness, this paper focuses on the approximate approaches, and successively proposes two constructive heuristics for generating fast schedule and providing good initialization of meta-heuristics, a differential evolution algorithm run in continuous search space to further better the so-obtained schedules, and a discrete differential evolution algorithm implemented directly in combinatorial search space. Extensive experimental results validate that the performance of discrete differential evolution perform the best and other algorithms proposed in this paper are all with satisfactory evaluations.

Answer set programming (ASP) is a declarative programming paradigm that is geared towards difficult combinatorial search problems. Sometimes, run times of ASP systems suffer due to so called grounding bottleneck. Lazy grounding solvers aim to mitigate this issue. In this paper we describe a new lazy grounding solver called DualGrounder. The DualGrounder system leverages multi-shot capabilities of the advanced ASP platform clingo. This paper also includes experimental data to explore the performance of DualGrounder compared to similar ASP grounding and solving systems.

The multi-agent path finding (MAPF) problem is a combinatorial search problem that aims at finding paths for multiple agents (e.g., robots) in an environment (e.g., an autonomous warehouse) such that no two agents collide with each other, and subject to some constraints on the lengths of paths. We consider a general version of MAPF, called mMAPF, that involves multi-modal transportation modes (e.g., due to velocity constraints) and consumption of different types of resources (e.g., batteries). The real-world applications of mMAPF require flexibility (e.g., solving variations of mMAPF) as well as explainability. Our earlier studies on mMAPF have focused on the former challenge of flexibility. In this study, we focus on the latter challenge of explainability, and introduce a method for generating explanations for queries regarding the feasibility and optimality of solutions, the nonexistence of solutions, and the observations about solutions. Our method is based on answer set programming. This paper is under consideration for acceptance in TPLP., Paper presented at the 36th International Conference on Logic Programming (ICLP 2020), University Of Calabria, Rende (CS), Italy, September 2020, 16 pages, 6 figures

Aim. This paper is the continuation of [1] that proposes using the R programming language for fault tree analysis (FTA). In [1], three examples are examined: fault tree (FT) calculation per known probabilities, dynamic FT calculation per known distributions of times to failure for a system’selements. In the latter example, FTA is performed for systems with elements that are described by different functional and service models. Fault tree analysis (FTA) is one of the primary methods of dependability analysis of complex technical systems. This process often utilizes commercial software tools like Saphire, Risk Spectrum, PTC Windchill Quality, Arbitr, etc. Practically each software tool allows calculating the dependability of complex systems subject to possible common cause failures (CCF). CCF are the associated failures of a group of several elements that occur simultaneously or within a short time interval (i.e. almost simultaneously) due to one common cause (e.g. a sudden change in the climatic service conditions, flooding of the premises, etc.). An associated failure is a multiple failure of several system elements, of which the probability cannot be expressed simply as the product of the probabilities of unconditional failures of individual elements. There are several generally accepted models used in CCF probability calculation: the Greek letters model, the alpha, beta factor models, as well as their variations. The beta factor model is the most simple in terms of associated failures simulation and further dependability calculation. The other models involve combinatorial search associated events in a group of n events, that becomes labor-consuming if the number n is large. Therefore, in the above software tools there are some restrictions on the n, beyond which the probability of CCF is calculated approximately. In the current R FaultTree package version there are no above CCF models, therefore all associated failures have to be simulated manually, which is not complicated if the number of associated events is small, as well as useful in terms of understanding the various CCF models. In this paper, for the selected diagram a detailed analysis of the procedure of associated failures simulation is performed for alpha and beta factor models. The Purposeof this paper consists in the detailed analysis of the alpha and beta factor methods for a certain diagram, in the demonstration of fault tree creation procedure taking account of ССF using R’s FaultTree package. Methods. R’s FaultTree scripts were used for the calculations and FTA capabilities demonstration.Conclusions. Two examples are examined in detail. In the first example, for the selected block diagram that contains two groups of elements subject to associated failures, the alpha factor model is applied. In the second example, the beta factor model is applied. The deficiencies of the current version of FaultTree package are identified. Among the main drawbacks we should indicate the absence of some basic logical gates.

This paper addresses the high school timetabling problem. The problem consists in building weekly timetables for meetings between classes and teachers with the goal of minimizing violations of specific requirements. In the last decades, several mixed-integer programs have been proposed and tested for this family of problems. However, medium and large size instances are still not effectively solved by these programs using state-of-the-art solvers and the scientific community has given special attention to the devising of alternative soft computing algorithms. In this paper, we propose a soft computing approach based on Iterated Local Search and Variable Neighborhood Search metaheuristic frameworks. Our algorithms incorporate new neighborhood structures and local search routines to perform an effective search. We validated the proposed algorithms on variants of the problem using seven public instances and a new dataset with 34 real-world instances including large cases. The results demonstrate that the proposed algorithms outperform the state-of-the-art approaches in both cases, finding the best solutions in 38 out of the 41 tested instances.

This paper presents a cooperative, combinatorial search model for a multi-mobile sensor, multi-mobile target scenario in a two dimensional grid space. In the proposed model, sensors and targets act as searchers and hiders of a search game. A search game is a game between searcher and hider, modeled on a graph. In this paper, the identified problem states that multiple targets enter into a grid from the same or different sides and try to exit on the opposite directions of their respective entry sides. Alternatively, multiple mobile sensors are randomly deployed in the grid and try to maximize the number of target searched and to minimize search time before the targets leave the grid. This problem fits into several real life scenarios such as international border security, terrorist searching in a specified area, finding spies etc. The novelty of the proposed model is interpreting the problem as a search game and formulating strategies for the mobile sensors to optimize their moves to maximize the number of target searched and minimize search time. In this paper, shortest path and random walk strategies for the targets are analyzed by applying suitable mathematical models and on the other hand, advantages of cooperative over non-cooperative strategies for the mobile sensors are also shown with the help of analytical methods and simulation results. The significant mathematical concepts applied in the proposed model are as follows-computing shortest path, random walk, Markov chain, probability graph, overlapping of multiple probability graphs, cooperative and non-cooperative strategies etc.

This paper proposes a method for visualizing combinatorial search spaces named low-dimensional Euclidean embedding (LDEE). The proposed method transforms the original search space, such as a set of permutations or binary vectors, to $\pmb {\mathbb {R}}^{k}$ (with ${k} {=} {2}$ or 3 in practice) while aiming to preserve spatial relationships existing in the original space. The LDEE method uses the t-distributed stochastic neighbor embedding (t-SNE) to transform solutions from the original search space to the Euclidean one. In this paper, it is mathematically shown that the assumptions underlying the t-SNE method are valid in the case of permutation spaces with the Mallows distribution. The same is true for other metric spaces provided that the distribution of points is assumed to be normal with respect to the adopted metric. The embedding obtained using t-SNE is further refined to ensure visual separation of individual solutions. The visualization obtained using the LDEE method can be used for analyzing the behavior of the population in a population-based metaheuristic, the working of the genetic operators, etc. Examples of visualizations obtained using this method for the four peaks problem, the firefighter problem, the knapsack problem, the quadratic assignment problem, and the traveling salesman problem are presented in this paper.

International audience; Most studies related to parallel and portfolio search for solving combinatorial problems, such as those found in Boolean satisfiability or constraint programming, evaluate search cost in terms of runtime. However, given the complex computing architectures available today and the focus on the environmental impact of computing, there is growing interest in also considering the energy cost associated with solving these problems. In the context of combinatorial problem-solving, a simple approximation of energy cost is the product of the number of machines multiplied by the runtime spent to solve a problem instance. However, the picture is much more complex due to the impact that the distribution of runtimes, even for solving a single specific instance, can have on search cost. In this paper we present an initial, but comprehensive, study on the impact of runtime distribution on the amount of energy required for combinatorial problem solving characterized by two common continuous runtime distributions, namely the Weibull and Pareto distributions. The primary contribution of this paper is to demonstrate that there is an interesting and non-trivial relationship between runtime, parallelisation, and energy cost in combinatorial solving that is worthy of further study.

A new approach is used to generate combinatorial test suites.Cuckoo Search application is investigated for a new type of application and case study.The strategy opens a new approach in Search Based Software Testing (SBST).The strategy is evaluated through different benchmarks and it is able to get comparative results.Application of combinatorial optimization is also investigated in the current paper. ContextSoftware has become an innovative solution nowadays for many applications and methods in science and engineering. Ensuring the quality and correctness of software is challenging because each program has different configurations and input domains. To ensure the quality of software, all possible configurations and input combinations need to be evaluated against their expected outputs. However, this exhaustive test is impractical because of time and resource constraints due to the large domain of input and configurations. Thus, different sampling techniques have been used to sample these input domains and configurations. ObjectiveCombinatorial testing can be used to effectively detect faults in software-under-test. This technique uses combinatorial optimization concepts to systematically minimize the number of test cases by considering the combinations of inputs. This paper proposes a new strategy to generate combinatorial test suite by using Cuckoo Search concepts. MethodCuckoo Search is used in the design and implementation of a strategy to construct optimized combinatorial sets. The strategy consists of different algorithms for construction. These algorithms are combined to serve the Cuckoo Search. ResultsThe efficiency and performance of the new technique were proven through different experiment sets. The effectiveness of the strategy is assessed by applying the generated test suites on a real-world case study for the purpose of functional testing. ConclusionResults show that the generated test suites can detect faults effectively. In addition, the strategy also opens a new direction for the application of Cuckoo Search in the context of software engineering.

This paper presents a new combinatorial search method for the quasi-static stiffness performance evaluation and payload capacity analysis of serial modular reconfigurable robots (MRRs). The goal in this paper is to optimize the external payload capacity to achieve a global set of satisfactory kineto-elastic performance requirements for all module configurations. This problem exhibits considerable numerical complexities since the maximum payload capacity is dependent on a large number of possible module configurations, the worst-case stiffness poses for each configuration, and multiple kineto-elastic performance requirements. Therefore, to alleviate these difficulties, the problem is decomposed into an elimination search algorithm to reduce the configuration search space, a genetic algorithm to directly search the configuration workspaces and find the worst-case stiffness poses, and a bisection method to determine the maximum payload capacity at the worst-case configurations and poses. It is demonstrated that the worst-case stiffness search method in this paper is superior in computational time and numerical accuracy compared to previous hierarchical or incremental search methods, which require searching through a pre-determined number of poses. Through case studies, the new combinatorial search method is proven to be computationally efficient and can obtain accurate results for the worst-case stiffness poses and maximum payload capacity.

retrieval is the most fundamental requirement for any kind of computing application and which requires search operation to be performed from massive databases implemented by various data structures. Searching an element from the list is the fundamental aspects in computing world. Numbers of algorithms are developed for searching an element among which linear search and binary search are the most popular algorithms. In this paper researcher has made efforts to compare these both algorithms to implement on various data structures and to find out the solution to implement binary search on linked linear list. This paper also analyzes both the algorithms at some extent for the applicability and execution efficiency. This paper also analyzes the few data structures to implement these algorithms. At last based on the linear search and binary search algorithms, one algorithm is designed to function on linked linear list.

Autonomous mobile robots have been deployed at hospitals to cope with numerous delivery services. Robots deliver items from point to point through autonomous navigation. Conventional robots work individually conducting only one task at a time. This paper proposes a fleet optimization method to maximize the advantages of operating a group of robots concurrently by assigning multiple tasks to a robot. The server selects an appropriate robot for a delivery task based on the cost for conducting the delivery task of each robot. The robot with the minimum cost is assigned for the new delivery task. This way, a robot is assigned to conduct multiple tasks. The scheduler finds the minimum routing path for visiting multiple delivery locations. The shortest path for visiting multiple delivery locations is derived from a combinatorial search approach. This paper proposes an algorithm that reduces the computational burden for finding the path combinations. Because this procedure takes a short amount of time, the allocation of a robot can be conducted in real-time. The proposed algorithm is tested in the simulation, and the results show that it increases the efficiency when using multiple robots. In addition, by running the simulation and reviewing the performance results, the management group of a hospital can determine the number of robots required at their site.

Search-based software testing has achieved great attention recently, but the efficiency is still the bottleneck of it. This paper focuses on improving the efficiency of generating test data for multiple paths. Genetic algorithms are chosen as the heuristic algorithms in search-based software testing in this paper. First, we propose an improved grouping strategy of target paths to balance the load of each calculation resource. This work makes a contribution to the parallel execution in search-based software testing. Then, common constraints of the target paths in the same group are collected to reduce the search space of test data. Symbolic execution technique is used in this phase. Based on the reduced search space, we can accelerate the convergence of search process and improve the efficiency of search-based software testing. Finally, our method is applied to some study cases to compare with other methods.

The core technology of the computer games is the search. The paper is studied to research both the mononuclear search algorithm and the parallel search algorithm. For the mononuclear search algorithm, the selective search thought is supplied to the computer games system. For the parallel search algorithm, the paper studies the several existing multi-core parallel search methods and analyzes their advantages and disadvantages. According to the characteristics, the improvement scheme is put forward to the parallel search algorithm. The practical results of the computer games system show the comparison effect between the original methods and the improved methods. The paper finally discusses some special programming skills of the Alpha-Beta implementation in the parallel search system. The advanced and modified algorithm is proved to be practical and applicative by experimentations and tests of parallel computer games system provided in this paper.

Testing is an important and expensive part of software and hardware development. Over the recent years, the construction of combinatorial interaction tests rose to play an important role towards making the cost of testing more efficient. Covering arrays are the key element of combinatorial interaction testing and a means to provide abstract test sets. In this paper, we present a family of set-based algorithms for generating covering arrays and thus combinatorial test sets. Our algorithms build upon an existing mathematical method for constructing independent families of sets, which we extend sufficiently in terms of algorithmic design in this paper. We compare our algorithms against commonly used greedy methods for producing 3-way combinatorial test sets, and these initial evaluation results favor our approach in terms of generating smaller test sets.

Determining the most appropriate search method or artificial intelligence technique to solve a problem is not always evident and usually requires implementation of the different approaches to ascertain this. In some instances a single approach may not be sufficient and hybridization of methods may be needed to find a solution. This process can be time consuming. The paper proposes the use of hyper-heuristics as a means of identifying which method or combination of approaches is needed to solve a problem. The research presented forms part of a larger initiative aimed at using hyper-heuristics to develop intelligent hybrid systems. As an initial step in this direction, this paper investigates this for classical artificial intelligence uninformed and informed search methods, namely depth first search, breadth first search, best first search, hill-climbing and the A* algorithm. The hyper-heuristic determines the search or combination of searches to use to solve the problem. An evolutionary algorithm hyper-heuristic is implemented for this purpose and its performance is evaluated in solving the 8-Puzzle, Towers of Hanoi and Blocks World problems. The hyper-heuristic employs a generational evolutionary algorithm which iteratively refines an initial population using tournament selection to select parents, which the mutation and crossover operators are applied to for regeneration. The hyper-heuristic was able to identify a search or combination of searches to produce solutions for the twenty 8-Puzzle, five Towers of Hanoi and five Blocks World problems. Furthermore, admissible solutions were produced for all problem instances.

In this paper we consider high-dimensional multiclass classification by sparse multinomial logistic regression. We propose first a feature selection procedure based on penalized maximum likelihood with a complexity penalty on the model size and derive the nonasymptotic bounds for misclassification excess risk of the resulting classifier. We establish also their tightness by deriving the corresponding minimax lower bounds. In particular, we show that there exist two regimes corresponding to small and large number of classes. The bounds can be reduced under the additional low noise condition. To find a penalized maximum likelihood solution with a complexity penalty requires, however, a combinatorial search over all possible models. To design a feature selection procedure computationally feasible for high-dimensional data, we propose multinomial logistic group Lasso and Slope classifiers and show that they also achieve the minimax order.

The fundamental inverse problem in distance geometry is the one of finding positions from inter-point distances. The Discretizable Molecular Distance Geometry Problem (DMDGP) is a subclass of the Distance Geometry Problem (DGP) whose search space can be discretized and represented by a binary tree, which can be explored by a Branch-and-Prune (BP) algorithm. It turns out that this combinatorial search space possesses many interesting symmetry properties that were studied in the last decade. In this paper, we present a new algorithm for this subclass of the DGP, which exploits DMDGP symmetries more effectively than its predecessors. Computational results show that the speedup, with respect to the classic BP algorithm, is considerable for sparse DMDGP instances related to protein conformation.

The paper gives overview of modern research on planning and scheduling of new generation of large groups of satellites, analyzes current methods and algorithms of planning and scheduling, considers their practical applications and main future trends. The list of requirements for developing new methods and algorithms for planning and scheduling is identified. The problem statement is formulated which shows multi-objective complexity of planning and scheduling for groups of satellites. A number of conflicting requirements are identified generated by demands and resources, including fast changing meteorological parameters, ballistic constraints, video cameras restrictions, satellite battery constraints, ground stations and communication lines requirements, etc. It is shown that the main part of developed methods and tools is still oriented on centralized control of resources and based on different heuristics for reducing exhausted combinatorial search of globally optimal options. These methods and tools do not consider networking nature of new generation of satellites groups which requires negotiations and conflict solving among orders and satellites in future. These new generation of satellites groups also requires high adaptability and flexibility, individuality, scalability, performance and reliability of future groups of satellites. One of new trends in adaptive planning and scheduling is multi-agent technology where agents of demands and resource can make matching on virtual market. But it requires new efforts not only on new generation software developments for designing open self-organized systems ("swarms of satellites") but also on direct communication between satellites and ground stations. Developing such smart swarms of satellites will provide new features, benefits and values for customers.

Gene selection aims at identifying a -small- subset of informative genes from the initial data to obtain high predictive accuracy for classification in human cancers. Gene selection can be considered as a combinatorial search problem and thus can be conveniently handled with optimization methods. hl{This paper proposes a Memetic Cellular Genetic Algorithm (MCGA) to solve the Feature Selection problem of cancer microarray datasets.} Benchmark gene expression datasets, i.e., colon, lymphoma, and leukaemia available in the literature were used for experimentation. MCGA is compared with other well-known metaheuristic´ strategies. The results demonstrate that our proposal can provide efficient solutions to find a minimal subset of the genes. Fil: Rojas, Matias Gabriel. Universidad Nacional de Cuyo. Instituto para las Tecnologías de la Informacion y las Comunicaciones; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Mendoza; Argentina Fil: Olivera, Ana Carolina. Universidad Nacional de Cuyo. Instituto para las Tecnologías de la Informacion y las Comunicaciones; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Mendoza; Argentina Fil: Carballido, Jessica Andrea. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Mendoza; Argentina. Universidad Nacional del Sur. Departamento de Ciencias e Ingeniería de la Computación. Instituto de Ciencias e Ingeniería de la Computación; Argentina Fil: Vidal, Pablo Javier. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Mendoza; Argentina. Universidad Nacional de Cuyo. Instituto para las Tecnologías de la Informacion y las Comunicaciones; Argentina

The practices by which actions are accomplished in interaction are invariably sensitive to context, as it is not only through their composition but also their position that they are recognisable as practices. This means that practices are not readily identifiable through straightforward searches for linguistic units in large datasets of spoken interaction. In this paper, we propose that through an explicitly combinatorial approach to search, the procedural basis of which is grounded in a specific array of compositional and sequential features associated with the candidate practice in question, we can more readily find potentially relevant examples of that phenomenon across large tracts of data, which can then be subjected to rigorous sequential analysis. We argue that this combinatorial search procedure enables us access to data from multiple different sources. We illustrate this combinatorial approach through an analysis of laughter that co-occurs with lapses in the ongoing progressivity of talk-in-interaction in various conversational settings. Careful analysis of post-lapse laughter in a dataset of initial interactions suggests that such laughter often occurs subsequent to silences greater than 500 ms and co-occurs with speaker change. We use these compositional and positional features to construct searches across different spoken corpora held within the Australian National Corpus in order to identify further possible examples of this candidate practice, thereby demonstrating the relevance of this approach for accessing data in conversation analytic research. We suggest that the advantage of an explicitly combinatorial approach to identifying practices, and the actions accomplished through them, is that it enables us to go beyond analysing them in single, isolated datasets, as well as opening up hitherto understudied practices for further investigation.

We present a novel framework for finding complex activities matching user-described queries in cluttered surveillance videos. The wide diversity of queries coupled with unavailability of annotated activity data limits our ability to train activity models. To bridge the semantic gap we propose to let users describe an activity as a semantic graph with object attributes and inter-object relationships associated with nodes and edges, respectively. We learn node/edge-level visual predictors during training and, at test-time, propose to retrieve activity by identifying likely locations that match the semantic graph. We formulate a novel CRF based probabilistic activity localization objective that accounts for mis-detections, mis-classifications and track-losses, and outputs a likelihood score for a candidate grounded location of the query in the video. We seek groundings that maximize overall precision and recall. To handle the combinatorial search over all high-probability groundings, we propose a highest precision subgraph matching algorithm. Our method outperforms existing retrieval methods on benchmarked datasets., Comment: 1520-9210 (c) 2018 IEEE. This paper has been accepted by IEEE Transactions on Multimedia. Print ISSN: 1520-9210. Online ISSN: 1941-0077. Preprint link is https://ieeexplore.ieee.org/document/8438958/

In recent years, some attention has been driven to modeling, simulation, and optimization techniques capable of representing and improving discrete event systems. These techniques can support decision making helping to determine the best scenario on a combinatorial search space with stochastic variables. This paper presents findings from a systematic literature review of discrete simulation-based optimization applied to industrial engineering problems. It indicates the most frequent contexts, problems, methods, tools, and intended results of discrete-simulation based studies published in the last 25 years (1991–2016) in scientific journals and conference proceedings. The four research questions presented a scenario to help practitioners and researchers to develop simulation optimization projects for industrial engineering problems. A conclusion presented the gap and prospects found during the writing of the research.

As the rapid development of natural-gas fired units (NGUs), power systems begin to rely more on a natural gas system to supply the primary fuel. On the other hand, natural gas system contingency might cause the nonavailability of NGUs and inevitably jeopardize power system security. To address this issue, this paper studies security-constrained joint expansion planning problems for this combined energy system. We develop a computationally efficient mixed-integer linear programming (MILP) approach that simultaneously considers N-1 contingency in both natural gas system and electricity power system. To reduce the combinatorial search space of MILP models, an extension of a reduced disjunctive model is proposed to decrease the numbers of binary and continuous variables as well as constraints. The involving nonlinear terms in N-1 constraints are exactly linearized without sacrificing any optimality. Numerical results on two typical integrated energy systems demonstrate the necessity of extending N-1 criterion to the whole network of a combined energy system. Experimental results also show that compared with the conventional approach, our proposed MILP approach achieves a great computational performance improvement in solving security-constrained co-optimization expansion planning problems.

Semi-bent Boolean functions are interesting from a cryptographic standpoint, since they possess several desirable properties such as having a low and flat Walsh spectrum, which is useful to resist linear cryptanalysis. In this paper, we consider the search of semi-bent functions through a construction based on cellular automata (CA). In particular, the construction defines a Boolean function by computing the XOR of all output cells in the CA. Since the resulting Boolean functions have the same algebraic degree of the CA local rule, we devise a combinatorial algorithm to enumerate all quadratic Boolean functions. We then apply this algorithm to exhaustively explore the space of quadratic rules of up to 6 variables, selecting only those for which our CA-based construction always yields semi-bent functions of up to 20 variables. Finally, we filter the obtained rules with respect to their balancedness, and remark that the semi-bent functions generated through our construction by the remaining rules have a constant number of linear structures., Comment: 12 pages, 1 figure, submitted to ACRI 2020

In this paper, we address the exact solution of the vertex bisection problem (VBP). We propose two novel B&B algorithms to solve VBP, which include new upper and lower bound constructive heuristics, and an efficient strategy to explore the combinatorial search space. The computational results show that the proposed algorithms clearly outperforms the state-of-the-art B&B algorithm in quality and efficiency. The two proposed B&B versions differ in the exploration strategy and the storage of the search tree. Also, we provide four new solutions, previously unknown. We consider that the main contributions of this work can be adapted to solve combinatorial problems in other related domains.

Serving ML prediction pipelines spanning multiple models and hardware accelerators is a key challenge in production machine learning. Optimally configuring these pipelines to meet tight end-to-end latency goals is complicated by the interaction between model batch size, the choice of hardware accelerator, and variation in the query arrival process.In this paper we introduce InferLine, a system which provisions and manages the individual stages of prediction pipelines to meet end-to-end tail latency constraints while minimizing cost. InferLine consists of a low-frequency combinatorial planner and a high-frequency auto-scaling tuner. The low-frequency planner leverages stage-wise profiling, discrete event simulation, and constrained combinatorial search to automatically select hardware type, replication, and batching parameters for each stage in the pipeline. The high-frequency tuner uses network calculus to auto-scale each stage to meet tail latency goals in response to changes in the query arrival process. We demonstrate that InferLine outperforms existing approaches by up to 7.6x in cost while achieving up to 34.5x lower latency SLO miss rate on realistic workloads and generalizes across state-of-the-art model serving frameworks.