Identification of design motifs with pattern matching algorithms

Design patterns are important in software maintenance because they help in understanding and re-engineering systems. They propose design motifs, solutions to recurring design problems. The identification of occurrences of design motifs in large systems consists of identifying classes whose structure and organization match exactly or approximately the structure and organization of classes as suggested by the motif. We adapt two classical approximate string matching algorithms based on automata simulation and bit-vector processing to efficiently identify exact and approximate occurrences of motifs. We then carry out two case studies to show the performance, precision, and recall of our algorithms. In the first case study, we assess the performance of our algorithms on seven medium-to-large systems. In the second case study, we compare our approach with three existing approaches (an explanation-based constraint approach, a metric-enhanced explanation-based constraint approach, and a similarity scoring approach) by applying the algorithms on three small-to-medium size systems, JHotDraw, Juzzle, and QuickUML. Our studies show that approximate string matching based on bit-vector processing provides efficient algorithms to identify design motifs.     

Template-based program verification and program synthesis

Program verification is the task of automatically generating proofs for a program’s compliance with a given specification. Program synthesis is the task of automatically generating a program that meets a given specification. Both program verification and program synthesis can be viewed as search problems, for proofs and programs, respectively. For these search problems, we present approaches based on user-provided insights in the form of templates. Templates are hints about the syntactic forms of the invariants and programs, and help guide the search for solutions. We show how to reduce the template-based search problem to satisfiability solving, which permits the use of off-the-shelf solvers to efficiently explore the search space. Template-based approaches have allowed us to verify and synthesize programs outside the abilities of previous verifiers and synthesizers. Our approach can verify and synthesize difficult algorithmic textbook programs (e.g., sorting and dynamic programming-based algorithms) and difficult arithmetic programs.     

Bandwidth Efficient String Reconciliation Using Puzzles

Of considerable interest in recent years has been the problem of exchanging correlated data with minimum communication. We thus consider the problem of exchanging two similar strings held by different hosts. Our approach involves transforming a string into a multiset of substrings that are reconciled efficiently using known multiset reconciliation algorithms, and then put back together on a remote host using tools from graph theory. We present analyses, experiments, and results to show that the communication complexity of our approach for high-entropy data compares favorably to existing algorithms including rsync, a widely-used string reconciliation engine. We also quantify the trade-off between communication and the computation complexity of our approach     

Automated String Constraints Solving for Programs Containing String Manipulation Functions

The ability to solve various constraints is a principal factor of automatic constraint solvers. Most object-oriented languages treat a character string as a primitive data type which is manipulated by string library functions. Most constraint solvers have limitations on their input constraints, such as strong restrictions on the expressiveness of constraints or lack of the ability to solve hybrid constraints. These limitations hinder applying automated constraint solvers on program analysis techniques for programs containing strings and string manipulation functions. We propose an approach to automatically solve program constraints involving strings and string manipulation functions. Based on the character array model, we design a constraint language which contains primitive operations to precisely describe the constraints of commonly used string manipulation functions. The translated string constraints together with numeric constraints are then solved by a two-phase test generation procedure: firstly, a partial solution is obtained to satisfy the arithmetic constraints of the position variables, and the solution is utilized to simplify the string constraints into pure character array constraints; secondly, the pure array constraints are solved by an off-the-shelf array-specific theory based constraint solver. We integrate the approach into an automated testing tool to support the generation of string test cases, and then perform experiments. The results of the experiments prove that the integration of the proposed approach promotes the testing coverage of the existing testing tool, and the integrated tool has an advantage of handling specific string manipulation functions compared with an existing string solver.     

The distributed constraint satisfaction problem: formalization andalgorithms

We develop a formalism called a distributed constraint satisfaction problem (distributed CSP) and algorithms for solving distributed CSPs. A distributed CSP is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various application problems in distributed artificial intelligence can be formalized as distributed CSPs. We present our newly developed technique called asynchronous backtracking that allows agents to act asynchronously and concurrently without any global control, while guaranteeing the completeness of the algorithm. Furthermore, we describe how the asynchronous backtracking algorithm can be modified into a more efficient algorithm called an asynchronous weak-commitment search, which can revise a bad decision without exhaustive search by changing the priority order of agents dynamically. The experimental results on various example problems show that the asynchronous weak-commitment search algorithm is, by far more, efficient than the asynchronous backtracking algorithm and can solve fairly large-scale problems     

Satisfying constraint sets through convex envelopes

In this article, we present a general representation for constraint satisfaction problems with disjunctive relations called cluster constraint systems (CCS). For this representation, we develop a novel and simple approach for solving CCSs using convex envelopes. These envelopes can be used to decompose the feasible space of the CCS through convex approximations. We explore interval reasoning as a case study of CCS. Our experimental results demonstrate that such CCS can be effectively and efficiently solved through convex enveloping with very modest branching requirements in comparison to other generic as well as specialized algorithms for interval reasoning. In fact, convex enveloping solves significantly more cases and more efficiently than other methods used in our test bed.     

Local search with constraint propagation and conflict-based heuristics

Search algorithms for solving csp (Constraint Satisfaction Problems) usually fall into one of two main families: local search algorithms and systematic algorithms. Both families have their advantages. Designing hybrid approaches seems promising since those advantages may be combined into a single approach. In this paper, we present a new hybrid technique. It performs a local search over partial assignments instead of complete assignments, and uses filtering techniques and conflict-based techniques to efficiently guide the search. This new technique benefits from both classical approaches: a priori pruning of the search space from filtering-based search and possible repair of early mistakes from local search. We focus on a specific version of this technique: tabu decision-repair. Experiments done on open-shop scheduling problems show that our approach competes well with the best highly specialized algorithms.     

Improved filtering for weighted circuit constraints

We study the weighted circuit constraint in the context of constraint programming. It appears as a substructure in many practical applications, particularly routing problems. We propose a domain filtering algorithm for the weighted circuit constraint that is based on the 1-tree relaxation of Held and Karp. In addition, we study domain filtering based on an additive bounding procedure that combines the 1-tree relaxation with the assignment problem relaxation. Experimental results on Traveling Salesman Problem instances demonstrate that our filtering algorithms can dramatically reduce the problem size. In particular, the search tree size and solving time can be reduced by several orders of magnitude, compared to existing constraint programming approaches. Moreover, for medium-size problem instances, our method is competitive with the state-of-the-art special-purpose TSP solver Concorde.     

Functional synthesis for linear arithmetic and sets

Synthesis of program fragments from specifications can make programs easier to write and easier to reason about. To integrate synthesis into programming languages, synthesis algorithms should behave in a predictable way—they should succeed for a well-defined class of specifications. To guarantee correctness and applicability to software (and not just hardware), these algorithms should also support unbounded data types, such as numbers and data structures. To obtain appropriate synthesis algorithms, we propose to generalize decision procedures into predictable and complete synthesis procedures. Such procedures are guaranteed to find the code that satisfies the specification if such code exists. Moreover, we identify conditions under which synthesis will statically decide whether the solution is guaranteed to exist and whether it is unique. We demonstrate our approach by starting from a quantifier elimination decision procedure for Boolean algebra of set with Presburger arithmetic and transforming it into a synthesis procedure. Our procedure also works in the presence of parametric coefficients. We establish results on the size and the efficiency of the synthesized code. We show that such procedures are useful as a language extension with implicit value definitions, and we show how to extend a compiler to support such definitions. Our constructs provide the benefits of synthesis to programmers, without requiring them to learn new concepts, give up a deterministic execution model, or provide code skeletons.     

GC-MCR: Directed Graph Constraint-guided Concurrent Bug Detection Method

Constraint solving has been applied to many domains of program analysis and is further used in concurrent program analysis. Concurrent programs have been widely used with the rapid development of multi-core processors. However, concurrent bugs threaten the security and reliability of concurrent programs, and thus it is of great importance to detect concurrent bugs. The explosion of thread interleaving caused by the uncertainty of the execution of concurrent program threads brings some challenges to the detection of concurrent bugs. Existing concurrent defect detection algorithms reduce the exploration cost in the state space of concurrent programs by reducing invalid thread interleaving. For example, the maximal causal model algorithm transforms the state space exploration problem of concurrent programs into a constraint solving problem. However, it will produce a large number of redundant and conflicting constraints during constraint construction, which greatly prolongs the time of constraint solving, increases the number of constraint solver calls, and reduces the exploration efficiency of concurrent program state space. Thus, this study proposes a directed graph constraint-guided maximal causality reduction method, called GC-MCR. This method aims to improve the speed of constraint solving and the efficiency of the state space exploration of concurrent programs by filtering and reducing constraints using directed graphs. The experimental results show that the GC-MCR method can effectively optimize the expression of constraints, so as to improve the solving speed of the constraint solver and reduce the number of solver calls. Compared with the existing J-MCR method, GC-MCR can significantly improve the detection efficiency of concurrent program bugs without reducing the detection ability of concurrent bugs, and the test time on 38 groups of concurrent test programs widely used by existing research methods can be reduced by 34.01% on average.     

A Reinforcement Learning Algorithm Based on Policy Iteration for Average Reward: Empirical Results with Yield Management and Convergence Analysis

We present a Reinforcement Learning (RL) algorithm based on policy iteration for solving average reward Markov and semi-Markov decision problems. In the literature on discounted reward RL, algorithms based on policy iteration and actor-critic algorithms have appeared. Our algorithm is an asynchronous, model-free algorithm (which can be used on large-scale problems) that hinges on the idea of computing the value function of a given policy and searching over policy space. In the applied operations research community, RL has been used to derive good solutions to problems previously considered intractable. Hence in this paper, we have tested the proposed algorithm on a commercially significant case study related to a real-world problem from the airline industry. It focuses on yield management, which has been hailed as the key factor for generating profits in the airline industry. In the experiments conducted, we use our algorithm with a nearest-neighbor approach to tackle a large state space. We also present a convergence analysis of the algorithm via an ordinary differential equation method.     

Optimization of heuristic search using recursive algorithm selection and reinforcement learning

The traditional approach to computational problem solving is to use one of the available algorithms to obtain solutions for all given instances of a problem. However, typically not all instances are the same, nor a single algorithm performs best on all instances. Our work investigates a more sophisticated approach to problem solving, called Recursive Algorithm Selection, whereby several algorithms for a problem (including some recursive ones) are available to an agent that makes an informed decision on which algorithm to select for handling each sub-instance of a problem at each recursive call made while solving an instance. Reinforcement learning methods are used for learning decision policies that optimize any given performance criterion (time, memory, or a combination thereof) from actual execution and profiling experience. This paper focuses on the well-known problem of state-space heuristic search and combines the A* and RBFS algorithms to yield a hybrid search algorithm, whose decision policy is learned using the Least-Squares Policy Iteration (LSPI) algorithm. Our benchmark problem domain involves shortest path finding problems in a real-world dataset encoding the entire street network of the District of Columbia (DC), USA. The derived hybrid algorithm exhibits better performance results than the individual algorithms in the majority of cases according to a variety of performance criteria balancing time and memory. It is noted that the proposed methodology is generic, can be applied to a variety of other problems, and requires no prior knowledge about the individual algorithms used or the properties of the underlying problem instances being solved.     

基于自变量简约的大规模稀疏多目标优化

现有的大多数进化算法在求解大规模优化问题时性能会随决策变量维数的增长而下降。通常,多目标优化的Pareto有效解集是自变量空间的一个低维流形,该流形的维度远小于自变量空间的维度。鉴于此,提出一种基于自变量简约的多目标进化算法求解大规模稀疏多目标优化问题。该算法通过引入局部保持投影降维,保留原始自变量空间中的局部近邻关系,并设计一个归档集,将寻找到的非劣解存入其中进行训练,以提高投影的准确性。将该算法与四种流行的多目标进化算法在一系列测试问题和实际应用问题上进行了比较。实验结果表明,所提算法在解决稀疏多目标问题上具有较好的效果。因此,通过自变量简约能降低问题的求解难度,提高算法的搜索效率,在解决大规模稀疏多目标问题方面具有显著的优势。     

Nogood-FC for solving partitionable constraint satisfaction problems

Many real problems can be naturally modelled as constraint satisfaction problems (CSPs). However, some of these problems are of a distributed nature, which requires problems of this kind to be modelled as distributed constraint satisfaction problems (DCSPs). In this work, we present a distributed model for solving CSPs. Our technique carries out a partition over the constraint network using a graph partitioning software; after partitioning, each sub-CSP is arranged into a DFS-tree CSP structure that is used as a hierarchy of communication by our distributed algorithm. We show that our distributed algorithm outperforms well-known centralized algorithms solving partitionable CSPs.     

Boosting Search with Variable Elimination in Constraint Optimization and Constraint Satisfaction Problems

There are two main solving schemas for constraint satisfaction and optimization problems: i) search, whose basic step is branching over the values of a variables, and ii) dynamic programming, whose basic step is variable elimination. Variable elimination is time and space exponential in a graph parameter called induced width, which renders the approach infeasible for many problem classes. However, by restricting variable elimination so that only low arity constraints are processed and recorded, it can be effectively combined with search, because the elimination of variables may reduce drastically the search tree size.In this paper we introduce BE-BB(k), a hybrid general algorithm that combines search and variable elimination. The parameter k controls the tradeoff between the two strategies. The algorithm is space exponential in k. Regarding time, we show that its complexity is bounded by k and a structural parameter from the constraint graph. We provide experimental evidence that the hybrid algorithm can outperform state-of-the-art algorithms in constraint satisfaction, Max-CSP and Weighted CSP. Especially in optimization tasks, the advantage of our approach over plain search can be overwhelming.     

Visual search tree profiling

Understanding how the search space is explored for a given constraint problem – and how it changes for different models, solvers or search strategies – is crucial for efficient solving. Yet programmers often have to rely on the crude aggregate measures of the search that are provided by solvers, or on visualisation tools that can show the search tree, but do not offer sophisticated ways to navigate and analyse it, particularly for large trees. We present an architecture for profiling a constraint programming search that is based on a lightweight instrumentation of the solver. The architecture combines a visualisation of the search tree with various tools for convenient navigation and analysis of the search. These include identifying repeated subtrees, high-level abstraction and navigation of the tree, and the comparison of two search trees. The resulting system is akin to a traditional program profiler, which helps the user to focus on the parts of the execution where an improvement to their program would have the greatest effect.     

Learning context-free grammars using tabular representations

We present a novel algorithm using new hypothesis representations for learning context-free grammars from a finite set of positive and negative examples. We propose an efficient hypothesis representation method which consists of a table-like data structure similar to the parse table used in efficient parsing algorithms for context-free grammars such as Cocke-Younger-Kasami algorithm. By employing this representation method, the problem of learning context-free grammars from examples can be reduced to the problem of partitioning the set of nonterminals. We use genetic algorithms for solving this partitioning problem. Further, we incorporate partially structured examples to improve the efficiency of our learning algorithm, where a structured example is represented by a string with some parentheses inserted to indicate the shape of the derivation tree of the unknown grammar. We demonstrate some experimental results using these algorithms and theoretically analyse the completeness of the search space using the tabular method for context-free grammars.     

Ants can solve constraint satisfaction problems

We describe a novel incomplete approach for solving constraint satisfaction problems (CSPs) based on the ant colony optimization (ACO) metaheuristic. The idea is to use artificial ants to keep track of promising areas of the search space by laying trails of pheromone. This pheromone information is used to guide the search, as a heuristic for choosing values to be assigned to variables. We first describe the basic ACO algorithm for solving CSPs and we show how it can be improved by combining it with local search techniques. Then, we introduce a preprocessing step, the goal of which is to favor a larger exploration of the search space at a lower cost, and we show that it allows ants to find better solutions faster. Finally, we evaluate our approach on random binary problems