Search

Exact combinatorial search is essential to a wide range of important applications, and there are many large problems that need to be solved quickly. Searches are extremely challenging to parallelise due to a combination of factors, e.g. searches are non-deterministic, dynamic pruning changes the workload, and search tasks have very different runtimes. YewPar is a C++/HPX framework that generalises parallel search by providing a range of sophisticated search skeletons.This paper demonstrates generic high performance combinatorial search, i.e. that a variety of exact combinatorial searches can be easily parallelised for HPC using YewPar. We present a new mechanism for profiling key aspects of YewPar parallel combinatorial search, and demonstrate its value. We exhibit, for the first time, generic exact combinatorial searches at HPC scale. We baseline YewPar against state-of-the-art sequential C++ and C++/OpenMP implementations. We demonstrate that deploying YewPar on an HPC system can dramatically reduce the runtime of large problems, e.g. from days to just 100s. The maximum relative speedups we achieve for an enumeration search are near-linear up to 195(6825) compute-nodes(workers), super-linear for an optimisation search on up to 128(4480) (pruning reduces the workload), and sub-linear for decision searches on up to 64(2240) compute-nodes(workers). [ABSTRACT FROM AUTHOR]

Post-translational modification of proteins plays an important role in cancer cell biology. Proteins encoded by oncogenes may be activated by phosphorylation, products of tumour suppressors might be inactivated by phosphorylation or ubiquitinylation, which marks them for degradation; chromatin-binding proteins are often methylated and/or acetylated. These are just a few of the many hundreds of post-translational modifications discovered by years of painstaking experimentation and the chemical analysis of purified proteins. In recent years, mass spectrometry-based proteomics emerged as the principal technique for identifying such modifications in samples from cultured cells and tumour tissue. Here, we used a recently developed combinatorial search algorithm implemented in the MGVB toolset to identify novel modifications in samples from breast cancer cell lines. Our results provide a rich resource of coupled protein abundance and post-translational modification data seen in the context of an important biological function—the response of cells to interferon gamma treatment—which can serve as a starting point for future investigations to validate promising modifications and explore the utility of the underlying molecular mechanisms as potential diagnostic or therapeutic targets. [ABSTRACT FROM AUTHOR]

In this paper, we study the target tracking problem in wireless sensor networks (WSNs) using quantized sensor measurements where the total number of bits that can be transmitted from sensors to the fusion center is limited. At each time step of tracking, a total of R available bits need to be distributed among the N sensors in the WSN for the next time step. The optimal solution for the bit allocation problem can be obtained by using a combinatorial search which may become computationally prohibitive for large N and R. Therefore, we develop two new suboptimal bit allocation algorithms which are based on convex optimization and approximate dynamic programming (A-DP). We compare the mean squared error (MSE) and computational complexity performances of convex optimization and A-DP with other existing suboptimal bit allocation schemes based on generalized Breiman, Friedman, Olshen, and Stone (GBFOS) algorithm and greedy search. Simulation results show that, A-DP, convex optimization and GBFOS yield similar MSE performance, which is very close to that based on the optimal exhaustive search approach and they outperform greedy search and nearest neighbor based bit allocation approaches significantly. Computationally, A-DP is more efficient than the bit allocation schemes based on convex optimization and GBFOS, especially for a large sensor network. [ABSTRACT FROM PUBLISHER]

The paper presents a two-stage, global planning algorithm for the waypoint-following task realized by a unicycle-like robot in a cluttered environment. It assumes motion execution with the VFO (Vector Field Orientation) controller. The planner is a result of a controller-driven design process and exploits particular properties of the VFO controller. Emphasis has been put on the plan safety in the sense of maximizing the distance from the obstacles. In the first stage of planning, an A*-like pathfinding algorithm is used to find a safe geometric plan (i.e. a polyline) in a two-dimensional occupancy grid. During the second stage, a sequence of waypoint positions is selected from the geometric plan and reference orientations at the waypoints are planned. Orientation planning exploits properties of the VFO controller used for subsequent motion execution. Proposed two-stage algorithm admits changes of robot motion strategy (forward/backward movement) and has lower computational cost than the full configuration space search. Performance of the algorithm can be intuitively tuned with provided design parameters. [ABSTRACT FROM AUTHOR]

Abstract We study two models of the Majority problem. We are given n balls and an unknown coloring of them with two colors. We can ask sets of balls of size k as queries, and in the so-called General Model the answer to a query shows if all the balls in the set are of the same color or not. In the so-called Counting Model the answer to a query gives the difference between the cardinalities of the color classes in the query. Our goal is to show a ball of the larger color class, or prove that the color classes are of the same size, using as few queries as possible. In this paper we improve the bounds given by De Marco and Kranakis (2015) for the number of queries needed. [ABSTRACT FROM AUTHOR]

Index-tracking is a low-cost alternative to active portfolio management. The implementation of a quantitative approach, however, is a major challenge from an optimization perspective. The optimal selection of a group of assets that can replicate the index of a much larger portfolio requires both to find the optimal subset of assets and to fine-tune their weights. The former is a combinatorial, the latter a continuous numerical problem. Both problems need to be addressed simultaneously, because whether or not a selection of assets is promising depends on the allocation weights and vice versa. Moreover, the problem is usually of high dimension. Typically, an optimal subset of 30–150 positions out of 100–600 need to be selected and their weights determined. Search heuristics can be a valuable alternative to traditional methods, which often cannot deal with the problem. In this paper, we propose a new optimization method, which is partly based on Differential Evolution (DE) and on combinatorial search. The main advantage of our method is that it can tackle the index-tracking problem as complex as it is, generating accurate and robust results. [ABSTRACT FROM AUTHOR]

We study generators of metric spaces--sets of points with the property that every point of the space is uniquely determined by the distances from their elements. Such generators put a light on seemingly different kinds of problems in combinatorics that are not directly related to metric spaces. The two applications we present concern combinatorial search: problems on false coins known from the borderline of extremal combinatorics and information theory; and a problem known from combinatorial optimization --connected joins in graphs. We use results on the detection of false coins to approximate the metric dimension (minimum size of a generator for the metric space defined by the distances) of some particular graphs for which the problem was known and open. In the opposite direction, using metric generators, we show that the existence of connected joins in graphs can be solved in polynomial time, a problem asked in a survey paper of Frank. On the negative side we prove that the minimization of the number of components of a join is NP-hard. We further explore the metric dimension with some problems.The main problem we are led to is how to extend an isometry given on a metric generator of a metric space. [ABSTRACT FROM AUTHOR]

Dominance relations are used to prune unnecessary nodes in search graphs. However, they are problem dependent and cannot be derived by a general procedure. In this paper, machine learning of dominance heuristics is presented. A classification of dominance relations and the applicable learning mechanisms are identified. A study of learning dominance heuristics using learning by experimentation is described. The design of TEACHER-1 (Techniques using Experimentation for Acquiring and Creating HEuRistics) is shown. This system has been able to learn dominance heuristics for the 0/1-knapsack problem, an inventory problem, the reliability-by-replication problem, the two-machine flow shop problem, a number of single-machine scheduling problems, and a two-machine scheduling problem. The proof that the dominance heuristics learned are true dominance relations is not part of TEACHER-1 and is not automated. The same methodology can be extended to learn dominance heuristics in general. [ABSTRACT FROM AUTHOR]

The flexibility of spectrum usage required by emerging paradigms, radio spectrum demand driven by new wireless technologies, new applications and government policies oriented to massive use of Internet require spectrum management authorities to have smarter tools to do their work in an efficient way. This paper presents the design and implementation of a web application to support spectrum management activities using constraints programming. The design includes a mathematical model for allocation constraints, a mathematical model for interference constraints, a relational database of the National Allocation Table considering bands, channels and services associated with geopolitical division of Colombia, and an operator allocation database. These tools allow creating and to parameterize different levels of restrictions establishing different costs and weights. The interference analysis module takes into account the geographical location and technical characteristics of transmitting stations. The tool developed in this work can be used, among others, in allocation optimization studies, assessing policies of spectrum reallocation, allocation analysis to maximize specific criteria, reducing technology costs of implementing specific technologies and help identifying objective variables for spectrum price estimation. To facilitate the understanding and exploitation of the application several didactic examples are included. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we study two combinatorial search problems: the coin weighing problem with a spring scale (also known as the vector reconstructing problem using additive queries) and the problem of reconstructing weighted graphs using additive queries. Suppose we are given  identical looking coins. Suppose that out of the coins are counterfeit and the rest are authentic. Assume that we are allowed to weigh subsets of coins with a spring scale. It is known that the optimal number of weighings for identifying the counterfeit coins and their weights is at least We give a deterministic polynomial time adaptive algorithm for identifying the counterfeit coins and their weights using weighings, assuming that the weight of the counterfeit coins are greater than the weight of the authentic coins. This algorithm is optimal when , where is any constant. Also our weighing complexity is within times the optimal complexity for all . To obtain this result, our algorithm makes use of search matrices, the divide and conquer approach and the guess and check approach. When combining these methods with the technique introduced in H. Mazzawi (2008) , we get a similar positive result for the problem of reconstructing a hidden weighted graph using additive queries. [Copyright &y& Elsevier]

Abstract: Consider the following generalization of the sequential group testing problem for 2 defective items, which is suggested by Aigner (1988) in : Suppose a graph contains one defective edge . Find the endpoints of by testing whether a subset of vertices of cardinality at most 2 contains at least one of the endpoints of or not. What is then the minimum number of tests, which are needed in the worst case to identify ? In Gerzen (2009) , this problem was partially solved by deriving sharp lower and upper bounds for . In addition, it was proved that the determination of is an NP-complete problem. Among others, it was shown that the inequality holds for graphs with 2-complexity and the edge set . 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. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the problem of reconstructing a hidden weighted graph using additive queries. We prove the following. Let be a weighted hidden graph with  vertices and edges such that the weights on the edges are bounded between  and  for any positive constants  and . For any , there exists a non-adaptive algorithm that finds the edges of the graph using additive queries. This solves the open problem in [S. Choi, J.H. Kim, Optimal query complexity bounds for finding graphs, in: STOC, 2008, pp. 749–758]. Choi and Kim’s proof holds for for a sufficiently large constant  and uses the graph theory. We use the algebraic approach for the problem. Our proof is simple and holds for any . [Copyright &y& Elsevier]

Abstract: Many well-known problems in Artificial Intelligence can be formulated in terms of systems of constraints. The problem of testing the satisfiability of propositional formulae (SAT) is of special importance due to its numerous applications in theoretical computer science and Artificial Intelligence. A brute-force algorithm for SAT will have exponential time complexity , where is the number of Boolean variables of the formula. Unfortunately, more sophisticated approaches such as resolution result in similar performances in the worst case. In this paper, we present a simple and relatively efficient parallel divide-and-conquer method to solve various subclasses of SAT. The dissection stage of the parallel algorithm splits the original formula into smaller subformulae with only a bounded number of interacting variables. In particular, we derive a parallel algorithm for the class of formulae whose corresponding graph representation is planar. Our parallel algorithm for planar 3-SAT has the worst-case performance of on a PRAM (parallel random access model) computer. Applications of our method to constraint satisfaction problems are discussed. [Copyright &y& Elsevier]

Abstract: The following search model of a coin-weighing problem is considered: G has n coins, of which are good coins of the same weight , one counterfeit coin of weight is heavier and another counterfeit coin of weight is lighter (). The weighing device is a two-arms balance. Let be the number of coins for which k weighings suffice to identify the two counterfeit coins by algorithm and let be the information-theoretic upper bound of the number of coins; then, . One is concerned with the question whether there is an algorithm such that for all integers k. It is proved that the information-theoretic upper bound is always achievable for all even integer . For odd integer , we establish a general method of approximating the information-theoretic upper bound arbitrarily. The ideas and techniques of this paper can be employed easily to settle other models of two counterfeit coins. [Copyright &y& Elsevier]

Abstract: The plurality problem is a game between two participants: Paul and Carole. We are given n balls, each of them is colored with one out of c colors. At any step of the game, Paul chooses two balls and asks whether they are of the same color, whereupon Carole answers yes or no. The game ends when Paul either produces a ball a of the plurality color (meaning that the number of balls colored like a exceeds those of the other colors), or when Paul states that there is no plurality. How many questions does Paul have to ask in the worst case? For , the problem is equivalent to the well-known majority problem which has already been solved (Combinatorica 11 (1991) 383–387). In this paper we show that Moreover, for any , we show that surprisingly the naive algorithm for the plurality problem is asymptotically optimal. [Copyright &y& Elsevier]

The performance of parallel combinatorial OR-tree searches (or OR-tree searches in short) is analytically evaluated in this paper. This performance depends on the complexity of the problem to be solved, the error allowance function, the dominance relation, and the search strategies. The exact performance may be difficult to predict due to the nondeterminism and anomalies of parallelism. We derive the performance. bounds of parallel OR-tree searches with respect to the best-first, depth-first, and breadth-first strategies, and verify these bound by simulations. We show that a near-linear speedup can be achieved with respect to a large number of processors for parallel OR- tree searches. Using the performance bound developed, we derive sufficient conditions for assuring that parallelism wilt not degrade the performance, and necessary conditions for allowing parallelism to have a speedup greater than the ratio of number of processors These bounds and conditions provide the theoretical foundation for determining the number of processors to assure a near-linear speedup. [ABSTRACT FROM AUTHOR]

Automated modeling aims at the induction of mathematical models, both their structure and parameter values, from time-series measurements of observed system variables. In this paper, we address the task of model structure selection, i.e., selecting an optimal structure from a user-specified finite set of alternative model structures, using various approaches to combinatorial search. We propose a mapping of the set of candidate model structures to a fixed-length, vector representation allowing the use of an arbitrary search algorithm as a solver of the structure selection task. We perform a comparative analysis of the performance of thirteen variants of several search algorithms, ranging from ones with high intensification, i.e., focus on neighborhood of the best candidate solutions, to ones with high diversification, i.e., focus on covering the entire search space. The empirical analysis involves eight tasks of reconstructing known models of dynamical systems from synthetic and measured data. The results of the analysis show that search algorithms involving moderate diversification methods have superior performance on the structure selection task. The empirical analysis also reveals that this finding is related to specific properties of the search space of candidate model structures. [ABSTRACT FROM AUTHOR]

We consider the following $$q$$ -analog of the basic combinatorial search problem: let $$q$$ be a prime power and $$\mathrm{GF}(q)$$ the finite field of $$q$$ elements. Let $$V$$ denote an $$n$$ -dimensional vector space over $$\mathrm{GF}(q)$$ and let $${{\mathbf v}}$$ be an unknown 1-dimensional subspace of $$V$$ . We will be interested in determining the minimum number of queries that is needed to find $${{\mathbf v}}$$ provided all queries are subspaces of $$V$$ and the answer to a query $$U$$ is YES if $${{{\mathbf v}} \leqslant U}$$ and NO if $${{{\mathbf v}} \nleqslant U}$$ . This number will be denoted by $$A(n,q)$$ in the adaptive case (when for each queries answers are obtained immediately and later queries might depend on previous answers) and $$M(n,q)$$ in the non-adaptive case (when all queries must be made in advance). In the case $$n=3$$ we prove $$2q-1=A(3,q)