Linear programs for constraint satisfaction problems

A novel representation is described that models some important NP-hard problems, such as the propositional satisfiability problem (SAT), the Traveling Salesperson Problem (TSP), the Quadratic Assignment Problem (QAP), and the Minimal Set Covering Problem (MSCP) by means of only two types of constraints: ‘choice constraints’ and ‘exclusion constraints’. In its main section the paper presents an approach for solving an m-CNF-SAT problem (Conjunctive Normal Form Satisfaction: n variables, p clauses, clause length m) by integer programming. The approach is unconventional, because 2n distinct 0–1 variables are used for each clause of the m-CNF-SAT problem. The constraint matrix A forces that for every clause exactly one 0–1 variable is set equal to 1 (choice constraint), and no two 0–1 variables, representing a literal and its complement, are both set equal to 1 (exclusion constraints). The particular m-CNF-SAT instance is coded in a cost vector, which serves for maximization of the number of satisfied clauses. The paper presents a modification of the Simplex for solving the obtained integer program. A main theorem of the paper is that this algorithm always finds a 0–1 integer solution. A solution of the integer program corresponds to a solution of the m-CNF-SAT and vice versa. The results of significant experimental tests are reported, and the procedure is compared to other approaches. The same modelling technique is then used for the Traveling Salesperson Problem, for the Minimal Set Covering, and for the Quadratic Assignment Problem: it is shown that a uniform approach is thus useful.     

Sharp thresholds for constraint satisfaction problems and homomorphisms

We determine under which conditions certain natural models of random constraint satisfaction problems have sharp thresholds of satisfiability. These models include graph and hypergraph homomorphism, the (d,k,t)‐model, and binary constraint satisfaction problems with domain size three. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

The complexity of recursive constraint satisfaction problems

We investigate the complexity of finding solutions to infinite recursive constraint satisfaction problems. We show that, in general, the problem of finding a solution to an infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through a recursive tree. We also identify natural classes of infinite recursive constraint satisfaction problems where the problem of finding a solution to the infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through finitely branching recursive trees or recursive binary trees. There are a large number of results in the literature on the complexity of the problem of finding an infinite path through a recursive tree. Our main result allows us to automatically transfer such results to give equivalent results about the complexity of the problem of finding a solution to a recursive constraint satisfaction problem.     

Conditional lexicographic orders in constraint satisfaction problems

The lexicographically-ordered CSP (“lexicographic CSP” or “LO-CSP” for short) combines a simple representation of preferences with the feasibility constraints of ordinary CSPs. Preferences are defined by a total ordering across all assignments, such that a change in assignment to a given variable is more important than any change in assignment to any less important variable. In this paper, we show how this representation can be extended to handle conditional preferences in two ways. In the first, for each conditional preference relation, the parents have higher priority than the children in the original lexicographic ordering. In the second, the relation between parents and children need not correspond to the importance ordering of variables. In this case, by obviating the “overwhelming advantage” effect with respect to the original variables and values, the representational capacity is significantly enhanced. For problems of the first type, any of the algorithms originally devised for ordinary LO-CSPs can also be used when some of the domain orderings are dependent on assignments to “parent” variables. For problems of the second type, algorithms based on lexical orders can be used if the representation is augmented by variables and constraints that link preference orders to assignments. In addition, the branch-and-bound algorithm originally devised for ordinary LO-CSPs can be extended to handle CSPs with conditional domain orderings.     

A scaling algorithm for polynomial constraint satisfaction problems

Good scaling is an essential requirement for the good behavior of many numerical algorithms. In particular, for problems involving multivariate polynomials, a change of scale in one or more variable may have drastic effects on the robustness of subsequent calculations. This paper surveys scaling algorithms for systems of polynomials from the literature, and discusses some new ones, applicable to arbitrary polynomial constraint satisfaction problems.     

The SAT-UNSAT transition for random constraint satisfaction problems

We study threshold phenomena for a large class of random constraint satisfaction problems over finite domains. Our main contribution is a complete classification of the nature (sharp or coarse) of the SAT-UNSAT transition for random Boolean CSPs, which is based on easily decidable properties.     

Linear phase transition in random linear constraint satisfaction problems

Our model is a generalized linear programming relaxation of a much studied random K-SAT problem. Specifically, a set of linear constraints on K variables is fixed. From a pool of n variables, K variables are chosen uniformly at random and a constraint is chosen from also uniformly at random. This procedure is repeated m times independently. We are interested in whether the resulting linear programming problem is feasible. We prove that the feasibility property experiences a linear phase transition, when n and m = cn for a constant c. Namely, there exists a critical value c^* such that, when c < c^*, the problem is feasible or is asymptotically almost feasible, as n, but, when c>c^*, the distance to feasibility is at least a positive constant independent of n. Our result is obtained using the combination of a powerful local weak convergence method developed in Aldous [Ald92], [Ald01], Aldous and Steele [AS03], Steele [Ste02] and martingale techniques. By exploiting a linear programming duality, our theorem implies the following result in the context of sparse random graphs G(n, cn) on n nodes with cn edges, where edges are equipped with randomly generated weights. Let (n, c) denote maximum weight matching in G(n, cn). We prove that when c is a constant and n , the limit lim_n (n, c)/n, exists, with high probability. We further extend this result to maximum weight b-matchings also in G(n, cn).     

ACCPM with a nonlinear constraint and an active set strategy to solve nonlinear multicommodity flow problems

This paper proposes an implementation of a constrained analytic center cutting plane method to solve nonlinear multicommodity flow problems. The new approach exploits the property that the objective of the Lagrangian dual problem has a smooth component with second order derivatives readily available in closed form. The cutting planes issued from the nonsmooth component and the epigraph set of the smooth component form a localization set that is endowed with a self-concordant augmented barrier. Our implementation uses an approximate analytic center associated with that barrier to query the oracle of the nonsmooth component. The paper also proposes an approximation scheme for the original objective. An active set strategy can be applied to the transformed problem: it reduces the dimension of the dual space and accelerates computations. The new approach solves huge instances with high accuracy. The method is compared to alternative approaches proposed in the literature. An erratum to this article can be found at     

Improving degree-based variable ordering heuristics for solving constraint satisfaction problems

In this paper, we improved two classical degree-based variable ordering heuristics, \(\frac{\textit{Dom}}{\textit{Ddeg}}\) and \(\frac{\textit{Dom}}{\textit{Wdeg}}\). We propose a method using the summation of constraint tightness in degree-based heuristics. We also propose two methods to calculate dynamic constraint tightness for binary extensional constraints and non-binary intensional constraints respectively. Our work shows how constraint tightness can be practically used to guide search. We performed a number of experiments on some benchmark instances. The results have shown that, the new heuristics improve the classical ones by both computational time and search tree nodes and they are more efficient than some other successful heuristics on the instances where the classical heuristics work well.     

The satisfiability threshold for randomly generated binary constraint satisfaction problems

We study two natural models of randomly generated constraint satisfaction problems. We determine how quickly the domain size must grow with n to ensure that these models are robust in the sense that they exhibit a non‐trivial threshold of satisfiability, and we determine the asymptotic order of that threshold. We also provide resolution complexity lower bounds for these models. One of our results immediately yields a theorem regarding homomorphisms between two random graphs. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Algebra complexity problems involving graph homomorphism,semigroups and the constraint satisfaction problem

In this paper, we connect the constraint satisfaction problem with other complexity problems, like the polynomial equivalence problem for combinatorial 0-simple semigroups, the graph retraction problem and the geometry problem. We show that every constraint satisfaction problem is polynomially equivalent to an easily formulated algebra complexity problem. As an application we prove that the polynomial equivalence problem (word problem) for the 2×2 matrices over the two element field is co-NP-complete.     

The property of being polynomial for Mal’tsev constraint satisfaction problems

A combinatorial constraint satisfaction problem aims at expressing in unified terms a wide spectrum of problems in various branches of mathematics, computer science, and AI. The generalized satisfiability problem is NP-complete, but many of its restricted versions can be solved in a polynomial time. It is known that the computational complexity of a restricted constraint satisfaction problem depends only on a set of polymorphisms of relations which are admitted to be used in the problem. For the case where a set of such relations is invariant under some Mal’tsev operation, we show that the corresponding constraint satisfaction problem can be solved in a polynomial time. __________ Translated from Algebra i Logika, Vol. 45, No. 6, pp. 655–686, November–December, 2006.     

On the solution‐space geometry of random constraint satisfaction problems

For various random constraint satisfaction problems there is a significant gap between the largest constraint density for which solutions exist and the largest density for which any polynomial time algorithm is known to find solutions. Examples of this phenomenon include random k‐SAT, random graph coloring, and a number of other random constraint satisfaction problems. To understand this gap, we study the structure of the solution space of random k‐SAT (i.e., the set of all satisfying assignments viewed as a subgraph of the Hamming cube). We prove that for densities well below the satisfiability threshold, the solution space decomposes into an exponential number of connected components and give quantitative bounds for the diameter, volume, and number.© 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 251–268, 2011     

Combining column generation and constraint programming to solve the tail assignment problem

Within the area of short term airline operational planning, Tail Assignment is the problem of assigning flight legs to individual identified aircraft while satisfying all operational constraints, and optimizing some objective function. In this article, we propose that Tail Assignment should be solved as part of both the short and the long term airline planning. We further present a hybrid column generation and constraint programming solution approach. This approach can be used to quickly produce solutions for operations management, and also to produce close-to-optimal solutions for long and mid term planning scenarios. We present computational results which illustrate the practical usefulness of the approach.     

Comparison of agent-based scheduling to look-ahead heuristics for real-time transportation problems

We consider the real-time scheduling of full truckload transportation orders with time windows that arrive during schedule execution. Because a fast scheduling method is required, look-ahead heuristics are traditionally used to solve these kinds of problems. As an alternative, we introduce an agent-based approach where intelligent vehicle agents schedule their own routes. They interact with job agents, who strive for minimum transportation costs, using a Vickrey auction for each incoming order. This approach offers several advantages: it is fast, requires relatively little information and facilitates easy schedule adjustments in reaction to information updates. We compare the agent-based approach to more traditional hierarchical heuristics in an extensive simulation experiment. We find that a properly designed multi-agent approach performs as good as or even better than traditional methods. Particularly, the multi-agent approach yields less empty miles and a more stable service level.     

Using Lin's method to solve Bykov's problems

We consider nonwandering dynamics near heteroclinic cycles between two hyperbolic equilibria. The constituting heteroclinic connections are assumed to be such that one of them is transverse and isolated. Such heteroclinic cycles are associated with the termination of a branch of homoclinic solutions, and called T-points   in this context. We study codimension-two T-points and their unfoldings in Rⁿ${\mathbb{R}}^n$. In our consideration we distinguish between cases with real and complex leading eigenvalues of the equilibria. In doing so we establish Lin's method as a unified approach to (re)gain and extend results of Bykov's seminal studies and related works. To a large extent our approach reduces the study to the discussion of intersections of lines and spirals in the plane.     

Using mathematical programming to solve large ranking problems

This paper introduces a mathematical programming model that overcomes the major methodological problem of a large ranking task: respondent fatigue and deteriorated decision quality caused by an excessive number of objects to be ranked. The model was applied to the problem of ranking Marketing and International Business journals. There are more than 200 such journals, making direct ranking or rating very difficult, if not impossible. The result shows that the mathematical programming model uses very little information and yet can produce rankings that are in agreement with results obtained from direct ranking studies.