IC-UNICAMP

# Minimum Length Corridor Problem - Benchmark Instances, by L. de Oliveira and C. C. de Souza

Use the BibTeX entry:

@Misc{symbolmaps-instances-page,
author = {Lucas de Oliveira and Cid C. de Souza},
title = {Minimum Length Corridor Problem -- Benchmark Instances},
year = {2012},
note = {{\sl www.ic.unicamp.br/\$\sim\$cid/Problem-instances/MinCorridor}}
}

### Problem description

In the Minimum Length Corridor Problem (MLCP) we are given a rectilinear polygon P and a set of minor rectilinear polygons forming a connected subdivision S of P. A solution to this problem, also called corridor, is a connected set C of segments that are edges of S and such that each inner face (room) of S is intersected by at least one segment in C. The goal is to find a corridor for which the sum of the lengths of its segments is as small as possible. The image below shows an instance of the problem with the segments in bold representing a corridor (solution) for this instance. Further details about the problem can be found in [1], [2] and [3].

### Instance Set

The authors in [3] created a benchmark of MLCP instances to evaluate experimentally exact, approximative and heuristic algorithms. This benchmark is divided in five instance sets, each one containing instances of an specific type (1, 2, 3, 4 and 5), as described in the section 9.1 of this reference. For each type, there are seventy five instances grouped according to the number of rooms (faces) in the subdivision S: 100, 200, ... , 1400 or 1500 rooms. In each of these groups, the five instances are named with integers from 1 to 5.

The format of the instance files follows the one from the SteinLib and described in http://steinlib.zib.de/format.php. To use this format it is necessary to reduce the MLCP instances to Steiner tree problem instances as discussed in the next section.

Each of the zipped files below contain all instances of a given type, organized in folders according to the number of rooms. Below the zip file link another link is available to the web page summarizing the results obtained in [3] for the instances of that type.

 type1[.zip] (2.34MB) type2[.zip] (2.48MB) type3[.zip] (2.71MB) type4[.zip] (1.62MB) type5[.zip] (1.94MB) Results Results Results Results Results

The results were obtained with the following machine configuration: Intel Core i7-820QM, 8GB RAM, Fedora Linux 14, ILOG CPLEX 12.1.

### Reduction to Steiner tree problem

The reduction procedure is described by the following steps:

(1) Construct a graph G where there is one vertex representing each vertex of S. For each edge e in S, add an edge in G incident to the vertices representing the endpoints of e, and let the weight of this edge in G equals the euclidean distance of e.
(2) For each vertice v in G with degree two, consider u and w as the vertices adjacent to v. Create an edge linking u and w with weight equals to the sum of the two incident edges in v, and remove v from G.
(3) For each face (room) f in S, let S(f) be the set of vertices in G that represent vertices in S that lie on this face. Create a terminal vertex v in G and add an artificial edge linking this vertex with all vertices in F(f). The weight of the artificial edges must be set (theoretically) to infinity.

The result is a Steiner tree problem instance comprising the graph G generated with terminal vertex set containing all the artificial vertices created in the step 3.

Below there is an example to illustrate the procedure. The euclidean length in the figure represents the weight of solid edges in the graphs, and for dashed edges consider infinite weights. The gray vertices are the terminals.

### Acknowledgments

This research was supported by FAPESP – Fundação de Amparo à Pesquisa do Estado de São Paulo – Grants #2010/06720-7, CNPq – Conselho Nacional de Desenvolvimento Científico e Tecnológico – Grants #132185/2010-5.

### References

• [1] H. L. Bodlaender, C. Feremans, A. Grigoriev, E. Penninkx, R. Sitters, e T. Wolle. On the minimum corridor connection problem and other generalized geometric problems. Computational Geometry: Theory and Applications, 42(9):939-951, November 2009.
• [2] A. Gonzalez-Gutierrez. Complexity of the minimum-length corridor problem. Ph. D. Thesis, University of California, Santa Barbara, CA, USA, 2007.
• [3] L. Oliveira. O Problema do Corredor de Comprimento Mínimo: Algoritmos Exatos, Aproximativos e Heurísticos. Master's Thesis, State University of Campinas, Campinas, SP, Brazil, 2012.