The minimisation problem of a sum of unary and pairwise functions of discrete variables is a general NP-hard problem with wide applications such as computing MAP configurations in Markov Random Fields (MRF), minimising Gibbs energy, or solving binary Valued Constraint Satisfaction Problems (VCSPs). We study the computational complexity of classes of discrete optimisation problems given by allowing only certain types of costs in every triangle of variable-value assignments to three distinct variables. We show that for several computational problems, the only non- trivial tractable classes are the well known maximum matching problem and the recently discovered joint-winner property. Our results, apart from giving complete classifications in the studied cases, provide guidance in the search for hybrid tractable classes; that is, classes of problems that are not captured by restrictions on the functions (such as submodularity) or the structure of the problem graph (such as bounded treewidth). Furthermore, we introduce a class of problems with convex cardinality functions on cross-free sets of assignments. We prove that while imposing only one of the two conditions renders the problem NP-hard, the conjunction of the two gives rise to a novel tractable class satisfying the cross-free convexity property, which generalises the joint-winner property to problems of unbounded arity.

In a minimal binary constraint network, every tuple of a constraint relation can be extended to a solution. The tractability or intractability of computing a solution to such a minimal network was a long standing open question. Dechter conjectured this computation problem to be NP-hard. We prove this conjecture. We also prove a conjecture by Dechter and Pearl stating that for k\geq2 it is NP-hard to decide whether a single constraint can be decomposed into an equivalent k-ary constraint network. We show that this holds even in case of bi-valued constraints where k\geq3, which proves another conjecture of Dechter and Pearl. Finally, we establish the tractability frontier for this problem with respect to the domain cardinality and the parameter k.

The rules of Sudoku are often specified using twenty seven \texttt{all\_different} constraints, referred to as the {\em big} \mrules. Using graphical proofs and exploratory logic programming, the following main and new result is obtained: many subsets of six of these big \mrules are redundant (i.e., they are entailed by the remaining twenty one \mrules), and six is maximal (i.e., removing more than six \mrules is not possible while maintaining equivalence). The corresponding result for binary inequality constraints, referred to as the {\em small} \mrules, is stated as a conjecture.

The Word-RAM is a model of computation that takes into account the capacity of a computer to manipulate a word of w bits with a single instruction. Many modern constraint solvers use a bitset data structure to encode the values contained in the variable domains. Using the algorithmic techniques developed for the Word-RAM, we propose new filtering algorithms that can prune Opwq values from a domain in a single instruction. Experiments show that on a processor with w = 64, the new filtering algorithms that enforce domain consis- tency on the constraints A + B = C, |A - B| = C and ALL-DIFFERENT can offer a speed up of a factor 10.

When designing a complex system, adhering to a design methodology is essential to ensure design quality and to shorten the design phase. Until recently, enforcing this could be done only partially or manually. This paper demonstrates how constraint programming technology can enable automation of the design methodology support when the design artifacts reside in a central repository. At any phase of the design, the proposed constraint programming application can indicate whether the design process data complies with the methodology and point out any violations that may exist. Moreover, the application can provide recommendations regarding the design process. The application was successfully used to check the methodology conformance of an industrial example and produced the desired outputs within reasonable times.

In proof-of-payment transit systems, passengers are legally required to purchase tickets before entering but are not physically forced to do so. Instead, patrol units move about the transit system, inspecting the tickets of passengers, who face fines if caught fare evading. The deterrence of such fines depends on the unpredictability and effectiveness of the patrols. In this paper, we present TRUSTS, an application for scheduling randomized patrols for fare inspection in transit systems. TRUSTS models the problem of computing patrol strategies as a leader-follower Stackelberg game where the objective is to deter fare evasion and hence maximize revenue. This problem differs from previously studied Stackelberg settings in that the leader strategies must satisfy massive temporal and spatial constraints; moreover, unlike in these counterterrorism-motivated Stackelberg applications, a large fraction of the ridership might realistically consider fare evasion, and so the number of followers is potentially huge. A third key novelty in our work is deliberate simplification of leader strategies to make patrols easier to be executed. We present an efficient algorithm for computing such patrol strategies and present experimental results using real-world ridership data from the Los Angeles Metro Rail system. The Los Angeles County Sheriff’s department has begun trials of TRUSTS.

This paper presents a prototype system called SFplanner which uses an automated planning technique to generate workflows for reconfiguring a computing infrastructure. The system allows an administrator to specify a configuration task which consists of current state, desired state and global constraints. This task is compiled to a grounded finite-domain representation as the input for the standard (unmodified) Fast-Downward planner in order to automatically generate a workflow. The execution of the workflow will bring the system into the desired state, preserving the global constraints at every stage of the workflow.

In an Artificial Intelligence course, a basic concept is Constraint Satisfaction (CS), which is acknowledged as a hard domain for teachers to teach and student to understand. In this paper, we present a game-based learning approach to assist students in learning CS algorithms, such as arc consistency and search algorithms, for problem solving in an easy, interactive and motivating way. Preliminary valuation has showed promising results.

Recently, a new language AC(C) was proposed to integrate answer set programming (ASP) and constraint logic programming (CLP). In this paper, we show that temporally expressive planning problems in PDDL2.1 can be translated into AC(C) and solved using AC(C) solvers. Compared with existing approaches, the new approach puts less restrictions on the planning problems and is easy to extend with new features like PDDL axioms. It can also leverage the inference engine for AC(C) which has the potential to exploit the best reasoning mechanisms developed in the ASP, SAT and CP communities.

Recent work on planning in incomplete domains focuses on constructing plans that succeed despite incomplete knowledge of action preconditions and effects. As planning models become more expressive, such as in temporal planning, the types of incompleteness may not only change, but plans become more challenging to evaluate. The primary difficulty to temporal plan evaluation is accounting for temporal constraints that may not be satisfied under all interpretations of the incomplete domain. In this work, we formulate incomplete temporal plan evaluation as a generalization of the temporal consistency problem, called partial temporal consistency. We present a knowledge compilation approach that is combined with symbolic constraint propagation and model counting algorithms for counting the number of incomplete domain model interpretations under which a plan is consistent. We present an evaluation that identifies the aspects of incomplete temporal plans most impact performance.