IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v200y2010i1p14-27.html
   My bibliography  Save this article

Variable neighbourhood search for bandwidth reduction

Author

Listed:
  • Mladenovic, Nenad
  • Urosevic, Dragan
  • Pérez-Brito, Dionisio
  • García-González, Carlos G.

Abstract

The problem of reducing the bandwidth of a matrix consists of finding a permutation of rows and columns of a given matrix which keeps the non-zero elements in a band as close as possible to the main diagonal. This NP-complete problem can also be formulated as a vertex labelling problem on a graph, where each edge represents a non-zero element of the matrix. We propose a variable neighbourhood search based heuristic for reducing the bandwidth of a matrix which successfully combines several recent ideas from the literature. Empirical results for an often used collection of 113 benchmark instances indicate that the proposed heuristic compares favourably to all previous methods. Moreover, with our approach, we improve best solutions in 50% of instances of large benchmark tests.

Suggested Citation

  • Mladenovic, Nenad & Urosevic, Dragan & Pérez-Brito, Dionisio & García-González, Carlos G., 2010. "Variable neighbourhood search for bandwidth reduction," European Journal of Operational Research, Elsevier, vol. 200(1), pages 14-27, January.
    • Handle: RePEc:eee:ejores:v:200:y:2010:i:1:p:14-27
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(08)01054-0
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Brimberg, J. & Urosevic, D. & Mladenovic, N., 2006. "Variable neighborhood search for the vertex weighted k-cardinality tree problem," European Journal of Operational Research, Elsevier, vol. 171(1), pages 74-84, May.
    2. Pinana, Estefania & Plana, Isaac & Campos, Vicente & Marti, Rafael, 2004. "GRASP and path relinking for the matrix bandwidth minimization," European Journal of Operational Research, Elsevier, vol. 153(1), pages 200-210, February.
    3. Rodriguez-Tello, Eduardo & Hao, Jin-Kao & Torres-Jimenez, Jose, 2008. "An improved simulated annealing algorithm for bandwidth minimization," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1319-1335, March.
    4. Marti, Rafael & Laguna, Manuel & Glover, Fred & Campos, Vicente, 2001. "Reducing the bandwidth of a sparse matrix with tabu search," European Journal of Operational Research, Elsevier, vol. 135(2), pages 450-459, December.
    5. Hansen, Pierre & Mladenovic, Nenad, 2001. "Variable neighborhood search: Principles and applications," European Journal of Operational Research, Elsevier, vol. 130(3), pages 449-467, May.
    6. Marti, Rafael & Campos, Vicente & Pinana, Estefania, 2008. "A branch and bound algorithm for the matrix bandwidth minimization," European Journal of Operational Research, Elsevier, vol. 186(2), pages 513-528, April.
    7. Lim, Andrew & Rodrigues, Brian & Xiao, Fei, 2006. "Heuristics for matrix bandwidth reduction," European Journal of Operational Research, Elsevier, vol. 174(1), pages 69-91, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Behrooz Koohestani & Riccardo Poli, 2015. "Addressing the envelope reduction of sparse matrices using a genetic programming system," Computational Optimization and Applications, Springer, vol. 60(3), pages 789-814, April.
    2. Abraham Duarte & Juan Pantrigo & Eduardo Pardo & Nenad Mladenovic, 2015. "Multi-objective variable neighborhood search: an application to combinatorial optimization problems," Journal of Global Optimization, Springer, vol. 63(3), pages 515-536, November.
    3. Elshaikh, Abdalla & Salhi, Said & Nagy, Gábor, 2015. "The continuous p-centre problem: An investigation into variable neighbourhood search with memory," European Journal of Operational Research, Elsevier, vol. 241(3), pages 606-621.
    4. S. L. Gonzaga de Oliveira & C. Carvalho, 2022. "Metaheuristic algorithms for the bandwidth reduction of large-scale matrices," Journal of Combinatorial Optimization, Springer, vol. 43(4), pages 727-784, May.
    5. Cavero, Sergio & Pardo, Eduardo G. & Duarte, Abraham, 2023. "Efficient iterated greedy for the two-dimensional bandwidth minimization problem," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1126-1139.
    6. Mladenović, Nenad & Kratica, Jozef & Kovačević-Vujčić, Vera & Čangalović, Mirjana, 2012. "Variable neighborhood search for metric dimension and minimal doubly resolving set problems," European Journal of Operational Research, Elsevier, vol. 220(2), pages 328-337.
    7. Guan, Jian & Lin, Geng, 2016. "Hybridizing variable neighborhood search with ant colony optimization for solving the single row facility layout problem," European Journal of Operational Research, Elsevier, vol. 248(3), pages 899-909.
    8. Palubeckis, Gintaras & Tomkevičius, Arūnas & Ostreika, Armantas, 2019. "Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization," Applied Mathematics and Computation, Elsevier, vol. 348(C), pages 84-101.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Vicente Campos & Estefanía Piñana & Rafael Martí, 2011. "Adaptive memory programming for matrix bandwidth minimization," Annals of Operations Research, Springer, vol. 183(1), pages 7-23, March.
    2. Behrooz Koohestani & Riccardo Poli, 2015. "Addressing the envelope reduction of sparse matrices using a genetic programming system," Computational Optimization and Applications, Springer, vol. 60(3), pages 789-814, April.
    3. Michele Samorani & Manuel Laguna, 2012. "Data-Mining-Driven Neighborhood Search," INFORMS Journal on Computing, INFORMS, vol. 24(2), pages 210-227, May.
    4. Rodriguez-Tello, Eduardo & Hao, Jin-Kao & Torres-Jimenez, Jose, 2008. "An improved simulated annealing algorithm for bandwidth minimization," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1319-1335, March.
    5. Lim, Andrew & Rodrigues, Brian & Xiao, Fei, 2006. "Heuristics for matrix bandwidth reduction," European Journal of Operational Research, Elsevier, vol. 174(1), pages 69-91, October.
    6. Marti, Rafael & Campos, Vicente & Pinana, Estefania, 2008. "A branch and bound algorithm for the matrix bandwidth minimization," European Journal of Operational Research, Elsevier, vol. 186(2), pages 513-528, April.
    7. Pierre Hansen & Nenad Mladenović & José Moreno Pérez, 2010. "Variable neighbourhood search: methods and applications," Annals of Operations Research, Springer, vol. 175(1), pages 367-407, March.
    8. Juan Pantrigo & Rafael Martí & Abraham Duarte & Eduardo Pardo, 2012. "Scatter search for the cutwidth minimization problem," Annals of Operations Research, Springer, vol. 199(1), pages 285-304, October.
    9. Sergio Cavero & Eduardo G. Pardo & Abraham Duarte, 2022. "A general variable neighborhood search for the cyclic antibandwidth problem," Computational Optimization and Applications, Springer, vol. 81(2), pages 657-687, March.
    10. S. L. Gonzaga de Oliveira & C. Carvalho, 2022. "Metaheuristic algorithms for the bandwidth reduction of large-scale matrices," Journal of Combinatorial Optimization, Springer, vol. 43(4), pages 727-784, May.
    11. Mladenovic, Nenad & Drazic, Milan & Kovacevic-Vujcic, Vera & Cangalovic, Mirjana, 2008. "General variable neighborhood search for the continuous optimization," European Journal of Operational Research, Elsevier, vol. 191(3), pages 753-770, December.
    12. Santos, Vinícius Gandra Martins & Carvalho, Marco Antonio Moreira de, 2021. "Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem," European Journal of Operational Research, Elsevier, vol. 289(3), pages 1056-1066.
    13. Maenhout, Broos & Vanhoucke, Mario, 2010. "A hybrid scatter search heuristic for personalized crew rostering in the airline industry," European Journal of Operational Research, Elsevier, vol. 206(1), pages 155-167, October.
    14. Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico, 2018. "Minimizing Piecewise-Concave Functions Over Polyhedra," Mathematics of Operations Research, INFORMS, vol. 43(2), pages 580-597, May.
    15. Amina Lamghari & Roussos Dimitrakopoulos & Jacques Ferland, 2015. "A hybrid method based on linear programming and variable neighborhood descent for scheduling production in open-pit mines," Journal of Global Optimization, Springer, vol. 63(3), pages 555-582, November.
    16. Patricia Domínguez-Marín & Stefan Nickel & Pierre Hansen & Nenad Mladenović, 2005. "Heuristic Procedures for Solving the Discrete Ordered Median Problem," Annals of Operations Research, Springer, vol. 136(1), pages 145-173, April.
    17. Ali Shahabi & Sadigh Raissi & Kaveh Khalili-Damghani & Meysam Rafei, 2021. "Designing a resilient skip-stop schedule in rapid rail transit using a simulation-based optimization methodology," Operational Research, Springer, vol. 21(3), pages 1691-1721, September.
    18. Ting Pong & Hao Sun & Ningchuan Wang & Henry Wolkowicz, 2016. "Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem," Computational Optimization and Applications, Springer, vol. 63(2), pages 333-364, March.
    19. Wilson, Duncan T. & Hawe, Glenn I. & Coates, Graham & Crouch, Roger S., 2013. "A multi-objective combinatorial model of casualty processing in major incident response," European Journal of Operational Research, Elsevier, vol. 230(3), pages 643-655.
    20. Felipe, Ángel & Ortuño, M. Teresa & Righini, Giovanni & Tirado, Gregorio, 2014. "A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 71(C), pages 111-128.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:200:y:2010:i:1:p:14-27. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.