Catálogo de publicaciones - libros

The Low Autocorrelation Binary Sequences problem (LABS) is problem 005 in the CSPLIB library, where it is stated that “these problems pose a significant challenge to local search methods”. This paper presents a straighforward tabu search that systematically finds the optimal solutions for all tested instances.

The Quantified CSP (QCSP) is a generalisation of the classical CSP in which some of the variables are universally quantified [3].We consider the problem of relaxing an instance of the QCSP when it is unsatisfiable. We propose several novel forms of problem relaxations for the QCSP and present an algorithm for generating conflict-based explanations of inconsistency. Our motivation comes from problems in supply-chain management and conformant planning.

We reconsider the idea of structural symmetry breaking (SSB) for constraint satisfaction problems (CSPs). We show that the dynamic dominance checks used in symmetry breaking by dominance-detection search for CSPs with piecewise variable and value symmetries have a static counterpart: there exists a set of constraints that can be posted at the root node and that breaks all these symmetries. The amount of these symmetry-breaking constraints is linear in the size of the problem, but they possibly remove a super-exponential number of symmetries on both values and variables. Moreover, static and dynamic structural symmetry breaking coincide for static variable and value orderings.

We describe the Zinc modelling language. Zinc provides set constraints, user defined types, constrained types, and polymorphic predicates and functions. The last allows Zinc to be readily extended to different application domains by user-defined libraries. Zinc is designed to support a modelling methodology in which the same conceptual model can be automatically mapped into different design models, thus allowing modellers to easily “plug and play” with different solving techniques and so choose the most appropriate for that problem.

We present an incomplete filtering algorithm for the circuit constraint. The filter removes redundant values by eliminating nonhamiltonian edges from the associated graph. We identify nonhamiltonian edges by analyzing a smaller graph with labeled edges that is defined on a separator of the original graph. The complexity of the procedure for each separator S is approximately O (| S |^5). We found that it identified all infeasible instances and eliminated about one-third of the redundant domain elements in feasible instances.

The paper presents a method for generating solutions of a constraint satisfaction problem (CSP) uniformly at random. Our method relies on expressing the constraint network as a uniform probability distribution over its solutions and then sampling from the distribution using state-of-the-art probabilistic sampling schemes. To speed up the rate at which random solutions are generated, we augment our sampling schemes with pruning techniques used successfully in constraint satisfaction search algorithms such as conflict-directed back-jumping and no-good learning.

This paper presents an enumerative approach for a sports league scheduling problem. This simple method can solve some instances involving a number T of teams up to 70 while the best known constraint programing algorithm is limited to T ≤40. The proposed approach relies on interesting properties which are used to constraint the search process.

Symmetry breaking by dominance detection (SBDD) [4,6,1,12], has proven to excel on problems that contain large symmetry groups. The core task of SBDD is the dominance detection algorithm. The first automated dominance detection algorithms were based on group theory [7], while the first provably polynomial-time dominance checkers for specific types of value symmetry were devised in [15]. This work was later extended to tackle any kind of value symmetry in polynomial time [13]. Based on these results, for specific “piecewise” symmetric problems, [14] showed that breaking variable and value symmetry can be broken simultaneously in polynomial time. The method was named structural symmetry breaking (SSB) and is based on the structural abstraction of a given partial assignment of values to variables.

Tractability results for structural subproblems have generally been considered for explicit relations listing the allowed assignments. In this paper we define a representation which allows us to express constraint relations as either an explicit set of allowed labelings, or an explicit set of disallowed labelings, whichever is smaller. We demonstrate a new structural width parameter, which we call the interaction width, that when bounded allows us to carry over well known structural decompositions to this more concise representation. Our results naturally derive new structurally tractable classes for SAT.

Search effort is typically measured in terms of the number of backtracks, constraint checks, or nodes in the search tree, but measures such as the number of incorrect decisions have also been proposed. Comparisons based on mean and median effort are common. However, other researchers focus on studying runtime distributions, where one can observe a (non-)heavy-tailed distribution under certain conditions [2, 3].