Tag: Global Constraints

Posted on

The pursuit of asymmetrical models in CP: Backtracking hardness is, after all, a tricky business!

Last week I wrote a post on the effectiveness of using backtracking alone to solve combinatorial problems. It was an interesting exercise to develop the discussion from theory to practice and back to theory again. However, there was a mistake in that development. As pointed by Jean-François Puget in his comment, it is possible to add a small number of symmetry breaking constraints to efficiently refute that class of infeasible instances of the pigeonhole principle used as example. After all, what was actually claimed by the theoretical development that I shortly mentioned is that the refutation of a specific formulation of the problem has an exponential lower-bound. While that could be a case for using a global constraint, it could also be addressed by symmetry breaking.

Symmetries arise naturally in combinatorial problems, but the extent to which they cause concern varies with the solving method used. They matter a lot for backtracking because of their impact in the size of the search space to be explored. We have a formulation with a symmetry breaking constraint if, compared to the formulation without such a constraint, only solutions differing by symmetry from the solutions of the more restricted formulation are feasible for one and not for the other.

There is an intuitive notion that symmetry breaking is a good thing, but care must be taken: what if it makes an easy problem harder? It might be the case that the original problem was underconstrained and additional constraints would rule out exactly the solutions that are easier to find, therefore making the search longer than without them. However, that was not the case of the problem in the previous post and is not likely to be the case in most applications. It is even interesting to ask if there are conditions in which this can be in fact observed.

Nevertheless, symmetry breaking is a bit challenging because it requires taking into account the whole formulation instead of reasoning about each constraint separately. For each symmetry identified in a subproblem, we may come up with an additional constraint that introduces information about the problem context that breaks it. As a consequence, symmetry breaking inference mechanisms cannot be encapsulated within global constraints and we are left with two options: expect good formulations from the modeler or develop some sort of general mechanism to find them.

The current practice is based on the former option, and thus the expertise of the modeler plays an important role in the process. However, the quest for a truly autonomous solver of broader use would demand further advances in the latter possibility. Honestly, I was not aware of the importance of reformulation until thinking about all of this, and it made me look again for Barry O’Sullivan’s paper at AAAI-10 discussing the automation of both modeling and solving. Among recent papers, it is a good start on the topic.

In conclusion, proving that backtracking cannot suffice is a bit trickier that I thought at first. Unless P=NP, there must exist an asymmetrical CSP class (or at least one for which breaking its symmetries would not be an easy problem) with lower-bound refutation asymptotically worst than any polynomial function in the size of the problem. If such a class is yet unknown, the interesting part of looking for it would be to find a number of general inference rules for symmetry breaking that we could use to solve other problems.

Posted on

Why backtracking alone cannot suffice to solve combinatorial problems: CP perspective, empirical hardness models evidence, and proof complexity results

Constraint Programming (CP) is a technique with particular strength to solve classes of combinatorial problems for which global constraints were identified and exploited in the design of specialized algorithms. However, I have been convinced that CP is, above all, a general model to understand combinatorial problems and their solution – using the term ‘model’ in a broader sense, as explained in a previous post and based on John Hooker’s article at CP Letters.

Regardless of the solving method used, the classic aim of CP is to tackle the Constraint Satisfaction Problem (CSP), which ultimately encodes any problem involving variables with discrete and finite values as the intersection of the regular languages defined by each of its constraints. When special properties are observed in a class of such languages that would allow us to make strong and efficient inferences among those variables, we have found one of those so-called global constraints. Not surprisingly, the concept is in fact a formalization of the widespread practice of exploiting problem structure, which was also discussed in a previous post linking the implementation of local search operators to CP concepts.

In spite of such claimed ‘agnosticism’ regarding solving methods, CSP solving is often associated with backtracking search algorithms. The rationale is that, if compared to other general solving techniques like dynamic programming, backtracking scales better in memory use with the size of the problem being solved. As a consequence, CP lectures and many lines of research are developed with the premise of using backtracking-based search. In practice, however, that post on CP and local search also points that the converse is true: local search methods like variable neighborhood search have been successfully used in commercial CP solvers.

One of such lines in which backtracking was extensively studied is the adaptive selection of algorithms, which is aimed to select the most suitable algorithm to solve a given instance according to predictive models of performance. From the characterization of CSP instances by means of properties like constrainedness, which is the ratio of pairwise constraints to variables, empirical hardness models were developed that also documented easy-hard-easy phase transitions. In short, it is easy to solve an unconstrained problem or to infer that an overconstrained one is unfeasible, but those in the ‘feasibility frontier’ are much harder to solve. A short reference about the topic is the 2005 article of Carla Gomes and Bart Selman in Nature entitled ‘Can get satisfaction’, and a precise figure of such hardness can be seen in the graph at slide number 6 of Kevin Leyton-Brown’s talk at the Workshop on Beyond Worst-Case Analysis.

Although a well-documented phenomenon, until very recently it was yet unclear to me why this happens. I was only convinced of it this week, when I came across some lecture notes of KTH Professor Jakob Nordstrom on proof complexity that discussed the resolution of formulas for the pigeonhole principle. Proof complexity is a discipline concerned with understanding the hardness of theorem proving, and comprises the study of characteristics and strengths of different proof systems as well as their equivalence. Among such systems is resolution, which is equivalent to solving through backtracking a CSP in which variables can only assume two values – true or false, or 0 or 1 – and constraints only use the logical operators NOT, OR, and AND in Conjunctive Normal Form (CNF): a set of clauses using NOT and OR joined by AND. This is a special form of the satisfiability problem, or simply SAT, for which the backtracking search with only local inference corresponds to the well-known DPLL algorithm.

The pigeonhole principle states that it is not possible to assign n pigeons into m pigeonholes without putting two of them in the same pigeonhole if n > m. It turns out that encoding an instance of this problem in polynomial size in n and m such that n = m+1 as a satisfiability problem (SAT), i.e., a CSP with variable domains of size two and constraints built of logical operators in CNF, results in an unsatisfiable problem that requires an exponential lower-bound resolution. That happens because a valid refutation requires exploring a large number of combinations of assignments to prove that none would lead to the satisfaction of the problem constraints. [check the erratum at the end of the post]

In short, backtracking really needs global constraints!

Erratum

According to the first comment to this post, there is an enconding for which the mentioned refutation is efficiently found. The discussion is continuned in the sequel of this post.