A new variant of the classic capacitated facility location problem, which considers incompatibilities between customers, has recently been introduced in the literature. This problem captures the situation where given pairs of customers cannot be served by the same facility. Such a feature is crucial for many practical cases of location problems, such as the presence of hazardous or polluting materials or contention between competing costumers. In this paper, we propose a Large Neighborhood Search (LNS) method to solve this problem. Within the framework of LNS, we introduce three different destroy operators and we use an exact solver in the repair phase. We critically analyze the effectiveness and the efficiency of both destroy and repair operators. The experimental analysis shows that our new method outperforms existing state-of-the-art metaheuristics, providing new best solutions for all available benchmark instances.

We propose a novel Multi-Neighborhood Simulated Annealing approach to address the Capacitated Dispersion Problem. It makes use of three neighborhoods, adapted from similar proposals from the literature. Our search method, properly engineered and tuned, is able to consistently improve the state-of-the-art methods on almost all instances from public benchmarks. In addition, we highlight the limitations of the current datasets and we propose a new, more challenging one, obtained by sampling data from real maps and population density. Finally, we propose two compact mathematical models that obtain good bounds on small/medium size instances as well as, with long runs, on large ones.

The Second International Timetabling Competition (TTC2007) opened in August 2007. Building on the success of the first competition in 2002, this sequel aimed to further develop research activity in the area of educational timetabling. The broad aim of the competition was to create better understanding between researchers and practitioners by allowing emerging techniques to be developed and tested on real-world models of timetabling problems. To support this, a primary goal was to provide researchers with models of problems faced by practitioners through incorporating a significant number of real-world constraints. Another objective of the competition was to stimulate debate within the widening timetabling research community. The competition was divided into three tracks to reflect the important variations that exist in educational timetabling within higher education. Because these formulations incorporate an increased number of “real-world” issues, it is anticipated that the competition will now set the research agenda within the field. After finishing in January 2008, final results were made available in May 2008. Along with background to the competition, the competition tracks are described here along with a brief overview of the techniques used by the competition winners.

Abstract Local search is a paradigm for search and optimization problems, which has recently evidenced to be very effective for a large number of combinatorial problems. Despite the increasing interest of the research community in this subject, there is still a lack of a widely‐accepted software tools for local search. We propose EASYLOCAL, an object‐oriented framework for the design and the analysis of local‐search algorithms. The abstract classes that compose the framework specify and implement the invariant part of the algorithm and are meant to be specialized by concrete classes that supply the problem‐dependent part. The framework provides the full control structures of the algorithms, and the user has only to write the problem‐specific code. Furthermore, the framework comes with some tools that simplify the analysis of the algorithms. The architecture of EASYLOCAL provides a principled modularization for the solution of combinatorial problems by local search and helps the user by deriving a neat conceptual scheme of the application. It also supports the design of combinations of basic techniques and/or neighborhood structures. The framework has been tested in some applicative domains and has proved to be flexible enough in the implementation of algorithms for the solution of various scheduling problems. Copyright © 2003 John Wiley & Sons, Ltd.

Local search is an emerging paradigm for combinatorial search which has recently been shown to be very effective for a large number of combinatorial problems. It is based on the idea of navigating the search space by iteratively stepping from one solution to one of its neighbors, which are obtained by applying a simple local change to it. In this paper we present LOCAL++, an object-oriented framework to be used as a general tool for the development and implementation of local search algorithms in C++. The framework comprises a hierarchy of abstract template classes, one for each local search technique taken into account (i.e. hill-climbing, simulated annealing and tabu search). Each class specifies and implements the invariant part of the algorithm built according to the technique, and is supposed to be specialized by a concrete class once a given search problem is considered, so as to implement the problem-dependent part of the algorithm. LOCAL++ comprises also a set of abstract classes for creating new techniques by combining different search techniques and different neighborhood relations. The architecture of LOCAL++ provides a principled modularization for the solution of combinatorial search problems, and helps the designer deriving a neat conceptual scheme of the application, thus facilitating the development and debugging phases. LOCAL++ proved to be flexible enough for the implementation of the algorithms solving various scheduling problems. Copyright © 2000 John Wiley & Sons, Ltd.

The high school timetabling problem regards the weekly scheduling for all the lectures of a high school. The problem consists in assigning lectures to periods in such a way that no teacher (or class) is involved in more than one lecture at a time, and other constraints are satisfied. The problem is NP-complete and is usually tackled using heuristic methods, This paper describes a solution algorithm (and its implementation) based on local search techniques. The algorithm alternates different techniques and different types of moves and makes use of an adaptive relaxation of the hard constraints. The implementation of the algorithm has been successfully experimented with in some large high schools with various kinds of side constraints.

We describe here an implemented small programming language, called Alma-O, that augments the expressive power of imperative programming by a limited number of features inspired by the logic programming paradigm. These additions encourage declarative programming and make it a more attractive vehicle for problems that involve search. We illustrate the use of Alma-O by presenting solutions to a number of classical problems, including α-β search, STRIPS planning, knapsack, and Eight Queens. These solutions are substantially simpler than their counterparts written in the imperative or in the logic programming style and can be used for different purposes without any modification. We also discuss here the implementation of Alma-O and an operational, executable, semantics of a large subset of the language.

We augment the expressive power of imperative programming in order to make it a more attractive vehicle for problems that involve search. The proposed additions are limited yet powerful and are inspired by the logic programming paradigm. We illustrate their use by presenting solutions to a number of classical problems, including the straight search problem, the knapsack problem, and the 8 queens problem. These solutions are substantially simpler than their counterparts written in the conventional way and can be used for different purposes without any modification.The proposed language is an intermediate stage on the road towards a realization of a strongly typed constraint programming language that combines the advantages of the logic programming and imperative programming.

We study the process of multi-agent reinforcement learning in the context ofload balancing in a distributed system, without use of either centralcoordination or explicit communication. We first define a precise frameworkin which to study adaptive load balancing, important features of which are itsstochastic nature and the purely local information available to individualagents. Given this framework, we show illuminating results on the interplaybetween basic adaptive behavior parameters and their effect on systemefficiency. We then investigate the properties of adaptive load balancing inheterogeneous populations, and address the issue of exploration vs.exploitation in that context. Finally, we show that naive use ofcommunication may not improve, and might even harm system efficiency.

It is a common opinion that subsumption is the central reasoning task in frame-based knowledge representation languages (or concept languages). Intuitively, a concept C subsumes another concept D if the set of objects represented by C is a superset of the one represented by D. When individual objects are taken into account, the basic deductive task for retrieving information from a knowledge base is instance checking, that amounts to checking whether the knowledge base implies that an individual is an instance of a given concept. In this paper, we address the question of whether instance checking can be solved by means of subsumption algorithms. We do so by considering several languages where subsumption belongs to different complexity classes. For such languages we present methods for the instance checking problem, provide a complexity analysis of this problem, and compare it with the subsumption problem. The main result of the paper is that instance checking is not always easily reducible to subsumption. In particular, there are cases where it is strictly harder than subsumption. This impacts on the design of reasoning algorithms for knowledge representation systems based on concept languages.

Terminological knowledge representation systems (TKRSs) are tools for designing and using knowledge bases that make use of terminological languages (or concept languages). We analyze from a theoretical point of view a TKRS whose capabilities go beyond the ones of presently available TKRSs. The new features studied, often required in practical applications, can be summarized in three main points. First, we consider a highly expressive terminological language, called ALCNR, including general complements of concepts, number restrictions and role conjunction. Second, we allow to express inclusion statements between general concepts, and terminological cycles as a particular case. Third, we prove the decidability of a number of desirable TKRS-deduction services (like satisfiability, subsumption and instance checking) through a sound, complete and terminating calculus for reasoning in ALCNR-knowledge bases. Our calculus extends the general technique of constraint systems. As a byproduct of the proof, we get also the result that inclusion statements in ALCNR can be simulated by terminological cycles, if descriptive semantics is adopted.