Let a set of n fixed length intervals and a set of n (larger) windows, in one-to-one correspondence with the intervals, be given, and assume that each interval can be assigned any position within its window. If the position of each interval has been fixed, the intersection graph of such set of intervals is an interval graph. By varying the position of each interval in all possible ways, we get a family of interval graphs. We shall define some optimization problems related to the clique, stability, chromatic, clique cover numbers and cardinality of the minimum dominating set of the interval graphs in the family, mainly focusing on complexity aspects, bounds and solution algorithms. Some problems are proved to be NP-hard, others are solved in polynomial time on some particular classes of instances, which are characterized in the paper. Many practical applications can be reduced to these kind of problems, which seems to be a new interesting modeling framework.

Slides presentation

Collaborators: Sara Nicoloso (IASI-CNR, Roma)

List of papers

1. Malucelli, F. and S. Nicoloso. Shiftable intervals. in ICGT 2000. 2000. Marseille; extended abstract in the Electronic Notes in Discrete Mathematics, full paper submitted to Discrete Mathematics
2. Bonfiglio, P., F. Malucelli and S. Nicoloso, The dominating set problem on Shiftable Interval Graphs, 461 (1997) IASI - CNR, Roma (revised version 2000)
3. Malucelli, F. and S. Nicoloso, Shiftable interval graphs, 435 (1996) IASI - CNR, Roma. (revised version 2000)
   

Given a combinatorial optimization problem instance and a feasible target solution, we want to determine the minimum perturbation of the costs so that the given target solution is optimal. We consider the matroid problems. The solution of the inverse problem give rise to a new matroid (called Base Matroid). An efficient solution algorithm is proposed.

Collaborators: Mauro Dell'amico (Università di Modena e Reggio Emilia), Francesco Maffioli (DEI, Politecnico di Milano).

List of papers

1. Dell'Amico, M., F. Maffioli and F. Malucelli, The Base-Matroid and Inverse Combinatorial Optimization Problem, (1999) DSMI - Università di Modena e Reggio Emilia.

We propose a general scheme to derive heuristics for the Set Covering Problem. The scheme is iterative and embeds constructive heuristics within a randomized procedure. A first group of heuristics is obtained by randomizing the choices made at each step when the solution is constructed in a way similar to that of the so called "Ant System"; a second group of more efficient heuristics is obtained by introducing a random perturbation of the costs of the problem instance. Some computational results are presented. Different parallel implementations of the algorithms are discussed and some performance measures reported.

This kind of general heuristic sheme has been applied also to a problem arising in managing a flexible transit system.

Collaborators: Stella Catalano

1. List of papers
   Fiorenzo Catalamo, M. S. and F. Malucelli, Parallel randomized heuristics for the set covering, (2000) accepted for publication in International Journal of Computer Research.
2. Fiorenzo Catalano, M. S., F. Malucelli, Randomized heuristic shemes for the set covering, DEI - Politecnico di Milano (working paper 2000).
3. Fiorenzo Catalano, M. S. and F. Malucelli, Parallel Implementations of a class of heuristics for the set covering problem, in Scienza e Supercalcolo al CINECA: Rapporto 1995, CINECA, Editor. 1995, Bologna.