Consider random hypergraphs on n vertices, where each k -element subset of vertices is selected with probability $independently and randomly as a hyperedge. By sparse we mean that the total number of hyperedges is  O ( n) or O ( n  ln n ). When k = 2, these are exactly the classical Erdös-Rényi random graphs G(n,p ). We prove that with high probability, hinge width on these sparse random hypergraphs can grow linearly with the expected number of hyperedges. Some random constraint satisfaction problems such as Model RB and Model RD have satisfiability thresholds on these sparse constraint hypergraphs, thus the large hinge width results provide some theoretical evidence for random instances around satisfiability thresholds to be hard for a standard hinge-decomposition based algorithm. We also conduct experiments on these and other kinds of random graphs with several hundreds vertices, including regular random graphs and power law random graphs. The experimental results also show that hinge width can grow linearly with the number of edges on these different random graphs. These results may be of further interests.

Classical constraint satisfaction problems (CSPs) are commonly defined on finite domains. In real life, constrained variables can evolve over time. A variable can actually take an infinite sequence of values over discrete time points. In this paper, we propose constraint programming on infinite data streams, which provides a natural way to model constrained time-varying problems. In our framework, variable domains are specified by ω-regular languages. We introduce special stream operators as basis to form stream expressions and constraints. Stream CSPs have infinite search space. We propose a search procedure that can recognize and avoid infinite search over duplicate search space. The solution set of a stream CSP can be represented by a Büchi automaton allowing stream values to be non-periodic. Consistency notions are defined to reduce the search space early. We illustrate the feasibility of the framework by examples and experiments.

The minimization problem for propositional formulas is an important optimization problem in the second level of the polynomial hierarchy. In general, the problem is Sigma-2-complete under Turing reductions, but restricted versions are tractable. We study the complexity of minimization for formulas in two established frameworks for restricted propositional logic: The Post framework allowing arbitrarily nested formulas over a set of Boolean connectors, and the constraint setting, allowing generalizations of CNF formulas. In the Post case, we obtain a dichotomy result: Minimization is solvable in polynomial time or coNP-hard. This result also applies to Boolean circuits. For CNF formulas, we obtain new minimization algorithms for a large class of formulas, and give strong evidence that we have covered all polynomial-time cases.

We address a dynamic decision problem in which decision makers must pay some costs when they change their decisions along the way. We formalize this problem as Dynamic SAT (DynSAT) with decision change costs, whose goal is to find a sequence of models that minimize the aggregation of the costs for changing variables. We provide two solutions to solve a specific case of this problem. The first uses a Weighted Partial MaxSAT solver after we encode the entire problem as a WeightedPartial MaxSAT problem. The second solution, which we believe is novel, uses the Lagrangian decomposition technique that divides the entire problem into sub-problems, each of which can be separately solved by an exact Weighted Partial MaxSATsolver, and produces both lower and upper bounds on the optimal in an anytime manner. To compare the performance of these solvers, we experimentedon the random problem and the target trackingproblem. The experimental results show that a solver based on Lagrangian decomposition performs better for the random problem and competitively for the target tracking problem.

Bessiere et al. (AAAI'08) showed that several intractable global constraints can be efficiently propagated when certain natural problem parameters are small. In particular, the complete propagation of a global constraint is fixed-parameter tractable in k — the number of holes in domains — whenever bound consistency can be enforced in polynomial time; this applies to the global constraints AtMost-NValue and Extended Global Cardinality (EGC). In this paper we extend this line of research and introduce the concept of reduction to a problem kernel, a key concept of parameterized complexity, to the field of global constraints. In particular, we show that the consistency problem for AtMost-NValue constraints admits a linear time reduction to an equivalent instance on O(k 2 ) variables and domain values. This small kernel can be used to speed up the complete propagation of NValue constraints. We contrast this result by showing that the consistency problem for EGC constraints does not admit a reduction to a polynomial problem kernel unless the polynomial hierarchy collapses.

We examine the complexity of constraint satisfaction problems that consist of a set of AllDiff constraints. Such CSPs naturally model a wide range of real-world and combinatorial problems, like scheduling, frequency allocations and graph coloring problems. As this problem is known to be NP-complete, we investigate under which further assumptions it becomes tractable. We observe that a crucial property seems to be the convexity of the variable domains and constraints. Our main contribution is an extensive study of the complexity of Multiple AllDiff CSPs for a set of natural parameters, like maximum domain size and maximum size of the constraint scopes. We show that, depending on the parameter, convexity can make the problem tractable while it is provably intractable in general.

Lazy clause generation is a powerful approach to reducing search in constraint programming. This is achieved by recording sets of domain restrictions that previously led to failure as new clausal propagators. Symmetry breaking approaches are also powerful methods for reducing search by recog- nizing that parts of the search tree are symmetric and do not need to be explored. In this paper we show how we can successfully combine symmetry breaking methods with lazy clause generation. Further, we show that the more precise nogoods generated by a lazy clause solver allow our combined approach to exploit redundancies that cannot be exploited via any previous symmetry breaking method, be it static or dynamic.

Such problems are that each relation R can be defined by a Boolean combination frequently intractable, but there are several important of equations over the signature,, andc, which are set CSPs that are known to be polynomial-time function symbols for intersection, union, and complementation, tractable. We introduce a large class of set CSPs respectively. Details of the formal definition and many that can be solved in quadratic time. Our class, examples of set constraint languages can be found in Section which we call EI, contains all previously known 3. The choice of N is just for notational convenience; tractable set CSPs, but also some new ones that as we will see, we could have selected any infinite set for are of crucial importance for example in description our purposes. In the following, a set constraint satisfaction logics. The class of EI set constraints has an problem (set CSP) is a problem of the form CSP(Γ) for a elegant universal-algebraic characterization, which set constraint language Γ. It has been shown by Marriott and we use to show that every set constraint language Odersky [Marriott and Odersky, 1996] that all set CSPs are that properly contains all EI set constraints already contained in NP; they also showed that the largest set constraint has a finite sublanguage with an NPhard constraint language, which consists of all relations that can be satisfaction problem.

The Partner Units Problem is a specific type of configuration problem with important applications in the area of surveillance and security. In this work we show that a special case of the problem, that is of great interest to our partners in industry, can directly be tackled via a structural problem decompostion method. Combining these theoretical insights with general purpose AI techniques such as constraint satisfaction and SAT solving proves to be particularly effective in practice.

This paper examines an extended double auction model where market clearing is restricted by temporal constraints. It is found that the allocation problem in this model can be effectively transformed into a weighted bipartite matching in graph theory. By using the augmentation technique, we propose a Vickrey-Clarke-Groves (VCG) mechanism in this model and demonstrate the advantages of the payment compared with the classical VCG payment (the Clarke pivot payment). We also show that the algorithms for both allocation and payment calculation run in polynomial time. It is expected that the method and results provided in this paper can be applied to the design and analysis of dynamic double auctions and futures markets.