Experimental evaluation of algorithms for solving problems with combinatorial explosion

1.Workshop aims and scope

Solving problems with combinatorial explosion plays an important role in decision-making, since feasible or optimal decisions often depend on a non-trivial combination of various factors. Generally, an effective strategy for solving such problems is merging different viewpoints adopted in different communities that try to solve similar problems, such that algorithms developed in one research area are applicable to other problems, or can be hybridised with techniques in other areas.

This is one of the aims of the RCRA (Ragionamento Automatico e Rappresentazione della Conoscenza) group,11 the interest group of the Italian Association for Artificial Intelligence (AI*IA) on knowledge representation and automated reasoning, which organises its annual meetings since 1994.

Scope of the RCRA 2014 workshop was fostering the cross-fertilisation of ideas stemming from different areas, proposing benchmarks for new challenging problems, comparing models and algorithms from an experimental viewpoint, and, in general, comparing different approaches with respect to efficiency, problem modelling, and ease of development.

2.History of the workshop series

Since the 2005 edition, the RCRA workshops have focussed on the theme of algorithms in Artificial Intelligence (AI), proposing benchmarks to compare them and evaluating their efficiency through experimental evaluation. These meetings have reached the objective to put together researchers coming from AI fields as diverse as constraint satisfaction, machine learning, logic languages, quantified satisfiability, and planning, just to name a few. The event has gained more and more interest, first from the Italian community, then from the international one.

RCRA 2008 (Udine, Italy) was co-located with the International Conference on Logic Programming (ICLP 2008). RCRA 2009 (Reggio Emilia, Italy) was a workshop of the 11th Conference of the Italian Association for Artificial Intelligence (AI*IA 2009). RCRA 2010 (Bologna, Italy) was in association with the 7th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CP-AI-OR 2010). RCRA 2011 (Barcelona, Spain) was a workshop of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011). RCRA 2012 (Rome, Italy) was held in association with the 12th AI*IA Symposium on Artificial Intelligence (AI*IA 2012). RCRA 2013 was held in Rome, Italy as an autonomous event.

The success of the workshop series shows that RCRA has become a major forum for exchanging ideas and proposing experimentation methodologies for algorithms in AI.

Starting from 2007, after each workshop edition, a special issue of a major International journal was published with extended versions of the best papers [1–7].

3.Articles in this special issue

Fourteen papers were presented at RCRA 2014, and the authors had the possibility to submit extended versions of their papers for possible publication in this special issue. After two rounds of reviews, the following seven papers were selected.

Wallace discusses extensions to Neighbourhood Singleton Arc Consistency, a type of singleton arc consistency for Constraint Satisfaction Problems.

Santucci et al. present a novel discrete Differential Evolution algorithm for variants of the Permutation Flowshop Scheduling Problem.

Pathak et al. experimentally evaluate Probabilistic Model Checking tools to investigate safe reinforcement learning in robots.

Luca Mancini et al. propose an immunization strategy for real scale-free networks (e.g., to prevent virus infections) based on distributed autonomous entities which self-regulate their diffusion in the network.

Erdem et al. perform a systematic analysis of levels of integration between discrete high-level reasoning and continuous low-level feasibility checks to address hybrid planning problems in robotic applications.

Ignatiev et al. study the Maximal Falsifiability problem in propositional logic and its relationships with the MinSAT problem.

Kamal et al. present a Generalized Hypertree Decomposition based solving technique for large non-binary Constraint Satisfaction Problems defined using compressed table constraints.

RCRA 2014 programme committee members.  Mario Alviano, University of Calabria, Rende (Italy); Laura Barbulescu, Carnegie Mellon University (CMU), Pittsburgh, PA (USA); Roman Bartak, Charles University, Prague (Czech Republic); Sara Bernardini, Royal Holloway, University of London (UK); Alessandro Dal Palù, University of Parma (Italy); Francesco Donini, University of Tuscia, Viterbo (Italy); Wolfgang Faber, University of Huddersfield, Huddersfield (UK); Andrea Formisano, University of Perugia (Italy); Marco Gavanelli, University of Ferrara (Italy); Philippe Laborie, ILOG, IBM, Gentilly (France); Yuliya Lierler, University of Nebraska, Omaha (USA); Ines Lynce, INESC-ID (Portugal); Joao Marques-Silva, University of Lisbon (Portugal); Marco Montali, Free University of Bolzano (Italy); Angelo Oddi, National Research Council (CNR), Rome (Italy); Andreas Pieris, University of Oxford (UK); Luca Pulina, University of Sassari (Italy); Daniel Riera, Open University of Catalonia, Barcelona (Spain); Marco Roveri, FBK, Trento (Italy); Francesco Scarcello, University of Calabria, Rende (Italy); Ivan Serina, University of Brescia (Italy); Andrea Schaerf, University of Udine (Italy); Paolo Torroni, University of Bologna (Italy); Mirek Truszczynski, University of Kentucky, Lexington, KY (USA); Stefan Woltran, Vienna University of Technology (Austria).

External referees.  Marco Chiarandini, University of Southern Denmark (Denmark); Agostino Dovier, University of Udine (Italy); George Katsirelos, INRA (France); Zeynep Kiziltan, University of Bologna (Italy); Francesco Lupia, University of Calabria, Rende (Italy); Paolo Marin, University of Freiburg (Germany); Ian Miguel, University of St. Andrews (UK); Barbara Nardi, University of Calabria, Rende (Italy); Eva Onaindia, Polytechnic University of Valencia (Spain); Valentina Poggioni, University of Perugia (Italy); Peter Schüller, Marmara University (Turkey).