Name
Abstract | ||
|---|---|---|
A 1-block in a binary matrix is any maximal sequence of 1s occurring consecutively in the same row. Consecutive block minimization (CBM) requires a permutation of the matrix columns that minimizes the number of 1-blocks. CBM is NP-hard for matrices with a maximum of two 1s per row and an arbitrary number of 1s per column. First, we prove that it is NP-hard even when it is restricted to binary matrices having a maximum of two 1s per row and a maximum of three 1s per column. In these circumstances, a reasonable and traditional approach to solve the problem is to design a heuristic capable of finding good configurations within acceptable computation times. This paper proposes an Iterated Local Search (ILS) metaheuristic. A binary matrix satisfies the strong consecutive ones property (is strongly C1P) if its non-zero entries occur consecutively in each row. It is C1P if there is a permutation of its columns such that the resulting matrix is strongly C1P. In this study, two necessary conditions for a binary matrix to be C1P are provided, each allowing to define a neighborhood for local search (LS). In addition, a third large-scale neighborhood is proposed where the local optimal solution can be directly obtained by solving a Traveling Salesman Problem (TSP). It is noteworthy that the three neighborhoods are being proposed for the first time. The ILS algorithm is tested on a dataset from the OR-library, composed of thirty large-scale set covering instances of varying sizes and densities. Comparison with two TSP solvers as well as with a recently published metaheuristic, from both accuracy and computing time points of view, allows to conclude that the proposed method competes favorably with the methods available in the literature. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.cor.2021.105273 | COMPUTERS & OPERATIONS RESEARCH |
Keywords | DocType | Volume |
Consecutive block minimization, Iterated local search, Large-scale neighborhood, Traveling salesman problem solver | Journal | 131 |
ISSN | Citations | PageRank |
0305-0548 | 0 | 0.34 |
References | Authors | |
0 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Salim Haddadi | 1 | 0 | 0.34 |