Citing this page:

Use the BibTeX entry:

@Misc{mlcp-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], [3], [4], and [5].

---

Instance Set

The authors in [5] created a benchmark of MLCP instances to evaluate experimentally exact, approximative and heuristic algorithms. This benchmark is divided into 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 MLCP instance files follows the STP Data Format from the SteinLib, which is described in http://steinlib.zib.de/format.php. To use this format it is necessary to reduce the MLCP instances to Steiner tree problem (STP) instances as discussed in the next section.

A corridor (solution) for an MLCP instance, in the form of an STP instance, is represented as a subset of the graph's edge set of the STP instance. Thus, the format of the corridors files is the following: the first line contains an integer n that is the number of edges in the solution, and each of the next n lines corresponds to a solution edge given by its vertex indices (integers).

Each of the gzip compressed tar files below contain all instances (.stp files) of a given type and the best solutions (.crd files) for them found in the experiments in [5]. The files are organized in folders according to the number of rooms. Below the file link another link is available to the web page summarizing the best results obtained in [5] for the instances of that type.

	type1[.tgz] (3.0MB)	type2[.tgz] (3.2MB)	type3[.tgz] (3.5MB)	type4[.tgz] (2.2MB)	type5[.tgz] (2.7MB)
	Results	Results	Results	Results	Results

The results were obtained with the following machine configuration: Intel Core i7-820QM @ 1.73 GHz, 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 (node) 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 artificial edges 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, 42(9):939-951, 2009.
• [2] A. Gonzalez-Gutierrez, T. F. Gonzalez. Complexity of the minimum-length corridor problem. Computational Geometry, 37(2):72-103, 2007.
• [3] A. Gonzalez-Gutierrez, T. F. Gonzalez. Approximating corridors and tours via restriction and relaxation techniques. ACM Transactions on Algorithms, 6(3):(56)1-36, 2010.
• [4] A. Gonzalez-Gutierrez. Complexity of the minimum-length corridor problem. Ph. D. Thesis, University of California, Santa Barbara, CA, USA, 2007.
• [5] 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.

---

Address

Lucas de Oliveira and Cid C. de Souza
Universidade Estadual de Campinas
Instituto de Computação
Avenida Albert Einstein, 1251
13083-852 Campinas, SP, Brasil
Phone: +55 19 3521.5877
Fax: +55 19 3521.5847
e-mail: ,