Scatter search for the profile minimization problem

TitleScatter search for the profile minimization problem
Publication TypeJournal Article
Year of Publication2015
AuthorsSánchez-Oro, J., M. Laguna, A. Duarte, and R. Martí
Start Page10

We study the problem of minimizing the profile of a graph and develop a solution method by following the tenets of scatter search. Our procedure exploits the net- work structure of the problem and includes strategies that produce a computationally efficient and agile search. Among several mechanisms, our search includes path relinking as the basis for combining solutions to gener- ate new ones. The profile minimization problem (PMP) is NP-Hard and has relevant applications in numerical anal- ysis techniques that rely on manipulating large sparse matrices. The problem was proposed in the early 1970s but the state-of-the-art does not include a method that could be considered powerful by today’s computing stan- dards. Extensive computational experiments show that we have accomplished our goal of pushing the envelope and establishing a new standard in the solution of the PMP.

Full text: