You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Experimental evaluation of algorithms for solving problems with combinatorial explosion

This special issue of AI Communications publishes extended versions of the best papers orally presented at the 21st RCRA International Workshop (RCRA 2014).

RCRA 2014 was held in Vienna, Austria, on 17 and 18 July 2014 as a workshop of the Federated Logic Conference (FLoC 2014) and part of the Vienna Summer of Logic (VSL). The workshop was co-located with three major VSL conferences:

  • the 17th International Conference on Theory and Applications of Satisfiability Testing (SAT 2014),

  • the 30th International Conference on Logic Programming (ICLP 2014), and

  • the 7th International Joint Conference on Automated Reasoning (IJCAR 2014).

The RCRA 2014 workshop title was “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,1 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 [17].

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).

Acknowledgements

We would like to thank the authors who submitted papers to this special issue and express our appreciation for all submissions, which were impressive, both in quantity and quality. We are very grateful to the RCRA 2014 Programme Committee members and to the external referees listed above for their high quality reviews, which provided many valuable suggestions to the authors.

Special thanks are due to the chairs of SAT 2014, ICLP 2014, IJCAR 2014 and to the organisers of FLoC and VSL. Finally, we would like to express our gratitude to Eva Onaindia and Daniele Magazzeni, Editors-in-Chief of AI Communications and to Maria Fox, former Editor-in-Chief of the Journal, for their support throughout the whole process.

References

1 

[[1]] M. Gavanelli and T. Mancini, RCRA 2007: Experimental evaluation of algorithms for solving problems with combinatorial explosion, Journal of Algorithms 63(1–3) (2008), 1–2.

2 

[[2]] M. Gavanelli and T. Mancini, RCRA 2008: Experimental evaluation of algorithms for solving problems with combinatorial explosion, Fundamenta Informaticae 102(3–4) (2010), i–ii.

3 

[[3]] M. Gavanelli and T. Mancini, 17th RCRA International Workshop on “Experimental evaluation of algorithms for solving problems with combinatorial explosion”, Annals of Mathematics and Artificial Intelligence 62(3–4) (2011), 159–160.

4 

[[4]] M. Gavanelli and T. Mancini, 18th RCRA International Workshop on “Experimental evaluation of algorithms for solving problems with combinatorial explosion”, AI Communications 25(2) (2012), 73–74.

5 

[[5]] M. Gavanelli, T. Mancini and A. Pettorossi, RCRA 2009: Experimental evaluation of algorithms for solving problems with combinatorial explosion, Fundamenta Informaticae 107(2–3) (2011).

6 

[[6]] T. Mancini, M. Maratea and F. Ricca, 20th RCRA International Workshop on “Experimental evaluation of algorithms for solving problems with combinatorial explosion”, JETAI 27(5) (2015), 501–502.

7 

[[7]] T. Mancini and A. Oddi, Experimental evaluation of algorithms for solving problems with combinatorial explosion, AI Communications 28(2) (2015), 159–160.