Search

This paper is aimed at improving the solution efficiency of convex MINLP problems in which the bottleneck lies in the combinatorial search for the 0–1 variables. An LP/NLP based branch and bound algorithm is proposed in which the explicit solution of an MILP master problem is avoided at each major iteration. Instead, the master problem is defined dynamically during the tree search to reduce the number of nodes that need to be enumerated. A branch and bound search is conduced to predict lower bounds by solving LP subproblems until feasible integer solutions are found. At these nodes nonlinear programming subproblems are solved, providing upper bounds and new linear approximations which are used to tighten the linear representation of the open nodes in the search tree. To reduce the size of the LP subproblems, new types of linear approximations are proposed which exploit linear substructures in the MINLP problem. Preliminary numerical results on several test problems are reported which show that the expense of solving the MI need to be enumerated, while in most cases the number of NLP subproblems to be solved remains the same.

In this paper, we model search algorithms with meta-control, allowing resource constraints, approximation, and parallel processing to be incorporated easily in the search process. The basic building block of the model is a hierarchical search process (HSP) consisting of context-free and context-sensitive grammars classified according to problem-independent and problem-dependent parts. The context-sensitive components are used mainly for evaluating decision parameters and in ordering production rules in the context-free grammar. The execution of the grammars for given initial conditions may invoke other HSPs already defined in the system. We describe ISE (acronym for Integrated Search Environment), a tool that implements hierarchical searches with meta-control. By separating the problem-dependent and problem-independent components in ISE, new search methods based on a combination of existing methods can be developed easily by coding a single master control program. Further, new applications solved by searches can be developed by coding the problem-dependent parts and reusing the problem-independent parts already developed. We describe the organization of ISE and present experiments carried out on the system.

Almost all successful exact approaches to hard combinatorial optimization problems are firmly rooted in the theory of a single canonical model format—linear integer programming. Some heuristic or approximate strategies for hard combinatorial problems are also structured around linear programming, but many of the most effective, including greedy and local search schemes have no close ties to the linear format.This paper introduces a new structure we call a paroid we believe has the potential to remedy these difficulties by providing a purely combinatorial canonical format in which discrete problems can be “naturally” modeled, and in which notions of combinatorial search can be studied and compared. A paroid is formed by a matroid and a partition of the underlying ground set into “all or nothing” parity sets. We offer as exemplars fairly natural paroid optimization formulations for seven classical combinatorial problems. Then a structural hierarchy of paroids is introduced and many of the seven models are seen to fall in the easiest class. We show that standard matroid theory can be extended with natural notions of paroid duals and minors, and investigate invariances over our classes. Finally, we briefly review the results in thecompanion Rardin and Sudit (1988) showing the power of a generic paroid search algorithm to unify a number of quite diverse combinatorial algorithms.

The least squares support vector machine (LS-SVM), like the SVM, is based on the margin-maximization performing structural risk and has excellent power of generalization. In this paper, we consider its use in semisupervised learning. We propose two algorithms to perform this task deduced from the transductive SVM idea. Algorithm 1 is based on combinatorial search guided by certain heuristics while Algorithm 2 iteratively builds the decision function by adding one unlabeled sample at the time. In term of complexity, Algorithm 1 is faster but Algorithm 2 yields a classifier with a better generalization capacity with only a few labeled data available. Our proposed algorithms are tested in several benchmarks and give encouraging results, confirming our approach.

Geometric Particle Swarm Optimization (GPSO) is a recently introduced formal generalization of traditional Particle Swarm Optimization (PSO) that applies naturally to both continuous and combinatorial spaces. Differential Evolution (DE) is similar to PSO but it uses different equations governing the motion of the particles. This paper generalizes the DE algorithm to combinatorial search spaces extending its geometric interpretation to these spaces, analogously as what was done for the traditional PSO algorithm. Using this formal algorithm, Geometric Differential Evolution (GDE), we formally derive the specific GDE for the Hamming space associated with binary strings and present experimental results on a standard benchmark of problems.

This paper studies the difference between Persistent Random Constants (PRC) and Digit Concatenation as methods for generating constants. It has been shown that certain problems have different fitness landscapes depending on how they are represented, independent of changes to the combinatorial search space, thus changing problem difficulty. In this case we show that the method for generating the constants can also influence how hard the problem is for Genetic Programming.

This paper studies the following question: given an instance of the propositional satisfiability problem, a randomized satisfiability solver, and a cluster of n computers, what is the best way to use the computers to solve the instance? Two approaches, simple distribution and search space partitioning as well as their combinations are investigated both analytically and empirically. It is shown that the results depend heavily on the type of the problem (unsatisfiable, satisfiable with few solutions, and satisfiable with many solutions) as well as on how good the search space partitioning function is. In addition, the behavior of a real search space partitioning function is evaluated in the same framework. The results suggest that in practice one should combine the simple distribution and search space partitioning approaches.

We have previously established the existence of decision algorithms with low-degree polynomial running times for a number of difficult combinatorial problems, including many that can be stated in terms of VLSI layout, placement, embedding and routing. In this paper, we turn our attention to the search complexity of these problems. We introduce a general technique, which we term scaffolding, and illustrate how it is useful in the design of efficient search algorithms.

The landscape formalism unites a finite candidate solution set to a neighborhood topology and an objective function. This construct can be used to model the behavior of local search on combinatorial optimization problems. A landscape is elementary when it possesses a unique property that results in a relative smoothness and decomposability to its structure. In this paper we explain elementary landscapes in terms of the expected value of solution components which are transformed in the process of moving from an incumbent solution to a neighboring solution. We introduce new results about the properties of elementary landscapes and discuss the practical implications for search algorithms.

The efficient design of meander line antennas for RFID devices is a significant real-world problem. Traditional manual tuning of antenna designs is becoming impractical for larger problems. Thus the use of automated techniques, in the form of combinatorial search algorithms, is a necessity. Ant colony system (ACS) is a very efficient meta-heuristic that is commonly used to solve path construction problems. Apart from its own native search capacity, ACS can be dramatically improved by combining it with local search strategies. As shown in this paper, applying local search as a form of structure refinement to RFID meander line antennas delivers effective antenna structures. In particular, we use the operator known as backbite, that has had previous application in the construction of self-avoiding walks and compact polymer chains. Moreover, we apply it in a novel, hierarchical manner that allows for good sampling of the local search space. Its use represents a significant improvement on results obtained previously.

International audience; Since their beginning in constraint programming, set solvers have been applied to a wide range of combinatorial search problems, such as bin-packing, set partitioning, circuit design, and Combinatorial Design Problems. In this paper we present and evaluate a new means towards improving the practical reasoning power of Finite Set (FS) constraint solvers to better address such set problems with a particular attention to the challenging symmetrical set problems often cast as Combinato-rial Design Problems (CDPs). While CDPs find a natural formulation in the language of sets, in constraint programming literature, alternative models are often used due to a lack of efficiency of traditional FS solvers. We first identify the main structural components of CDPs that render their modeling suitable to set languages but their solving a technical challenge. Our new prototype solver extends the traditional subset variable domain with lexicographic bounds that better approximate a set domain by satisfying the cardinality restrictions applied to the variable , and allow for active symmetry breaking using ordering constraints. Our contribution includes the formal and practical framework of the new solver implemented on top of a traditional set solver, and an empirical evaluation on benchmark CDPs.

Software testing plays an important role in the life cycle of software development. Because software testing is very costly and tedious, many techniques have been proposed to automate it. One technique that has achieved good results is the use of search algorithms. Because most previous work on search algorithms has been of an empirical nature, there is a need for theoretical results that confirm the feasibility of search algorithms applied to software testing. Such theoretical results might shed light on the limitations and benefits of search algorithms applied in this context. In this paper, we formally analyse the expected runtime of three different search algorithms on the problem of test data generation for an instance of the triangle classification program. The search algorithms that we analyse are random search, hill climbing and alternating variable method. We believe that this is a necessary first step that will lead and help the software engineering community to better understand the role of search based techniques applied to software testing.

Many logic programming based approaches can be used to describe and solve combinatorial search problems. On the one hand there is constraint logic programming which computes a solution as an answer substitution to a query containing the variables of the constraint satisfaction problem. On the other hand there are systems based on stable model semantics, abductive systems, and first order logic model generators which compute solutions as models of some theory. This paper compares these different approaches from the point of view of knowledge representation (how declarative are the programs) and from the point of view of performance (how good are they at solving typical problems)., 15 pages, 3 eps-figures

A common type of DNA variation is called a Single Nucleotide Polymorphism (SNP), where a single position within a DNA sequence is altered from one nucleotide base to another. The problem of identifying disease-associated SNPs has been the subject of extensive research by statisticians. However, less research has been done within the computing community. In this paper, we propose a novel geometrical computing model for the SNP Motif Identification Problem. The purpose of our research is to explore the properties of SNPs in a combinatorial way. We test our algorithm on two real clinical datasets, and give computational results which demonstrate the efficiency and effectiveness of our approach. ©2007 IEEE.

This paper focuses on using beam search, a heuristic search algorithm, for pruning state spaces while generating. The original beam search is adapted to the state space generation setting and two new search variants are devised. The resulting framework encompasses some known algorithms, such as $A^*$. We also report on two case studies based on an implementation of beam search in $\mu$CRL.

AND/OR search spaces are a unifying paradigm for advanced algorithmic schemes for graphical models. The main virtue of this representation is its sensitivity to the structure of the model, which can translate into exponential time savings for search algorithms. In this paper we introduce an AND/OR search algorithm that explores a context-minimal AND/OR search graph in a best-firstmanner for solving 0/1 Integer Linear Programs (0/1 ILP). We also extend to the 0/1 ILP domain the depth-firstAND/OR Branch-and-Bound search with caching algorithm which was recently proposed by [1] for solving optimization tasks in graphical models. The effectiveness of the best-first AND/OR search approach compared to depth-first AND/OR Branch-and-Bound search is demonstrated on a variety of benchmarks for 0/1 ILPs, including instances from the MIPLIB library, real-world combinatorial auctions, random uncapacitated warehouse location problems and MAX-SAT instances.

Answer set programming (ASP) is a form of declarative programming particularly suited to difficult combinatorial search problems. However, it has yet to be used for more than a handful of large-scale applications, which are needed to demonstrate the strengths of ASP and to motivate the development of tools and methodology. This paper describes such a large-scale application, the TOAST (Total Optimisation using Answer Set Technology) system, which seeks to generate optimal machine code for simple, acyclic functions using a technique known as superoptimisation. ASP is used as a scalable computational engine to handle searching over complex, non-regular search spaces, with the experimental results suggesting that this is a viable approach to the optimisation problem and demonstrates the scalability of a variety of solvers.

There are two complementary approaches to playing sums of combinatorial games. They can be characterized as local analysis and global search. Algorithms from combinatorial game theory such as Hotstrat and Thermostrat [2] exploit summary information about each subgame such as its temperature or its thermograph. These algorithms can achieve good play, with a bounded error. Their runtime depends mainly on the complexity of analyzing individual subgames. Most importantly, it is not exponential in global parameters such as the branching factor and the number of moves in the sum game. One problem of these classic combinatorial game algorithms is that they cannot exploit extra available computation time. A global minimax search method such as αβ can determine the optimal result of a sum game. However, the solution cost grows exponentially with the total size of the sum game, even if each subgame by itself is simple. Such an approach does not exploit the independence of subgames. This paper explores combinations of both local and global-level analysis in order to develop locally informed global search algorithms for sum games. The algorithms utilize the subgame structure in order to reduce the runtime of a global αβ search by orders of magnitude. In contrast to methods such as Hotstrat and Thermostrat, the new algorithms exhibit improving solution quality with increasing time limits.

Modern search methods for optimization consider hybrid search metaheuristics those employing general optimizers working together with a problem-specific local search procedure. The hybridism comes from the balancing of global and local search procedures. A challenge in such algorithms is to discover efficient strategies to cover all the search space, applying local search only in actually promising search areas. This paper proposes the Clustering Search (*CS): a generic way of combining search metaheuristics with clustering to detect promising search areas before applying local search procedures. The clustering process aims to gather similar information about the problem at hand into groups, maintaining a representative solution associated to this information. Two applications to combinatorial optimization are examined, showing the flexibility and competitiveness of the method.

The understanding of human behavior in sequential decision tasks is important for economics and socio-psychological sciences. In search tasks, for example when individuals search for the best price of a product, they are confronted in sequential steps with different situations and they have to decide whether to continue or stop searching. The decision behavior of individuals in such search tasks is described by a search strategy. This paper presents a new approach of finding high-quality search strategies by using genetic algorithms (GAs). Only the structure of the search strategies and the basic building blocks (price thresholds and price patterns) that can be used for the search strategies are pre- specified. It is the purpose of the GA to construct search strategies that well describe human search behavior. The search strategies found by the GA are able to predict human behavior in search tasks better than traditional search strategies from the literature which are usually based on theoretical assumptions about human behavior in search tasks. Furthermore, the found search strategies are reasonable in the sense that they can be well interpreted, and generally that means they describe the search behavior of a larger group of individuals and allow some kind of categorization and classification. The results of this study open a new perspective for future research in developing behavioral strategies. Instead of deriving search strategies from theoretical assumptions about human behavior, researchers can directly analyze human behavior in search tasks and find appropriate and high-quality search strategies. These can be used for gaining new insights into the motivation behind human search and for developing new theoretical models about human search behavior.

Graphical models are a powerful representation framework for automated reasoning tasks. These models use graphs to capture conditional independencies between variables, allowing for a concise representation of the knowledge. Optimization tasks defined within this framework are typically tackled with either search or inference. Search methods are time exponential in the number of variables and can operate in linear space. Inference algorithms are time and space exponential in the tree width of the problem. This potentially higher space complexity makes these methods impractical. The AND/OR search space for graphical models is a newly introduced framework for search that is sensitive to the independencies in the model, often resulting in exponentially reduced complexities. The AND/OR search is based on a pseudo-tree which expresses independencies between variables, resulting in a search tree exponential in the depth of the pseudo-tree, rather than the number of variables. The AND/OR Branch-and-Bound algorithm (AOBB) is a new search method that explores the AND/OR search tree for solving optimization tasks in graphical models. In this paper we extend the algorithm for solving combinatorial optimization problems from the class of Mixed Integer Linear Programs (MILP). A MILP instance is a linear program where some of the decision variables are constrained to have only integer values at the optimal solution (we consider only binary integer variables). AOBB can be readily adapted for solving this class of optimization problems by arranging the integer variables into a start pseudo-tree and, then, traversing the corresponding AND/OR search tree. This rather straightforward extension can be further improved. We introduce a dynamic version of AOBB which uses a recursive decomposition of the problem, based on hypergraph separators. The hypergraph of a MILP instance has a vertex for each constraint and a hyperedge, which corresponds to a variable, connects all the constraints that contain that variable. A separator translates into a subset of variables that, when instantiated, decompose the problem into independent components. The algorithm traverses an AND/OR search tree based on a pseudo-tree which is recomputed dynamically at each search tree node using the hypergraph separator of the respective subproblem. The search process is guided in both cases by lower-bounding heuristic estimates computed at each node by solving the linear relaxation (i.e. ignoring the integrality restrictions) of the subproblem rooted at that node. Preliminary evaluation of the structural properties of several hard problem instances from the MIPLIB2003 library showed promise that the new AND/OR search schemes can improve significantly over the traditional OR tree search approach. Finally, we mention that more advanced strategies developed in the recent years for integer programming, such as the branch-and-cut scheme, can be readily adapted to exploit the AND/OR structural paradigm.

Meta-heuristics is a new paradigm that aims to obtain an approximate solution within a feasible computation time. In the meta-heuristics, Tabu Search is one of the most effective algorithms for solving combinatorial optimization problems. While the intensification of Tabu Search is powerful, the diversification of Tabu Search is not powerful. This paper proposes an algorithm - Multi Criteria Tabu Search coordinating the intensification and the diversification based on a Proximate Optimality Principle (POP) - which has several advantages for solving combinatorial optimization problems. The proposed algorithm is applied to some traveling salesman problems which are typical combinatorial optimization problems in order to verify the performance of the proposed algorithm.

MAX-SAT, the optimisation variant of the satisfiability problem in propositional logic, is an important and widely studied combinatorial optimisation problem with applications in AI and other areas of computing science. In this paper, we present a new stochastic local search (SLS) algorithm for MAX-SAT that combines Iterated Local Search and Tabu Search, two well-known SLS methods that have been successfully applied to many other combinatorial optimisation problems. The performance of our new algorithm exceeds that of current state-of-the-art MAX-SAT algorithms on various widely studied classes of unweighted and weighted MAX-SAT instances, particularly for Random-3-SAT instances with high variance clause weight distributions. We also report promising results for various classes of structured MAX-SAT instances.

This paper introduces a method for selecting subsets of relevant statistical features in biological shape-based classification problems. The method builds upon existing feature selection methodology by introducing a heuristic that favors the geometric locality of the selected features. This heuristic effectively reduces the combinatorial search space of the feature selection problem. The new method is tested on synthetic data and on clinical data from a study of hippocampal shape in schizophrenia. Results on clinical data indicate that features describing the head of the right hippocampus are most relevant for discrimination.

The paper presents recent results on the application of soft computing techniques for predictive modelling in the built sector. More specifically, an air-conditioned zone (Anglesea Building, University of Portsmouth), a naturally ventilated room (Portland Building, University of Portsmouth), and an endothermic building (St Catherine’s Lighthouse, Isle of Wight) are considered. The zones are subjected to occupancy effects and external disturbances which are difficult to predict in a quantitative way and hence the soft computing approach seems to be a better alternative. In fact, the overall complexity of the problem domain makes the modelling of the internal climate in buildings a difficult task which is not always carried out in a satisfactory way by traditional deterministic and stochastic methods. The approach adopted uses fuzzy logic for modelling, as well as neural networks for adaptation and genetic algorithms for optimisation of the fuzzy model. The latter is of the Takagi-Sugeno type and it is built by subtractive clustering as a result of which the initial values of the antecedent non-linear membership functions and the consequent linear algebraic equations parameters are determined. A method of a combinatorial search over all possible fuzzy model structures for a specified plant order is presented. The model parameters are further adjusted by a back-propagation neural network and a real-valued genetic algorithm in order to obtain a better fit to the measured data. Modelling results with actual data from the three buildings are presented where the initial (fuzzy) and the final (fuzzy-neuro and fuzzy-genetic) models are shown.

This paper proposes a new method for searching two-valued (binary) game trees in games like chess or Go. Lambda-search uses null-moves together with different orders of threat-sequences (so-called lambda-trees), focusing the search on threats and threat-aversions, but still guaranteeing to find the minimax value (provided that the game-rules allow passing or zugzwang is not a motive). Using negligible working memory in itself, the method seems able to offer a large relative reduction in search space over standard alpha-beta comparable to the relative reduction in search space of alpha-beta over minimax, among other things depending upon how non-uniform the search tree is. Lambda-search is compared to other resembling approaches, such as null-move pruning and proof-number search, and it is explained how the concept and context of different orders of lambda-trees may ease and inspire the implementation of abstract game-specific knowledge. This is illustrated on open-space Go block tactics, distinguishing between different orders of ladders, and offering some possible grounding work regarding an abstract formalization of the concept of relevancy-zones (zones outside of which added stones of any colour cannot change the status of the given problem).

Many combinatorial search problems can be expressed as 'constraint satisfaction problems'. This class of problems is known to be NP-hard in general, but a number of restricted constraint classes have been identified which ensure tractability. This paper presents the first general results on combining tractable constraint classes to obtain larger, more general, tractable classes. We give examples to show that many known examples of tractable constraint classes, from a wide variety of different contexts, can be constructed from simpler tractable classes using a general method. We also construct several new tractable classes that have not previously been identified.

Many combinatorial search problems can be expressed as 'constraint satisfaction problems', and this class of problems is known to be NP-complete in general. In this paper we investigate 'disjunctive constraints', that is, constraints which have the form of the disjunction of two constraints of specified types. We show that when the constraint types involved in the disjunction have a certain property, which we call 'independence', and when a certain restricted class of problems is tractable, then the class of all problems involving these disjunctive constraints is tractable. We give examples to show that many known examples of tractable constraint classes arise in this way, and derive new tractable classes which have not previously been identified.

Alpha-Beta has been the algorithm of choice for game-tree search for over three decades. Its success is largely attributable to a variety of enhancements to the basic algorithm that can dramatically improve the search efficiency. Although state-ofthe-art game-playing programs build trees that are close in size to the minimal Alpha-Beta search tree, this paper shows that there is still room for improvement. Three new enhancements are presented: best-first Alpha-Beta search, better use of transpositions, and improvingaspiration search under real-time constraints. Measurements show that these improvements can reduce search effort by 35%.

Many decision problems contain, in some form, a NP-hard combinatorial problem. Therefore decision support systems have to solve such combinatorial problems in a reasonable time. Many combinatorial problems can be solved by a search method. The search methods used in decision support systems have to be robust in the sense that they can handle a large variety of (user defined) constraints and that they allow user interaction, i.e. they allow a decision maker to control the search process manually. In this paper we show how Markov decision processes can be used to guide a random search process. We first formulate search problems as a special class of Markov decision processes such that the search space of a search problem is the state space of the Markov decision process. In general it is not possible to compute an optimal control procedure for these Markov decision processes in a reasonable time. We therefore, define several simplifications of the original problem that have much smaller state spaces. For these simplifications, decompositions and abstractions, we find optimal strategies and use the exact solutions of these simplified problems to guide a randomized search process. The search process selects states for further search at random with probabilities based on the optimal strategies of the simplified problems. This randomization is a substitute for explicit backtracking and avoids problems with local extrema. These randomized search procedures are repeated as long as we have time to solve the problem. The best solution of those generated during that time is accepted. We illustrate the approach with two examples: the N-puzzle and a job shop scheduling problem.

Many combinatorial search problems may be expressed as constraint satisfaction problems, and this class of problems is known to be NP-complete in general. In this paper we examine restricted classes of constraints which lead to tractable problems. We show that all known classes with this property may be characterized by a simple algebraic closure condition. Using this condition provides a uniform test to establish whether a given set of constraints falls into any of the known tractable classes, and may therefore be solved efficiently.

Generally, mathematical programming for heat exchanger network (HEN) design uses variables resulting from a decomposition of the temperature range in intervals, based on potential pinch points. In this paper an approach using only lumped variables is presented. It reintroduces the information that is involved in the decomposition in intervals, by means of additional constraints. As a result, smaller and more flexible models involving the minimum number of required continuous variables, are available. This is advantageous especially when many iterative calculations should be carried out, e.g. in combinatorial search procedures. To demonstrate this approach, two cases have been worked out.

Branch-and-bound algorithms are organized and intelligently structured searches of solutions in a combinatorially large problem space. In this paper, we propose an approximate stochastic model of branch-and-bound algorithms with a best-first search. We have estimated the average memory space required and have predicted the average number of subproblems expanded before the process terminates. Both measures are exponentials of sublinear exponent. In addition, we have also compared the number of subproblems expanded in a best-first search to that expanded in a depth-first search. Depth-first search has been found to have computational complexity comparable to best-first search when the lower-bound function is very accurate or very inaccurate; otherwise, best-fit search is usually better. The results obtained are useful in studying the efficient evaluation of branch-and-bound algorithms in a virtual memory environment. They also confirm that approximations are very effective in reducing the total number of iterations.

One of the best studied problems in combinatorial search theory concerns the selection of the s th largest element out of an unknown linear order. In this paper, the corresponding problem, how to find the s th and t th largest elements, is treated. Two general lower bounds and some upper bounds are derived, and it is shown that an algorithm selecting any two elements (whatever their positions) can never be faster than selection of the top two elements, thereby answering a question of G. Katona. Some remarks on recognition and asymptotics are added.

In, this paper we argue that if search procedures are to use problem-specific information to direct a search, then they must have complete control over the deductive process. This includes the freedom to select any pair of clauses to interact as well as the freedom to select the literals upon which to attempt the interaction. We give examples to indicate the nature of inference rules which are incompatible with such search procedures. We then present a framework for a search procedure to indicate where problem-specific information may be utilized. Finally, we augment the search procedure to prevent the generation of certain redundant inferences. The augmentation makes use of lemmas to avoid replicating deduction sequences in solving multiple instances of the same subproblem at distinct places in the search space.

The major problem in solving combinatorial optimization problems is the huge size of the search space. To explore the search space in a reasonable time, using smart search algorithms is inevitable. One of the main difficulties in implementing search methods is the lack of a uniform, high-level template for all search paradigms. In this paper, we propose a high-level, parametric template suitable for modeling languages which covers both tree search and local search.

Artificial intelligence (AI) research has developed an extensive collection of methods to solve state-space problems. Using the challenging domain of Sokoban, this paper studies the effect of general search enhancements on program performance. We show that the current state of the art in AI generally requires a large research and programming effort to use domain-dependent knowledge to solve even moderately complex problems in such difficult domains. The application of domain-specific knowledge to exploit properties of the search space can result in large reductions in the size of the search tree, often several orders of magnitude per search enhancement. This application-specific knowledge is discovered and applied using application-independent search enhancements. Understanding the effect of these enhancements on the search leads to a new taxonomy of search enhancements, and a new framework for developing single-agent search applications. This is used to illustrate the large gap between what is portrayed in the literature versus what is needed in practice.

In recent years, numerous studies have observed that many hard combinatorial decision problems exhibit behaviour described as a ‘phase-transition’. This is the phenomenon whereby typical instances of a problem display a dramatic shift in certain characteristics as some parameter of the instances is varied. Such characteristics include the likelihood of an instance having a solution and the time taken by a search algorithm. The apparent pervasiveness of phase-transitions in hard combinatorial search problems has led to contrasting claims being advanced concerning to what extent all NP-complete problems exhibit phase-transitions. The established importance of exploiting phase-transition effects in the design of search heuristics provides a strong motivation for assessing how valid such claims may be. In this paper we argue that questions concerning the generality of phase-transition phenomena are, at present, ill-defined. In order to address this difficulty, we propose and examine rigorous complexity-theoretic models of the statement ‘the decision problem D has a phase-transition’. Within these models it is proved that for certain ‘natural’ definitions contrasting results about phase-transition behaviour can be proved.

Consider the following generalization of the sequential group testing problem for 2 defective items, which is suggested by Aigner (1988) in [1]: Suppose a graph G contains one defective edge e∗. Find the endpoints of e∗ by testing whether a subset of vertices of cardinality at most 2 contains at least one of the endpoints of e∗ or not. What is then the minimum number c2(G) of tests, which are needed in the worst case to identify e∗?In Gerzen (2009) [10], this problem was partially solved by deriving sharp lower and upper bounds for c2(G). In addition, it was proved that the determination of c2(G) is an NP-complete problem. Among others, it was shown that the inequality |E|≤4(c2−12)+4=2c22−6c2+8 holds for graphs with 2-complexity c2 and the edge set E. In the present paper, we study the class of graphs for which this inequality is sharp and characterize these graphs in several ways. We suppose that for those graphs the 2-complexity can be computed in polynomial time by means of this characterization.

This paper introduces a new approach to applying hyper-heuristic algorithms to solve combinatorial problems with less effort, taking into account the modelling and algorithm construction process. We propose a unified encoding of a solution and a set of low level heuristics which are domain-independent and which change the solution itself. This approach enables us to address NP-hard problems and generate good approximate solutions in a reasonable time without a large amount of additional work required to tailor search methodologies for the problem in hand. In particular, we focused on solving DNA sequencing by hybrydization with errors, which is known to be strongly NP-hard. The approach was extensively tested by solving multiple instances of well-known combinatorial problems and compared with results generated by meta heuristics that have been tailored for specific problem domains.

The disambiguation of sentences is a combinatorial problem. This paper describes a method for treating it as such, directly, by adapting standard combinatorial search optimizations. Traditional disambiguation heuristics are applied but, instead of being embedded in individual decision procedures for specific types of ambiguities, they contribute to numerical weights that are considered by a single global optimizer. The result is increased power and simpler code. The method is being implemented for a machine translation project, but could be adapted to any natural language system.

Summarization: The Eternity II puzzle is a combinatorial search problem which qualifies as a computational grand challenge. As no known closed form solution exists, its solution is based on exhaustive search, making it an excellent candidate for FPGA-based architectures, in which complex data structures and non-trivial recursion are implemented in hardware. This paper presents such an architecture, which was designed and fully implemented on a Virtex5 FPGA (XUP ML505 board). Despite the serial nature of the recursion, as parallelism can be applied with the initiation of multiple searches, the system shows a measured speedup of 2.6 vs. a high-end multi-core compute server. Παρουσιάστηκε στο: International Conference on Field Programmable Logic and Applications

Small populations are very desirable for reducing the required computational resources in evolutionary optimization of complex real-world problems. Unfortunately, the search performance of small populations often reduces dramatically in a large search space. To addresses this problem, a method to find an optimal search dimension for small populations is suggested in this paper. The basic idea is that the evolutionary algorithm starts with a small search dimension and then the search dimension is increased during the optimization. The search dimension will continue to increase if an increase in the search dimension improves the search performance. Otherwise, the search dimension will be decreased and then kept constant. Through empirical studies on a test problem with an infinite search dimension, we show that the proposed algorithm is able to find the search dimension that is the most efficient for the given population size.

Suppose that the vertices of a graph $G$ are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study the problem of finding a majority vertex (or show that none exists) if we can query edges to learn whether their endpoints have the same or different colors. Denote the least number of queries needed in the worst case by $m(G)$. It was shown by Saks and Werman that $m(K_n)=n-b(n)$, where $b(n)$ is the number of 1's in the binary representation of $n$. In this paper, we initiate the study of the problem for general graphs. The obvious bounds for a connected graph $G$ on $n$ vertices are $n-b(n)\le m(G)\le n-1$. We show that for any tree $T$ on an even number of vertices we have $m(T)=n-1$ and that for any tree $T$ on an odd number of vertices, we have $n-65\le m(T)\le n-2$. Our proof uses results about the weighted version of the problem for $K_n$, which may be of independent interest. We also exhibit a sequence $G_n$ of graphs with $m(G_n)=n-b(n)$ such that $G_n$ has $O(nb(n))$ edges and $n$ vertices., 19 pages

Combinatorial branch and bound searches are a common technique for solving global optimisation and decision problems. Their performance often depends on good search order heuristics, refined over decades of algorithms research. Parallel search necessarily deviates from the sequential search order, sometimes dramatically and unpredictably, e.g. by distributing work at random. This can disrupt effective search order heuristics and lead to unexpected and highly variable parallel performance. The variability makes it hard to reason about the parallel performance of combinatorial searches. This paper presents a generic parallel branch and bound skeleton, implemented in Haskell, with replicable parallel performance. The skeleton aims to preserve the search order heuristic by distributing work in an ordered fashion, closely following the sequential search order. We demonstrate the generality of the approach by applying the skeleton to 40 instances of three combinatorial problems: Maximum Clique, 0/1 Knapsack and Travelling Salesperson. The overheads of our Haskell skeleton are reasonable: giving slowdown factors of between 1.9 and 6.2 compared with a class-leading, dedicated, and highly optimised C++ Maximum Clique solver. We demonstrate scaling up to 200 cores of a Beowulf cluster, achieving speedups of 100x for several Maximum Clique instances. We demonstrate low variance of parallel performance across all instances of the three combinatorial problems and at all scales up to 200 cores, with median Relative Standard Deviation (RSD) below 2%. Parallel solvers that do not follow the sequential search order exhibit far higher variance, with median RSD exceeding 85% for Knapsack.

The linear ordering problem is an NP-hard problem that arises in a variety of applications. Due to its interest in practice, it has received considerable attention and a variety of algorithmic approaches to its solution have been proposed. In this paper we give a detailed search space analysis of available benchmark instance classes that have been used in various researches. The large fitness-distance correlations observed for many of these instances suggest that adaptive restart algorithms like iterated local search or memetic algorithms, which iteratively generate new starting solutions for a local search based on previous search experience, are promising candidates for obtaining high performing algorithms. We therefore experimentally compared two such algorithms and the final experimental results suggest that, in particular, the memetic algorithm is a new state-of-the-art approach to the linear ordering problem.

Optimal observability of continuous Petri Nets consists in deciding the places to be measured (considering that all are measurable) such that the net system is observable and a cost function is minimal. Unfortunately this is not a simple covering problem. The results obtained in the paper are used in the implementation of an algorithm to improve the pure combinatorial search.

International audience; Mission planning for a constellation of Earth observation satellites is a complex problem raising significant technological challenges for tomorrow’s space systems. The large numbers of customers requests and their dynamic introduction in the planning system result in a huge combinatorial search space with a potentially highly dynamical evolution requirements. The techniques used nowadays have several limitations, in particular, it is impossible to dynamically adapt the plan during its construction even for small modifications. Satellites of a constellation are planned in a chronological way instead of a more collective planning which can provide additional load balancing.In this paper, we propose to solve this difficult and highly dynamic problem using adaptive multi-agent systems, taking advantage from their self-adaptation and self-organization mechanisms. In the proposed system, the agents, through their local interactions, allow to dynamically reach a good solution, while ensuring a controlled distribution of tasks within the constellation of satellites. Finally, a comparison with a classical chronological greedy algorithm, commonly used in the spatial domain, high- lights the advantages of the presented system.