CSP problems as algorithmic benchmarks: measures, methods and models

• Autores: Carlos Mateu Piñol
• Directores de la Tesis: Ramón Béjar Torres (dir. tes.) , César Fernández Camón (dir. tes.)
• Lectura: En la Universitat de Lleida ( España ) en 2009
• Idioma: inglés
• Tribunal Calificador de la Tesis: Felip Manyà Serres (presid.) , María Teresa Alsinet Bernadó (secret.) , Chu-Min Li (voc.) , Manuel Ojeda Aciego (voc.) , Álvaro del Val Latorre (voc.)
• Enlaces
  • Tesis en acceso abierto en: TDX
• Resumen

  • Part of the current research in Arti cial Intelligence is focused in resolving and studying the problems known as search problems, especially the ones which are proven to have non-polinomial hardness (NP).

    Many of these problems (SAT, CSP, etc.) are resolution-based logic search problems, and, interestingly, in many cases, present an explosion of hardness for some instances. Until AI research has centered his eorts in the research related in the worst case of these problems, how to test, for example, the NP-completeness of concrete problems, compare the hardness with other NP problems, that is, in fact, trying to answer the basic question: is N=NP? Recently more and more attention has been devoted to the study of such problems, but not in their worst case but in the typical case, that is, the behaviour of problems in their globality. This is because some instances of problems, spite not having, a priori, more hardness than others, require more (in some cases we are talking of orders of magnitude higher) computation eorts to be solved. The core of the question we try to answer is, for the chosen problems studied, why by simply changing a few simple parameters, the balancing of the distribution of holes in a sudoku, the number of colors in an edge puzzle, etc. the time required to solve those instances boosts, sometimes event making totally impossible to solve the problems.

    Another important aspect of the research in AI is the building of test sets for benchmarking that help to the design of more and better programs and algorithms of resolution. Having available tools for building test sets and benchmarks that allow solver builders to choose hardness, adjust some other parameters as desired, etc. is crucial for the correct development of solving algorithms.

    This thesis contributes to both problems, the one to comprise better the problems hardness and the other one, to create tools to build, as desired, sets of problems, with the selected hardness and having some prede ned characteristics. On the one hand have studied several problems: Random Binary CSP, Generalised Sudoku Problems and Edge Matching Puzzles. We studied which factors contribute to the hardness in the typical case, and modifying these factors one can increase hardness (increases that reach several orders of magnitude in some cases) and we propose explanations of which eect have these factors in the heuristic and algorithms of resolution.On the other hand have designed mechanisms for the systematic and easy building of problem instances, where the researcher can choose, easily, some building parameters that will have a re ection in the structure of the problem as well as in the level of resulting hardness.

    An additional result has been the formalitzation and de nition of a new problem, edge matching puzzles, one variation of the kids puzzles and that have revealed as a structured NP problem easily de ned but with an extraordinary hardness. We have designed three variants of the problem, proposing very ecients mechanisms for building instances of the problem and that allow to obtain always satis able problems as well as normal problems.

    Of this problem we have done also an extensive study of which factors in uence on the hardness of the instances, of how small variations on problem de nitions, for example the number of colors, have a tremendous impact on problem hardness. We have also done an intensive and exhaustive analytical 1 analysis, characterizing and locating the phase transition, as well as, de ning analytic expressions of boundaries of the phase transition