IDEAS home Printed from
   My bibliography  Save this article

Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization


  • Palubeckis, Gintaras
  • Tomkevičius, Arūnas
  • Ostreika, Armantas


Given a bipartite graph, the problem we address, called the bipartite graph crossing minimization problem (BGCMP), is to find an embedding the parts of the graph along two parallel lines so that the number of edge crossings is minimized. It is assumed that each edge is drawn as a straight line segment and edges sharing an end vertex do not cross. We propose an approach for the BGCMP, which combines a simulated annealing (SA) method with a variable neighborhood search (VNS) scheme. These two algorithms are executed iteratively. At each iteration, the solution produced by SA is submitted as input to the VNS component of the approach. Our VNS algorithm uses a local search technique which is based on a fast insertion neighborhood exploration procedure. We show that the time complexity of this procedure is O(n2), where n is the order of the graph. Another fast procedure is proposed for computing the gain in the objective function value obtained by swapping positions of two vertices. We experimentally compare our algorithm (called SA-VNS) against the tabu search algorithm as well as GRASP approach from the literature. Computational results are reported on four sets of bipartite graphs. The results demonstrate the superiority of SA-VNS over the state-of-the-art methods. The source code implementing SA-VNS is made publicly available as a benchmark for future comparisons.

Suggested Citation

  • 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.
  • Handle: RePEc:eee:apmaco:v:348:y:2019:i:c:p:84-101
    DOI: 10.1016/j.amc.2018.11.051

    Download full text from publisher

    File URL:
    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

    1. 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.
    2. 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.
    3. Christoph Buchheim & Angelika Wiegele & Lanbo Zheng, 2010. "Exact Algorithms for the Quadratic Linear Ordering Problem," INFORMS Journal on Computing, INFORMS, vol. 22(1), pages 168-177, February.
    4. Manuel Laguna & Rafael Marti, 1999. "GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization," INFORMS Journal on Computing, INFORMS, vol. 11(1), pages 44-52, February.
    5. Valls, Vicente & Marti, Rafael & Lino, Pilar, 1996. "A branch and bound algorithm for minimizing the number of crossing arcs in bipartite graphs," European Journal of Operational Research, Elsevier, vol. 90(2), pages 303-319, April.
    6. Palubeckis, Gintaras, 2015. "Fast local search for single row facility layout," European Journal of Operational Research, Elsevier, vol. 246(3), pages 800-814.
    7. Hansen, Pierre & Mladenovic, Nenad, 2001. "Variable neighborhood search: Principles and applications," European Journal of Operational Research, Elsevier, vol. 130(3), pages 449-467, May.
    8. repec:spr:coopap:v:68:y:2017:i:3:d:10.1007_s10589-017-9926-5 is not listed on IDEAS
    Full references (including those not matched with items on IDEAS)


    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:apmaco:v:348:y:2019:i:c:p:84-101. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Dana Niculescu). General contact details of provider: .

    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 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.