| Vol-451 Copyright © 2009 for the individual papers by the papers' authors. Copying permitted for private and academic purposes. Re-publication of material from this volume requires permission by the copyright owners.

# Experimental Evaluation of Algorithms for Solving Problems
with Combinatorial Explosion (RCRA-2008)

### Proceedings of the 15th RCRA workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion
Udine, Italy, December 12-13, 2008.

Edited by

### Marco Gavanelli *
Toni Mancini **

* Università di Ferrara, Dipartimento di Ingegneria, Via Saragat 1, 44100 Ferrara, Italy
** Sapienza Università di Roma, Dipartimento di Informatica, Via Salaria 113, 00198 Roma, Italy

Organized by

### the RCRA working group (Rappresentazione della conoscenza e Ragionamento Automatico, Knowledge representation and automatic reasoning) of the Italian Association for Artificial Intelligence

## Table of Contents

1. CNF Instances from the Software Package Installation Problem
   Josep Argelich, Ines Lynce
2. Experimental Evaluation of Modern Variable Selection Strategies in Constraint Satisfaction Problems
   Thanasis Balafoutis, Kostas Stergiou
3. A Statistical Analysis of the Features of a Dynamic Tabu Search Algorithm for Course Timetabling Problems
   Ruggero Bellio, Luca Di Gaspero, Andrea Schaerf
4. Distributed Cluster Tree Elimination
   Ismel Brito and Pedro Meseguer
5. EasyAnalyzer: an Object-Oriented Framework for the Experimental Analysis of Stochastic Local Search Algorithms
   Luca Di Gaspero, Andrea Roli, Andrea Schaerf.
   Also appearing in Proceedings of Engineering Stochastic Local Search Algorithms (SLS 2007), volume 4638 of Lecture Notes in Computer Science, pages 76-90. Springer, 2007. DOI: 10.1007/978-3-540-74446-7_6.
6. Solving Satisfiability Problems with Qualitative Preferences: A new Approach.
   Emanuele Di Rosa, Enrico Giunchiglia, Marco Maratea.
   Also appearing as A new Approach for Solving Satisfiability Problems with Qualitative Preferences, in Proceedings of the 18th European Conference on Artificial Intelligence (ECAI 2008), pages 510-514. IOS Press, 2008. DOI: 10.3233/978-1-58603-891-5-510.
7. Look-back Techniques for ASP Programs with Aggregates
   Wolfgang Faber, Nicola Leone, Marco Maratea, Francesco Ricca
8. Efficient Plan Adaptation through Replanning Windows and Heuristic Goals
   Alfonso Gerevini, Ivan Serina
9. Preprocessing Techniques for QBFs
   Enrico Giunchiglia, Paolo Marin, Massimo Narizzano
10. Computing #2-SAT of Grids, Grid-Cylinders and Grid-Tori Boolean Formulas
    C. Guillen, A. Lopez Lopez, G. De Ita
11. Verification from Declarative Specifications Using Logic Programming
    Marco Montali, Paolo Torroni, Marco Alberti, Federico Chesani, Marco Gavanelli, Evelina Lamma, and Paola Mello.
    Also appearing in Proceedings of the 24th International Conference on Logic Programming (ICLP 2008), volume 5366 of Lecture Notes in Computer Science, pages 440-454. Springer, 2008. DOI: 10.1007/978-3-540-89982-2_39.
12. Combinatorial Optimization Solutions for the Maximum Quartet Consistency Problem
    Antonio Morgado, Joao Marques Silva
13. Belief Merging without Distance Measures
    Maria del Pilar Pozos Parra, Veronica Borja Macias
14. Treewidth: A Useful Marker of Empirical Hardness in Quantified Boolean Logic Encodings
    Luca Pulina, Armando Tacchella.
    Also appearing in Proceedings of the 15th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2008), volume 5330 of Lecture Notes in Computer Science, pages 528-542. Springer, 2008. DOI: 10.1007/978-3-540-89439-1_37.
15. The SLGAD Procedure for Inference on Logic Programs with Annotated Disjunctions
    Fabrizio Riguzzi
16. A SAT-based Method for Solving the Two-dimensional Strip Packing Problem
    Takehide Soh, Katsumi Inoue, Naoyuki Tamura, Mutsunori Banbara, Hidetomo Nabeshima
17. Experiencing ASP with Real World Applications
    Giorgio Terracina, Erika De Francesco, Claudio Panetta, Nicola Leone
18. Solving Dynamic Constraint Satisfaction Problems by Identifying Stable Features
    Richard Wallace, Diarmuid Grimes, Eugene Freuder

06-May-2009: submitted by Marco Gavanelli and Toni Mancini
07-May-2009: published on CEUR-WS.org