CSP problems as algorithmic benchmarks: measures, methods and models
Universitat de Lleida. Departament d'Informàtica i Enginyeria Industrial
MetadataShow full item record
On Computer Science research, traditionally, most efforts have been devoted to research hardness for the worst case of problems (proving NP completeness and comparing and reducing problems between them are the two most known). Artifcial Intelligence research, recently, has focused also on how some characteristics of concrete instances have dramatic effects on complexity and hardness while worst-case complexity remains the same. This has lead to focus research efforts on understanding which aspects and properties of problems or instances affect hardness, why very similar problems can require very diferent times to be solved. Research search based problems has been a substantial part of artificial intelligence research since its beginning. Big part of this research has been focused on developing faster and faster algorithms, better heuristics, new pruning techniques to solve ever harder problems. One aspect of this effort to create better solvers consists on benchmarking solver performance on selected problem sets, and, an, obviously, important part of that benchmarking is creating and defining new sets of hard problems. This two folded effort, on one hand to have at our disposal new problems, harder than previous ones, to test our solvers, and on the other hand, to obtain a deeper understanding on why such new problems are so hard, thus making easier to understand why some solvers outperform others, knowledge that can contribute towards designing and building better and faster algorithms and solvers. This work deals with designing better, that is harder and easy to generate, problems for CSP solvers, also usable for SAT solvers. In the first half of the work general concepts on hardness and CSP are introduced, including a complete description of the chosen problems for our study. This chosen problems are, Random Binary CSP Problems (BCSP), Quasi-group Completion Problems (QCP), Generalised Sudoku Problems (GSP), and a newly defined problem, Edge-Matching Puzzles (GEMP). Although BCSP and QCP are already well studied problems, that is not the case with GSP and GEMP. For GSP we will define new creation methods that ensure higher hardness than standard random methods. GEMP on the other hand is a newly formalised problem, we will define it, will provide also algorithms to build easily problems of tunable hardness and study its complexity and hardness. On the second part of the work we will propose and study new methods to increase the hardness of such problems. Providing both, algorithms to build harder problems and an in-depth study of the effect of such methods on hardness, specially on resolution time.
European research projects
- Tesis Doctorals 
Showing items related by title, author, creator and subject.
Ansótegui Gil, Carlos José; Argelich Romà, Josep; Béjar Torres, Ramón; Mateu Piñol, Carles; Planes Cid, Jordi; Ribó i Balust, Josep M. (Josep Maria) (2012)L’objectiu d’aquest curs ´es ser: I Una introducci ´o a tots els conceptes m´es ` etics o filos `ofics del programari lliure i del contingut lliure. I Una mostra de quin ´es el panorama legal referent a la Llei de Propietat ...
Mateu Piñol, Carles; Béjar Torres, Ramón; Fernàndez Camon, César (Springer, 2005)The goal of this work is to try to create a statistical model, based only on easily computable parameters from the CSP problem to predict runtime behaviour of the solving algorithms, and let us choose the best algorithm ...
Fernàndez Camon, César; Manyà Serres, Felip; Mateu Piñol, Carles; Solé Mauri, Francina (Elsevier, 2014)In a world where resources are scarce and urban areas consume the vast majority of these resources, it is vital to make cities greener and more sustainable. A smart city is a city in which information and communications ...