Memory intensive AND/OR search for combinatorial optimization in graphical models

In this paper we explore the impact of caching during search in the context of the recent framework of AND/OR search in graphical models. Specifically, we extend the depth-first AND/OR Branch-and-Bound tree search algorithm to explore an AND/OR search graph by equipping it with an adaptive caching scheme similar to good and no-good recording. Furthermore, we present best-first search algorithms for traversing the same underlying AND/OR search graph and compare both algorithms empirically. We focus on two common optimization problems in graphical models: finding the Most Probable Explanation (MPE) in belief networks and solving Weighted CSPs (WCSP). In an extensive empirical evaluation we demonstrate conclusively the superiority of the memory intensive AND/OR search algorithms on a variety of benchmarks.     

AND/OR search spaces for graphical models

The paper introduces an AND/OR search space perspective for graphical models that include probabilistic networks (directed or undirected) and constraint networks. In contrast to the traditional (OR) search space view, the AND/OR search tree displays some of the independencies present in the graphical model explicitly and may sometimes reduce the search space exponentially. Indeed, most algorithmic advances in search-based constraint processing and probabilistic inference can be viewed as searching an AND/OR search tree or graph. Familiar parameters such as the depth of a spanning tree, treewidth and pathwidth are shown to play a key role in characterizing the effect of AND/OR search graphs vs. the traditional OR search graphs. We compare memory intensive AND/OR graph search with inference methods, and place various existing algorithms within the AND/OR search space.     

Parallel Branch-and-Bound Formulations for AND/OR Tree Search

This paper discusses two general schemes for performing branch-and-bound (B&B) search in parallel. These schemes are applicable in principle to most of the problems which can be solved by B&B. The schemes are implemented for SSS*, a versatile algorithm having applications in game tree search, structural pattern analysis, and AND/OR graph search. The performance of parallel SSS* is studied in the context of AND/OR tree and game tree search. The paper concludes with comments on potential applications of these parallel implementations of SSS* in structural pattern analysis and game playing.     

Weighted heuristic anytime search: new schemes for optimization over graphical models

Weighted heuristic search (best-first or depth-first) refers to search with a heuristic function multiplied by a constant w [31]. The paper shows, for the first time, that for optimization queries in graphical models the weighted heuristic best-first and weighted heuristic depth-first branch and bound search schemes are competitive energy-minimization anytime optimization algorithms. Weighted heuristic best-first schemes were investigated for path-finding tasks. However, their potential for graphical models was ignored, possibly because of their memory costs and because the alternative depth-first branch and bound seemed very appropriate for bounded depth. The weighted heuristic depth-first search has not been studied for graphical models. We report on a significant empirical evaluation, demonstrating the potential of both weighted heuristic best-first search and weighted heuristic depth-first branch and bound algorithms as approximation anytime schemes (that have sub-optimality bounds) and compare against one of the best depth-first branch and bound solvers to date.     

Extended Hopfield models for combinatorial optimization

The extended Hopfield neural network proposed by Abe et al. (1992) for solving combinatorial optimization problems with equality and/or inequality constraints has the drawback of being frequently stabilized in states with neurons of ambiguous classification as active or inactive. We introduce in the model a competitive activation mechanism and we derive a new expression of the penalty energy allowing us to reduce significantly the number of neurons with intermediate level of activations. The new version of the model is validated experimentally on the set covering problem. Our results confirm the importance of instituting competitive activation mechanisms in Hopfield neural-network models.     

Evolutionary optimization using graphical models

We have previously shown that a genetic algorithm can be approximated by an evolutionary algorithm using the product of univariate marginal distributions of selected points as search distribution. This algorithm (UMDA) successfully optimizes difficult multi-modal optimization problems. For correlated fitness landscapes more complex factorizations of the search distribution have to be used. These factorizations are used by the Factorized Distribution Algorithm FDA. In this paper we extend FDA to an algorithm which computes a factorization from the data. The factorization can be represented by a Bayesian network. The Bayesian network is used to generate the search points. Heinz Mühlenbein, Ph.D.: He is a research manager at GMD, the German national center for information technology. He obtained his diploma in mathematics from the University of Cologne in 1969, and his Ph.D from the University of Bonn in 1975. He entered GMD in 1969. He has worked on performance analysis of computer systems, computer networks, and massively parallel computers. Since 1988 his research interests are in Natural Computation. He was Visiting Professor at the Universities Paderborn, Bonn, Edinburgh and Carnegie-Mellon University. He has published over 60 research papers. He initiated the international conference series in natural computation PPSN in 1990. From 1993 to 1998 he was responsible European editor of Evolutionary Computation. He is presently on the Editorial Board of Evolutionary Computation, Scientific Computation and Journal of Heuristics. Thilo Mahnig, Ph.D. student: He is working at GMD — German National Research Center for Information Technology in St. Augustin. He obtained his diploma in mathematics from the University of Bonn in differential geometry in 1996. His research interest lies in the theory of population based optimization algorithms. He has co-authored several papers with Heinz Mühlenbein.     

Cut-and-solve: An iterative search strategy for combinatorial optimization problems

Branch-and-bound and branch-and-cut use search trees to identify optimal solutions to combinatorial optimization problems. In this paper, we introduce an iterative search strategy which we refer to as cut-and-solve and prove optimality and termination for this method. This search is different from traditional tree search as there is no branching. At each node in the search path, a relaxed problem and a sparse problem are solved and a constraint is added to the relaxed problem. The sparse problems provide incumbent solutions. When the constraining of the relaxed problem becomes tight enough, its solution value becomes no better than the incumbent solution value. At this point, the incumbent solution is declared to be optimal. This strategy is easily adapted to be an anytime algorithm as an incumbent solution is found at the root node and continuously updated during the search.Cut-and-solve enjoys two favorable properties. Since there is no branching, there are no “wrong” subtrees in which the search may get lost. Furthermore, its memory requirement is negligible. For these reasons, it has potential for problems that are difficult to solve using depth-first or best-first search tree methods.In this paper, we demonstrate the cut-and-solve strategy by implementing a generic version of it for the Asymmetric Traveling Salesman Problem (ATSP). Our unoptimized implementation outperformed state-of-the-art solvers for five out of seven real-world problem classes of the ATSP. For four of these classes, cut-and-solve was able to solve larger (sometimes substantially larger) problems. Our code is available at our websites.     

A quantum-inspired Tabu search algorithm for solving combinatorial optimization problems

In this study, we propose a novel quantum-inspired evolutionary algorithm (QEA), called quantum inspired Tabu search (QTS). QTS is based on the classical Tabu search and characteristics of quantum computation, such as superposition. The process of qubit measurement is a probability operation that increases diversification; a quantum rotation gate used to searching toward attractive regions will increase intensification. This paper will show how to implement QTS into NP-complete problems such as 0/1 knapsack problems, multiple knapsack problems and the traveling salesman problem. These problems are important to computer science, cryptography and network security. Furthermore, our experimental results on 0/1 knapsack problems are compared with those of other heuristic algorithms, such as a conventional genetic algorithm, a Tabu search algorithm and the original QEA. The final outcomes show that QTS performs much better than other heuristic algorithms without premature convergence and with more efficiency. Also on multiple knapsack problems and the traveling salesman problem QTS verify its effectiveness.     

Structural analysis of local search heuristics in combinatorial optimization

Neighborhood, or local, search is a popular and practical heuristic for many combinational optimization problems. We examine the neighborhood structures of two classes of problems, 0–1 integer programming and the mean tardiness job sequencing problem—from the viewpoint of state-space graphs in artificial intelligence. Such analysis is shown to provide fundamental insights into the nature of local search algorithms and provides a useful framework for evaluating and comparing such heuristics. Computational results are presented to support these observations.     

Evolutionary algorithm with a directional local search for multiobjective optimization in combinatorial problems

Evolutionary algorithms (EAs) are often employed to multiobjective optimization, because they process an entire population of solutions which can be used as an approximation of the Pareto front of the tackled problem. It is a common practice to couple local search with evolutionary algorithms, especially in the context of combinatorial optimization. In this paper a new local search method is proposed that utilizes the knowledge concerning promising search directions. The proposed method can be used as a general framework and combined with many methods of iterating over a neighbourhood of an initial solution as well as various decomposition approaches. In the experiments the proposed local search method was used with an EA and tested on 2-, 3- and 4-objective versions of two well-known combinatorial optimization problems: the travelling salesman problem (TSP) and the quadratic assignment problem (QAP). For comparison two well-known local search methods, one based on Pareto dominance and the other based on decomposition, were used with the same EA. The results show that the EA coupled with the directional local search yields better results than the same EA coupled with any of the two reference methods on both the TSP and QAP problems.     

Multi-center variable-scale search algorithm for combinatorial optimization problems with the multimodal property

Combinatorial optimization problems (COPs) are discrete problems arising from aerospace, bioinformatics, manufacturing, and other fields. One of the classic COPs is the scheduling problem. Moreover, these problems are usually multimodal optimization problems with a quantity of global and local optima. As a result, many search algorithms can easily become trapped into local optima. In this article, we propose a multi-center variable-scale search algorithm for solving both single-objective and multi-objective COPs. The algorithm consists of two distinct points. First, the multi-center strategy chooses several individuals with better performance as the only parents of the next generation, which means that there are a number of separate searching areas around the searching center. Second, the next generation of the population is produced by a variable-scale strategy with an exponential equation based on the searching center. The equation is designed to control the neighborhood scale, and adaptively realize the large-scale and small-scale searches at different search stages to balance the maintenance of diversity and convergence speed. In addition, an approach of adjusting centers is proposed concerning the number and distribution of centers for solving multi-objective COPs. Finally, the proposed algorithm is applied to three COPs, including the well-known flexible job shop scheduling problem, the unrelated parallel machine scheduling problem, and the test task scheduling problem. Both the single-objective optimization algorithm and the multi-objective optimization algorithm demonstrate competitive performance compared with existing methods.     

Black-box combinatorial optimization using models with integer-valued minima

Annals of Mathematics and Artificial Intelligence - When a black-box optimization objective can only be evaluated with costly or noisy measurements, most standard optimization algorithms are...     

A graphical formalism for mixed multi-unit combinatorial auctions

Mixed multi-unit combinatorial auctions are auctions that allow participants to bid for bundles of goods to buy, for bundles of goods to sell, and for transformations of goods. The intuitive meaning of a bid for a transformation is that the bidder is offering to produce a set of output goods after having received a set of input goods. To solve such an auction the auctioneer has to choose a set of bids to accept and decide on a sequence in which to implement the associated transformations. Mixed auctions can potentially be employed for the automated assembly of supply chains of agents. However, mixed auctions can be effectively applied only if we can also ensure their computational feasibility without jeopardising optimality. To this end, we propose a graphical formalism, based on Petri nets, that facilitates the compact represention of both the search space and the solutions associated with the winner determination problem for mixed auctions. This approach allows us to dramatically reduce the number of decision variables required for solving a broad class of mixed auction winner determination problems. An additional major benefit of our graphical formalism is that it provides new ways to formally analyse the structural and behavioural properties of mixed auctions.     

Hyper-Distributed Hyper-Parallel Implementation of Heuristic Search of Implicit AND/OR Graph

This paper presents the hierarchic chaotic cellular networks for the hardware implementation of hyper-distributed hyper-parallel intelligent problem solving based on competitive wave propagation.By using the bifurcation and the synchronization of distributed chaotic dynamic systems,and by improving the Chua‘s circuit,the mechanism and the algorithms of heuristic search of an implicit AND/OR graph are realized in a hyper-distributed hyper-parallel environment.This paper‘s approach has many advantages in comparison with other traditional systolic structures based on symbolic logic algorithms.     

Tests for Gaussian graphical models

Gaussian graphical models are promising tools for analysing genetic networks. In many applications, biologists have some knowledge of the genetic network and may want to assess the quality of their model using gene expression data. This is why one introduces a novel procedure for testing the neighborhoods of a Gaussian graphical model. It is based on the connection between the local Markov property and conditional regression of a Gaussian random variable. Adapting recent results on tests for high-dimensional Gaussian linear models, one proves that the testing procedure inherits appealing theoretical properties. Besides, it applies and is computationally feasible in a high-dimensional setting: the number of nodes may be much larger than the number of observations. A large part of the study is devoted to illustrating and discussing applications to simulated data and to biological data.     

A graphical model for evolutionary optimization

We present a statistical model of empirical optimization that admits the creation of algorithms with explicit and intuitively defined desiderata. Because No Free Lunch theorems dictate that no optimization algorithm can be considered more efficient than any other when considering all possible functions, the desired function class plays a prominent role in the model. In particular, this provides a direct way to answer the traditionally difficult question of what algorithm is best matched to a particular class of functions. Among the benefits of the model are the ability to specify the function class in a straightforward manner, a natural way to specify noisy or dynamic functions, and a new source of insight into No Free Lunch theorems for optimization.