Annals of Operations Research manuscript No. (will be inserted by the editor) Abstract The Low Autocorrelation Binary Sequence problem has applications in telecommunications, is of theoretical interest to physicists, and has inspired work by many optimisation researchers because of its difficulty. For many years it was considered unsuitable for solution by metaheuristics because of its search space topology, but in recent years metaheuristics have found long high-quality sequences. However, complete search has not progressed since a parallel branch-and-bound method of 1996. In this paper we find four ways of improving branch-and-bound, leading to a tighter relaxation, faster convergence to optimality and better scalability. We also extend known optimality results for skew-symmetric sequences from length 73 to 89.

We investigate two systems of fully proportional representation suggested by Chamberlin & Courant and Monroe. Both systems assign a representative to each voter so that the "sum of misrepresentations" is minimized. The winner determination problem for both systems is known to be NP-hard, hence this work aims at investigating whether there are variants of the proposed rules and/or specific electorates for which these problems can be solved efficiently. As a variation of these rules, instead of minimizing the sum of misrepresentations, we considered minimizing the maximal misrepresentation introducing effectively two new rules. In the general case these "minimax" versions of classical rules appeared to be still NP-hard. We investigated the parameterized complexity of winner determination of the two classical and two new rules with respect to several parameters. Here we have a mixture of positive and negative results: e.g., we proved fixed-parameter tractability for the parameter the number of candidates but fixed-parameter intractability for the number of winners. For single-peaked electorates our results are overwhelmingly positive: we provide polynomial-time algorithms for most of the considered problems. The only rule that remains NP-hard for single-peaked electorates is the classical Monroe rule.

The problem of optimizing unknown costly-to-evaluate functions has been studied for a long time in the context of Bayesian Optimization. Algorithms in this field aim to find the optimizer of the function by asking only a few function evaluations at locations carefully selected based on a posterior model. In this paper, we assume the unknown function is Lipschitz continuous. Leveraging the Lipschitz property, we propose an algorithm with a distinct exploration phase followed by an exploitation phase. The exploration phase aims to select samples that shrink the search space as much as possible. The exploitation phase then focuses on the reduced search space and selects samples closest to the optimizer. Considering the Expected Improvement (EI) as a baseline, we empirically show that the proposed algorithm significantly outperforms EI.

ExtractingMUCs(MinimalUnsatisfiableCores)fromanunsatisfiable constraint network is a useful process when causes of unsatisfiability must be understood so that the network can be re-engineered and relaxed to become sat- isfiable. Despite bad worst-case computational complexity results, various MUC- finding approaches that appear tractable for many real-life instances have been proposed. Many of them are based on the successive identification of so-called transition constraints. In this respect, we show how local search can be used to possibly extract additional transition constraints at each main iteration step. The approach is shown to outperform a technique based on a form of model rotation imported from the SAT-related technology and that also exhibits additional transi- tion constraints. Our extensive computational experimentations show that this en- hancement also boosts the performance of state-of-the-art DC(WCORE)-like MUC extractors.

Incremental heuristic searches try to reuse their previous search efforts whenever these are available. As a result, they can often solve a sequence of similar planning problems much faster than planning from scratch. State-of-the-art incremental heuristic searches such as LPA*, D* and D* Lite all work by propagating cost changes to all the states on the search tree whose g-values (the costs of computed paths from the start) are no longer optimal. While such a complete propagation of cost changes is required to ensure optimality, the propagations can be stopped much earlier if we are looking for solutions within a given suboptimality bound. We present a framework called Truncated Incremental Search that builds on this observation, and uses a target suboptimality bound to efficiently restrict the cost propagations. Using this framework, we develop two algorithms, Truncated LPA* (TLPA*) and Truncated D* Lite (TD* Lite). We discuss their analytical properties and present experimental results for 2D and 3D (x, y, heading) path planning that show significant improvement in runtime over existing incremental heuristic searches when searching for close-to-optimal solutions. In addition, unlike typical incremental searches, Truncated Incremental Search is much less dependent on the proximity of the cost changes to the goal of the search due to the early termination of the cost change propagation.

Constraint Programming (CP) solvers classically explore the solution space using tree-search based heuristics. Monte-Carlo Tree-Search (MCTS) is a tree-search method aimed at optimal sequential decision making under uncertainty. At the crossroads of CP and MCTS, this paper presents the Bandit Search for Constraint Programming (BASCOP)  algorithm, adapting MCTS to the specifics of CP search trees. Formally, MCTS simultaneously estimates the average node reward, and uses it to bias the exploration towards the most promising regions of the tree, borrowing the multi-armed bandit (MAB) decision rule. The two contributions in BASCOP concern i) a specific reward function, estimating the relative failure depth conditionally to a (variable, value) assignment; ii) a new  decision rule, hybridizing the MAB framework and the spirit of local neighborhood search. Specifically, BASCOP guides the CP search in the neighborhood of the previous best solution, by exploiting statistical estimates gathered across multiple restarts. BASCOP, using Gecode as the underlying constraint solver, shows significant improvements over the depth-first search baseline on some  CP benchmark suites. For hard job-shop scheduling problems, BASCOP matches the results of state-of-the-art scheduling-specific CP approaches. These results demonstrate the potential of BASCOP as a generic yet robust search method for CP.

In this short position paper, we consider MaxWalkSAT, a local search algorithm for MAP inference in probabilistic graphical models, and lift it to the first-order level, yielding a powerful algorithm for MAP inference in Markov logic networks (MLNs). Lifted MaxWalkSAT is based on the observation that if the MLN is monadic, namely if each predicate is unary then MaxWalkSAT is completely liftable in the sense that no grounding is required at inference time. We propose to utilize this observation in a straight-forward manner: convert the MLN to an equivalent monadic MLN by grounding a subset of its logical variables and then apply lifted MaxWalkSAT on it. It turns out however that the problem of finding the smallest subset of logical variables which when grounded will yield a monadic MLN is NP-hard in general and therefore we propose an approximation algorithm for solving it.

Predicting native conformations of a protein sequence is known as de novo structure prediction and is a central challenge in computational biology. Most computational protocols employ Monte Carlo sampling. Evolutionary search algorithms have also been proposed to enhance sampling of near-native conformations. These approaches bias stochastic search by an energy function, even though current energy functions are known to be inaccurate and drive sampling to non-native energy minima. This paper proposes a multiobjective approach which employs Pareto dominance, rather than total energy, to evaluate a conformation. This multiobjective approach accounts for the fact that terms in an energy function are conflicting optimization criteria. Our analysis is conducted on a diverse set of 20 proteins. Results show that employing Pareto dominance, rather than total energy, to guide stochastic search is more effective at sampling conformations which are both lower in energy and near the protein native structure.

There are many algorithms designed to solve the shortest path problem. Each of the published algorithms has a demonstrated use; a situation in which it is the clear choice.  Unfortunately, if faced with a novel problem, there is no reliable robust way to figure out which algorithm should be used to solve the new problem. When classifying things, the first step is to identify relevant features for classifications.  In the context of heuristic search, it not clear what pieces of information should be used to predict search algorithm performance, and the question of algorithm selection for a novel domain is an open question. We first analyze which domain attributes common algorithms leverage, and discuss how to identify domains containing these attributes.  In addition to discussing how to classify domains, we also discuss why the classifications matter for various algorithms.  Ultimately, this will allow us to offer more accurate runtime predictions for various algorithms we analyze, allowing us to determine which algorithm will likely offer the best performance.

Although the heuristic search algorithm A* is well-known to be optimally efficient, this result explicitly assumes forward search. Bidirectional search has long held promise for surpassing A*'s efficiency, and many varieties have been proposed, but it has proven difficult to achieve robust performance across multiple domains in practice. We introduce a simple bidirectional search technique called Incremental KKAdd that judiciously performs backward search to improve the accuracy of the forward heuristic function for any search algorithm. We integrate this technique with A*, assess its theoretical properties, and empirically evaluate its performance across seven benchmark domains. In the best case, it yields a factor of six reduction in node expansions and CPU time compared to A*, and in the worst case, its overhead is provably bounded by a user-supplied parameter, such as 1%. Viewing performance across all domains, it also surpasses previously proposed bidirectional search algorithms. These results indicate that Incremental KKAdd is a robust way to leverage bidirectional search in practice.