Andrea Schaerf

AIIM Journal 2012 Journal Article

Modeling and solving the dynamic patient admission scheduling problem under uncertainty

• Sara Ceschia
• Andrea Schaerf

Objective Our goal is to propose and solve a new formulation of the recently-formalized patient admission scheduling problem, extending it by including several real-world features, such as the presence of emergency patients, uncertainty in the length of stay, and the possibility of delayed admissions. Method We devised a metaheuristic approach that solves both the static (predictive) and the dynamic (daily) versions of this new problem, which is based on simulated annealing and a complex neighborhood structure. Results The quality of our metaheuristic approach is compared with an exact method based on integer linear programming. The main outcome is that our method is able to solve large cases (up to 4000 patients) in a reasonable time, whereas the exact method can solve only small/medium-size instances (up to 250 patients). For such datasets, the two methods obtain results at the same level of quality. In addition, the gap between our (dynamic) solver and the static one, which has all information available in advance, is only 4–5%. Finally, we propose (and publish on the web) a large set of new instances, and we discuss the impact of their features in the solution process. Conclusion The metaheuristic approach proved to be a valid search method to solve dynamic problems in the healthcare domain.

ECAI Conference 2006 Conference Paper

A Study on the Short-Term Prohibition Mechanisms in Tabu Search

• Luca Di Gaspero
• Marco Chiarandini
• Andrea Schaerf

Tabu Search (TS) is a well known local search method which has been widely used for solving AI problems. Different versions of TS have been proposed in the literature, and many features of TS have been considered and tested experimentally. The feature that is present in almost all TS variants is the so called (short-term) tabu list which is recognised as the crucial issue of TS. However, the definition of the parameters associated with the tabu list remains in most TS applications still a handcrafted activity. In this work we undertake a systematic study of the relative influence of few relevant tabu list features on the performances of TS solvers. In particular, we apply statistical methods for the design and analysis of experiments. The study focuses on a fundamental theoretical problem (GRAPH COLOURING) and on one of its practical specialisation (EXAMINATION TIMETABLING), which involves specific constraints and objectives. The goal is to determine which TS features are more critical for the good performance of TS in a general context of applicability. The general result is that, when the quantitative parameters are well tuned, the differences with respect to qualitative parameters become less evident.

AIJ Journal 2005 Journal Article

Compiling problem specifications into SAT

• Marco Cadoli
• Andrea Schaerf

We present a compiler that translates a problem specification into a propositional satisfiability test (SAT). Problems are specified in a logic-based language, called np-spec, which allows the definition of complex problems in a highly declarative way, and whose expressive power is such as to capture all problems which belong to the complexity class NP. The target SAT instance is solved using any of the various state-of-the-art solvers available from the community. The system obtained is an executable specification language for all NP problems which shows interesting computational properties. The performance of the system has been tested on a few classical problems, namely graph coloring, Hamiltonian cycle, job-shop scheduling, and on a real-world scheduling application, namely the tournament scheduling problem.

IJCAI Conference 1997 Conference Paper

Combining Local Search and Look-Ahead for Scheduling and Constraint Satisfaction Problems

• Andrea Schaerf

We propose a solution technique for scheduling and constraint satisfaction problems that combines backtracking-free constructive methods and local search techniques. Our technique incrementally constructs the solution, performing a local search on partial solutions each time the construction reaches a dead-end. Local search on the space of partial solutions is guided by a cost function based on three components: the distance to feasibility of the partial solution, a look-ahead factor, and (for optimization problems) a lower bound of the objective function. In order to improve search effectiveness, we make use of an adaptive relaxation of constraints and an interleaving of different lookahead factors. The new technique has been successfully experimented on two real-life problems: university course scheduling and sport tournament scheduling.

ECAI Conference 1996 Conference Paper

Scheduling Sport Tournaments using Constraint Logic Programming

• Andrea Schaerf

AAAI Conference 1996 Conference Paper

Tabu Search Techniques for Large High-School Timetabling Problems

• Andrea Schaerf

The high-school timetabling problem consists in assigning all the lectures of a high school to the time periods in such a way that no teacher (or class) is involved in more than one lecture at a time and other side constraints are satisfied. The problem is NPcomplete and is usually tackled using heuristic methods. This paper describes a solution algorithm (and its implementation) based on Z’ abzr Search. The algorithm interleaves different types of modes and makes use of an adaptive relaxation of the hard constraints. The implementation of the algorithm has been successfully experimented in some large high schools with various kinds of side constraints.