Hard and soft precedence constraints  play  a key role in many application domains.  In telecommunications, one application is the configuration of call control feature subscriptions  where the task is to sequence a set of user-selected features subject to a set of hard (catalogue) precedence constraints and a set of soft (user-selected) precedence constraints. When no such consistent sequence exists, the task is to find an optimal relaxation by discarding some  features or user precedences. For this purpose, we present the global constraint SOFTPREC. Enforcing Generalized Arc Consistency  (GAC)  on SOFTPREC is NP-complete. Therefore, we approximate  GAC based on domain pruning  rules that follow from the semantics of  SOFTPREC; this pruning is polynomial. Empirical results demonstrate  that  the search effort  required by SOFTPREC is  up to one order of magnitude less than  the previously known best CP approach for the feature subscription problem. SOFTPREC is also applicable to other  problem domains  including minimum  cutset problems  for which initial experiments confirm the interest.

Powerful consistency techniques, such as AC* and FDAC*, have been developed for Weighted Constraint Satisfaction Problems (WCSPs) to reduce the space in solution search, but are restricted to only unary and binary constraints.  On the other hand, van Hoeve et al developed efficient graph-based algorithms for handling soft constraints as classical constraint optimization problems. We prove that naively incorporating van Hoeve's method into the WCSP framework can enforce a strong form of varnothing-Inverse Consistency, which can prune infeasible values and deduce good lower bound estimates.  We further show how Van Hoeve's method can be modified so as to handle cost projection and extension to maintain the stronger AC* and FDAC* generalized for non-binary constraints.  Using the soft allDifferent constraint as a testbed, preliminary results demonstrate that our proposal gives improvements up to an order of magnitude both in terms of time and pruning.

Set variables in constraint satisfaction problems (CSPs) are typically propagated by enforcing set bounds consistency together with cardinality reasoning, which uses some inference rules involving the cardinality of a set variable to produce more prunings than set bounds propagation alone. Multiset variables are a generalization of set variables by allowing the elements to have repetitions. In this paper, we generalize cardinality reasoning for multiset variables. In addition, we propose to exploit the variety of a multiset — the number of distinct elements in it — to improve modeling expressiveness and further enhance constraint propagation. We derive a number of inference rules involving the varieties of multiset variables. The rules interact varieties with the traditional components of multiset variables (such as cardinalities) to obtain stronger propagation. We also demonstrate how to apply the rules to perform variety reasoning on some common multiset constraints. Experimental results show that performing variety reasoning on top of cardinality reasoning can effectively reduce more search space and achieve better runtime in solving multiset CSPs.

Systematic search and local search paradigms for combinatorial problems are generally believed to have complementary strengths. Nevertheless, attempts to combine the power of the two paradigms have had limited success, due in part to the expensive information communication overhead involved. We propose a hybrid strategy based on shared memory, ideally suited for multi-core processor architectures. This method enables continuous information exchange between two solvers without slowing down either of the two. Such a hybrid search strategy is surprisingly effective, leading to substantially better quality solutions to many challenging Maximum Satisfiability (MaxSAT) instances than what the current best exact or heuristic methods yield, and it often achieves this within seconds. This hybrid approach is naturally best suited to MaxSAT instances for which proving unsatisfiability is already hard; otherwise the method falls back to pure local search.

Alpha-Beta is the most common game tree search algorithm, due to its high-performance and straightforward implementation. In practice one must find the best trade-off between heuristic evaluation time and bringing the subset of nodes explored closer to a minimum proof graph. In this paper we present a series of structural properties of minimum proof graphs that help us to prove that finding such graphs is NP-hard for arbitrary DAG inputs, but can be done in linear time for trees. We then introduce the class of fastest-cut-first search heuristics that aim to approximate minimum proof graphs by sorting moves based on approximations of sub-DAG values and sizes. To explore how various aspects of the game tree (such as branching factor and distribution of move values) affect the performance of Alpha-Beta we introduce the class of ``Prefix Value Game Trees'' that allows us to label interior nodes with true minimax values on the fly without search. Using these trees we show that by explicitly attempting to approximate a minimum game tree we are able to achieve performance gains over Alpha-Beta with common extensions.

Many local search algorithms are based on searching in the k-exchange neighborhood. This is the set of solutions that can be obtained from the current solution by exchanging at most k elements. As a rule of thumb, the larger k is, the better are the chances of  finding an improved  solution. However,  for inputs of size n,  a naive brute-force search of the k-exchange neighborhood requires n (O(k)) time, which is not practical even for very small values of k. We show that for several classes of sparse graphs, like planar graphs, graphs of bounded vertex degree and graphs excluding some fixed graph as a minor, an improved solution in the k-exchange neighborhood for many problems can be found much more efficiently.  Our algorithms run in time O(T(k)*n c ), where T is a function depending on k only and c is a constant independent of k.  We demonstrate the applicability of this  approach on different  problems like r-Center, Vertex Cover,  Odd Cycle Transversal, Max-Cut, and  Min-Bisection.  In particular, on planar graphs, all our algorithms searching for a k-local improvement run in time O(2 (O(k) ) * n (2) ), which is polynomial for k=O(log n). We also complement the algorithms with complexity results indicating that brute force search is unavoidable in more general classes of sparse graphs.

Monte Carlo tree search has brought significant improvements to the level of computer players in games such as Go, but so far it has not been used very extensively in games of strongly imperfect information with a dynamic board and an emphasis on risk management and decision making under uncertainty. In this paper we explore its application to the game of Kriegspiel (invisible chess), providing three Monte Carlo methods of increasing strength for playing the game with little specific knowledge. We compare these Monte Carlo agents to the strongest known minimax-based Kriegspiel player, obtaining significantly better results with a considerably simpler logic and less domain-specific knowledge.

Many problems have a huge state space and no good heuristic to order moves so as to guide the search toward the best positions. Random games can be used to score positions and evaluate their interest. Random games can also be improved using random games to choose a move to try at each step of a game. Nested Monte-Carlo Search addresses the problem of guiding the search toward better states when there is no available heuristic. It uses nested levels of random games in order to guide the search. The algorithm is studied theoretically on simple abstract problems and applied successfully to three different games: Morpion Solitaire, SameGame and 16x16 Sudoku.

Real-time heuristic search algorithms are used for planning by agents in situations where a constant-bounded amount of deliberation time is required for each action regardless of the problem size.  Such algorithms interleave their planning and execution to ensure real-time response. Furthermore, to guarantee completeness, they typically store improved heuristic estimates for previously expanded states.  Although subsequent planning steps can benefit from updated heuristic estimates, many of the same states are expanded over and over again.   Here we propose a variant of the A* algorithm, Time-Bounded A* (TBA*), that guarantees real-time response. In the domain of path-finding on video-game maps TBA* expands an order of magnitude fewer states than traditional real-time search algorithms, while finding paths of comparable quality. It reaches the same level of performance as recent state-of-the-art real-time search algorithms but, unlike these, requires neither state-space abstractions nor pre-computed pattern databases.

We study under what conditions bound consistency (BC) and arc consistency  (AC),  two forms of propagation used in constraint solvers, are equivalent to each other. We show that they prune exactly the same values when the propagated constraint is connected row convex / closed under median and its complement is row convex. This  characterization is exact for binary constraints. Since row convexity depends on the order of the values in the domains, we give polynomial algorithms for computing orders under which BC and AC are equivalent, if any.