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.

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.

On my way to Quebec City for CP 2012 and heading for INFORMS 2012 in one week!

I am right now in a bus from Montreal to Quebec City. CP 2012 will officially start on Monday, but a gathering of those who arrived earlier was suggested for tomorrow in the late afternoon. The same happened last year at CPAIOR, and that was one of the reasons why I decide to come as soon as possible: to avoid missing the first gathering again.

I will be presenting a talk and a poster about the application that I approached during my MSc, which is described in a full paper in the conference proceedings. This work helped me being accepted in the CP Doctoral Program, which will promote some events directed to the graduate students attending to the conference and has assigned a mentor to each one. The CP DP organizers were very kind to help a number of us with registration costs and hosting. On top of that, I was told last week that my position paper about characterizing adaptive search methods (a sequel of my extended abstract from CPAIOR 2011) entitled me 2 minutes to give my 2 cents in a panel about the future of CP, which is being organized by Professor Pascal Van Hentenryck. In short, I am really looking forward this meeting!

In the following, I will go to Phoenix for the INFORMS Annual Meeting. I will give two talks there, one of which at the sessions about OR applications in the energy sector of emerging markets, which I am organizing, and the other at the sessions about CP, organized by Professor van Hoeve. I will also contribute to the blog of the conference, which will have as authors many of the usual OR bloggers. As soon as the blog is officially released, I will post the link here. I have interacted with a number of those guys online but I saw very few of them in person so far. Therefore, my expectations for Phoenix are also very high!

CP Mini-Course by Prof. J. Hooker at Unicamp

Prof. John Hooker will stay for about a month at the State University of Campinas (Unicamp). During that period, he will teach a mini-course entitled “Constraint Programming and CP/OR Integration”. For those interested in enrolling in the course, which is limited to 40 students, contact Prof. Cid de Souza according to the instructions that follow. The instructions are in Portuguese, but the course will be taught in English.

Prezad*s colegas,

Gostaria de pedir a vocês que divulgassem aos eventuais interessados o mini-curso de “Constraint Programming and CP/OR Integration” a ser ministrado pelo Prof. John Hooker da Tepper School of Business da Universidade Carnegie Mellon aqui no IC/UNICAMP de 26/09 a 26/10/2012. Detalhes sobre o curso podem ser lidos no texto do anúncio que se encontra no final desta mensagem. Convém chamar a atenção dos interessados sobre os horários e locais das aulas pois estes irão variar de acordo com o dia da semana.

Favor informar a quem quiser fazer o mini-curso que preencha os dados do pequeno formulário abaixo e enviem-no para o meu email (cid@ic.unicamp.br), colocando no assunto (subject) os seguintes dizeres: “Registration: CP Mini-Course by Prof. J. Hooker”.

Como só temos cerca de 40 vagas disponíveis, atenderemos aos pedidos de acordo com a ordem de chegada dos mesmos. Portanto, seria bom que as pessoas interessadas não deixassem para a última hora.

Agradeço a colaboração de vocês e, claro, convido-*s a participar do mini-curso caso tenham interesse e disponibilidade.

Obrigado.

Abraços,

Cid

(corte aqui)
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Formulário de Inscrição no Mini-Curso
———————————————————————-
Nome:
Email:
Informe abaixo sua ocupação atual:
[ ] graduando; Curso: ____; Instituição: _____;
[ ] mestrando; Curso: ____; Instituição: _____; Orientador: ____;
[ ] doutorando; Curso: ____; Instituição: _____; Orientador: ____;
[ ] pós-doutorando; Instituição: _____; Supervisor: ____; Orientador: ____;
[ ] docente; Departamento: ___; Instituição: ____;
[ ] outro; Especificar (cargo, empresa, etc): ____;

Observação: até o dia 16/9 a sua inscrição será confirmada via email.
———————————————————————-
(corte aqui)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Anúncio do Mini-Curso

********************************************************
Mini-Curso: Constraint Programming and CP/OR Integration

Instituto de Computação – UNICAMP

========================================================

>>>>>>>>>>>>>>>>>>>> APOIO: FAPESP <<<<<<<<<<<<<<<<<<<<<
********************************************************

Instrutor:
**********

Prof. Dr. John Hooker
Tepper School of Business, Carnegie Mellon University

Short Bio:
———-

John Hooker is the T. Jerome Holleran Professor of Business Ethics and Social Responsibility and a professor of operations research at the Tepper School of Business. He joined the Tepper School in 1984 and has since held several visiting posts, most recently at the London School of Economics. He holds doctoral degrees in philosophy and operations research.

Professor Hooker has published over 130 articles, 6 books, and 5 edited volumes. In the area of operations research, he has produced pioneering work on the integration of optimization technologies and wrote the first book on the subject. He is also the author of Optimization Methods for Logical Inference and two editions of Integrated Methods for Optimization. He has served on several editorial boards, including two decades as an area editor for INFORMS Journal on Computing. He is an INFORMS Fellow and recipient of the INFORMS Computing Society Prize.

He also has interests in business ethics and cross-cultural management, as reflected in his books Business Ethics as Rational Choice and Working across Cultures. He is founding editor-in-chief of the Journal of Business Ethics Education and co-organized four conferences on international corporate responsibility. He has lived and worked in Australia, China, Denmark, India, Qatar, Turkey, the United Kingdom, the United States, and Zimbabwe, and has extensive experience in Germany and Mexico.

Professor Hooker headed the Tepper School’s undergraduate business administration program from 1996 to 2001 and received a Distinguished Academic Service Award for his contributions. In 2009, he was recognized with an Award for Sustained Teaching Excellence.

Para maiores detalhes ver: http://ba.gsia.cmu.edu/jnh/

Objetivo do Curso:
******************

The goal of this mini-course is to give an opportunity for the researchers and students in the field of Combinatorial Optimization to be brought up to date on the progress that has been made by the CP community in the last years, both theoretically and computationally. The duration of the mini-course will be 16 to 20 hours, divided into 8 to 10 sessions (one per day) of 2 hours each. It will be opened for any researcher interested in the topic and not constrained to the IC/UNICAMP community. However, some limitations may occur due to the physical infrastructure available (size of classrooms, etc).

Conteúdo do Curso:
******************

Constraint Programming
   Basis ideas of constraint programming (CP)
      Global constraints
      Constraint-based processing
      Constraint propagation
      Search
   CP modeling
      Employee scheduling
      Assembly line sequencing
      Resource-constrained scheduling
      Other models
   Consistency
      Strong k-consistency
      Domain consistency
      Bounds consistency
   The element constraint
      Variable subscripts
      Achieving domain consistency
   The alldiff constraint
      Review of network flow theory
      Achieving domain consistency
      Achieving bounds consistency
   The cardinality and nvalues constraints
   The among and sequence constraints
      Filtering based on cumulative sums
      Flow-based filtering
   The stretch constraint
      Dynamic programming model
      Domain filtering
   The regular constraint
      Deterministic finite automata
      Domain filtering
      Filtering by decomposition
   Disjunctive scheduling
      Edge finding rules
      Not-first/not-last rules
   Cumulative scheduling
      Edge finding rules
      Not-first/not-last rules
      Energy-based reasoning

CP/OR integration
   Basic ideas
      Branch, infer, and relax
      Example: freight transport
      Example: production planning
      Example: product configuration
      Example: Routing and frequency assignment
   Inference and relaxation duality
      Example: bounds propagation
      Example: Lagrangian relaxation
   CP-based branch and price
      Example: airline crew scheduling
   Logic-based Benders decomposition
      Example: planning and scheduling

Dias/Horários das Aulas:
************************

Fique atento pois as aulas das quartas e sextas serão em horários e locais diferentes.

Quarta: 26/09, das 18:00 às 20:00 horas, sala 85 IC-2
Sexta.: 28/09, das 10:00 às 12:00 horas, sala 316 IC-3
Quarta: 03/10, das 18:00 às 20:00 horas, sala 85 IC-2
Sexta.: 05/10, das 10:00 às 12:00 horas, sala 316 IC-3
Quarta: 10/10, das 18:00 às 20:00 horas, sala 85 IC-2
Sexta.: 12/10 *************** FERIADO ***************
Quarta: 17/10, das 18:00 às 20:00 horas, sala 85 IC-2
Sexta.: 19/10, das 10:00 às 12:00 horas, sala 316 IC-3
Quarta: 24/10, das 18:00 às 20:00 horas, sala 85 IC-2
Sexta.: 26/10, das 10:00 às 12:00 horas, sala 316 IC-3

Contato:
********

Prof. Cid de Souza (cid@ic.unicamp.br)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
OBSERVAÇÃO: o mini-curso será integralmente ministrado em inglês.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

When CP becomes local search and local search becomes CP, and the same about CP and machine learning

As it is said in a Brazilian song entitled Sobradinho, “o sertão vai virar mar, dá no coração o medo que algum dia o mar também vire sertão [the hinterland will become sea, it comes to the heart the fear that someday the sea also will turn into hinterland]”. However, such an occurrence in the academic field is often reason for joy instead of worries – as well as for joint conferences where you can be delighted by funny flamewars.

In the case of Constraint Programming (CP), I have been observing the development of a strong relationship with local search as well as with machine learning. Coincidentally, while I was writing this post, a presentation of a local search solver at the 2012 ISMP (International Symposium on Mathematical Programming) seems to have caused some buzz on Twitter about local search and CP. To the argument that local search has not been exploited by major commercial solvers (as far as I could understand about the controversy), some observed that there is much of local search embedded inconspicuously in CP solvers etc. In the sequence, the discussion extended to the limits between what is CP and what is not.

However, why do we suppose that such techniques must be mutually exclusive?

From CP to local search…

Local search has been increasingly used within CP solvers, as is the case of Comet and of many papers authored by researchers from IBM describing what is behind CP Optimizer’s curtains. Many of them regard Large Neighborhood Search (LNS) as a must to solve cumulative scheduling problems, i.e., scheduling problems in which many activities can be simultaneously processed by the same resource. LNS is based on separate operators to generate modified solutions from a starting pool of solutions, and to adjust feasibility issues of those modified solutions. This latter type of operator addresses a common drawback of local search: the need to fix what the neighborhood operator unintentionally broke. [check the erratum at the end of the post]

For some, it might look strange to associate CP with local search and detach it from standard systematic techniques. While those techniques are important to tackle combinatorial problems in the general case, the size of many real-world problems is far beyond what it is possible to do in a lifetime. Hence, who cares if the search space is not fully explored by the search procedure if that is more of a theoretical matter than of a practical one? In addition, CP is about exploiting problem constraints, from the modeling with more semantic to the propagation that reduces the search space to the search that attempts to obtain feasible solutions. That leaves plenty of space to define the search according to the constraints in the model.

… and back from local search to CP!

A few weeks ago, I had the chance to observe the opposite trend: I saw a presentation about another commercial local search framework, but this one was using the concept of global constraints. As far as I could grasp, it was not on purpose. In order to reduce the problem of generating invalid solutions with standard local search operators on a broad range of problems, specialized constraints were defined to model certain combinatorial problems whose solutions cannot be modified at random. In other words, they are using specialized operators according to the structure of the problem, what is quite similar to performing propagation with specialized constraints in the context of CP models. As stated previously, the use of global constraints in CP is not only about propagation, but rather about exploiting problem structure for the sake of a better performance. And that is what they did on that local search solver. When I see such coincidences of design, I wonder how powerful but at the same time still unknown is the principle beneath CP.

Now from CP to machine learning…

And since constraints can be leveraged not only to improve propagation but also to improve search, why not mix the latter with the feedback received along the solving process in order to improve the selection of algorithms? That is a topic in which I am very interested: the development of adaptive search methods for constraint solving. It has been studied in great depth for the past decade and a half, and has received even more attention in recent years. One of the venues dedicating space to this topic is the LION (Learning and Intelligent OptimizatioN) conference series, which will have its seventh edition in Catania at the beginning of 2013. That is one of the conferences that I want to attend in the following years (monetary and job vacation constraints prevent my prompt participation).

… and back again to CP!

And if local search and CP each show off in the context of the other, one should expect the same in this case. At least, that seems to be the thought of the proponents of the recent call for papers of the first COCOMILE workshop (COmbining Constraint solving with MIning and LEarning), which will be held next August in Montpellier during the 2012 ECAI (European Conference on Artificial Intelligence). The workshop CFP emphasizes the two-way relationship between both fields. While I know that there exist some research on the CP-machine learning direction (even though I am not following it very closely), I think that a single and very specific event that attempts to look for both directions is of great help to foster further development. And, of course, that is yet another event that I want to attend in a nearby future (hopefully, publishing about at least in one of such directions).

Erratum

The description of LNS as stated in the post is not correct. It would be more precise to define that the first type of operator fixes values for part of the variables, and that the second attempts to find a feasible solution by assigning values to the remaining variables. The prior definition that I gave resembles somewhat what I understand as standard local search operators: procedures that fix the value of all variables on each solution that they generate. In the case of LNS, however, just part of the values is fixed and an iterative process is aimed at complete such partial solution.

Offshore Resources Scheduling and the Brazilian Symposium on Operations Research

On August 17th, I will present an article about what I’ve been working on my M.Sc. thesis at the Brazilian Symposium on Operations Research (shortened SBPO in Brazil). This article is authored by me and some colleagues from work. We are tackling the problem of scheduling offshore resources to develop oil wells with Constraint Programming (CP). It took a great effort to present so much about the problem and how to solve it in a way that it accessible to a broader audience (I hope we have managed to do that). There are four other papers competing for the best paper award. We will try our best there. Anyway, I’m glad by the nomination.

The 2011 SBPO will be held in Ubatuba, a beach town half-way between São Paulo and Rio de Janeiro.