logo

SCIENTIA SINICA Informationis, Volume 51 , Issue 4 : 582(2021) https://doi.org/10.1360/SSI-2019-0122

A dynamic programming-based local search algorithm for solving the dynamic bipartite drawing problem

More info
  • ReceivedApr 9, 2019
  • AcceptedAug 5, 2019
  • PublishedMar 18, 2021

Abstract


Funded by

中央高校基本科研业务费专项资金(JBK1901011,JBK190504)

智能信息处理与实时工业系统湖北省重点实验室基金(znxx2018QN01)


Acknowledgment

感谢Rafael Martí教授为本文提供测试算例和对比算法的实验数据.


References

[1] Antonellis I, Molina H G, Chang C C. Simrank+. Proc VLDB Endow, 2008, 1: 408-421 CrossRef Google Scholar

[2] Even G, Guha S, Schieber B. Improved approximations of crossings in graph drawings and VLSI layout areas. SIAM J Comput, 2003, 32: 231--252. Google Scholar

[3] Oselio B, Kulesza A, Hero A O. Multi-layer graph analytics for social networks. In: Proceedings of the 5th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), 2013. 284--287. Google Scholar

[4] Burch M, Müller C, Reina G, et al. Visualizing dynamic call graphs. 2012. http://www.profitippliga.de/papers/31.pdf. Google Scholar

[5] Erten C, Harding P J, Kobourov S G, et al. Graphael: graph animations with evolving layouts. In: Proceedings of International Symposium in Graph Drawing, 2003. 98--110. Google Scholar

[6] Garey M R, Johnson D S. Crossing Number is NP-Complete. SIAM J Algebraic Discrete Methods, 1983, 4: 312-316 CrossRef Google Scholar

[7] Eades P, Kelly D. Heuristics for drawing 2-layered networks. Ars Combin, 1986, 21: 89--98. Google Scholar

[8] Jünger M, Mutzel P. 2-layer straightline crossing minimization: performance of exact and heuristic algorithms. J Graph Alg Appl, 1997, 1: 1--25. Google Scholar

[9] Martí R, Estruch V. Incremental bipartite drawing problem. Comput Operations Res, 2001, 28: 1287-1298 CrossRef Google Scholar

[10] Martí R, Martínez-Gavara A, Sánchez-Oro J. Tabu search for the dynamic Bipartite Drawing Problem. Comput Operations Res, 2018, 91: 1-12 CrossRef Google Scholar

[11] Martí R, Campos V, Hoff A. Heuristics for the min-max arc crossing problem in graphs. Expert Syst Appl, 2018, 109: 100-113 CrossRef Google Scholar

[12] Napoletano A, Martínez-Gavara A, Festa P. Heuristics for the Constrained Incremental Graph Drawing Problem. Eur J Operational Res, 2019, 274: 710-729 CrossRef Google Scholar

[13] Sánchez-Oro J, Martínez-Gavara A, Laguna M. Variable neighborhood scatter search for the incremental graph drawing problem. Comput Optim Appl, 2017, 68: 775-797 CrossRef Google Scholar

[14] Wang Z, Lü Z P, Ye T. Local search algorithms for large-scale load balancing problems in cloud computing. Sci Sin Inform, 2015, 45: 587-604 CrossRef Google Scholar

[15] Cai S, Luo C, Lin J. New local search methods for partial MaxSAT. Artificial Intelligence, 2016, 240: 1-18 CrossRef Google Scholar

[16] Cai S W, Hou W Y, Lin J K, et al. Improving local search for minimum weight vertex cover by dynamic strategies. In: Proceedings of International Joint Conference on Artificial Intelligence, 2018. 1412--1418. Google Scholar

[17] Lü Z, Hao J K. A memetic algorithm for graph coloring. Eur J Operational Res, 2010, 203: 241-250 CrossRef Google Scholar

[18] Stallmann M, Brglez F, Ghosh D. Heuristics, Experimental Subjects, and Treatment Evaluation in Bigraph Crossing Minimization. J Exp Algorithmics, 2001, 6: 8-42 CrossRef Google Scholar

  • Figure 1

    (Color online) An example (GB_1_rnd1_01_0001_20 instance) of two solutions for a two-layered graph. (a) the first solution (64 crossing edges); (b) the second solution (44 crossing edges)

  • Figure 2

    (Color online) An example of the DP-LS method for selecting several independent neighborhood moves

  • Figure 5

    (Color online) Insert vertex $v$ immediately before (upwards) vertex $u_{j-1}$ or $u_{j}$

  • Table 1   Results of DP-LS in comparison with the reference algorithms (i.e., GRASP, TS+PR, and Gurobi) for the 22 typical instances
    GRASP TS+PR Gurobi DP-LS
    $n_1$ $n_2$ Density $\gamma$ Best known Cross Time (s) GAP (%) Cross Time (s) GAP (%) Cross Time (s) GAP (%) Cross Time (s) GAP (%)
    25 25 0.065 1.2 305 316 6.1 3.6 305 0.4 0 305 0.4 0 305 0.01 0
    25 25 0.065 1.6 979 1131 34.5 15.5 1106 1.8 13 979 237.7 0 980 1.17 0.1
    25 25 0.175 1.2 3922 4037 36.9 2.9 3927 0.4 0.1 3922 1.4 0 3922 0.01 0
    25 25 0.175 1.6 11982 12374 120 3.3 11982 3.8 0 12444 1800.6 3.9 11794 0.18 $-$1.57
    25 25 0.3 1.2 15036 15185 60.9 1 15067 0.6 0.2 15036 9.6 0 15036 0 0
    25 25 0.3 1.6 39657 40538 252.2 2.2 39657 7.7 0 41705 1801.6 5.2 39465 0.11 $-$0.48
    25 50 0.065 1.2 2173 2218 27.8 2.1 2185 0.7 0.6 2173 1.5 0 2173 0.04 0
    25 50 0.175 1.2 19794 20112 201.7 1.6 19861 2.1 0.3 19794 193.3 0 19794 0.01 0
    25 50 0.3 1.2 62986 64113 495.3 1.8 63312 4.8 0.5 62986 1802.3 0 61813 0.02 $-$1.86
    25 50 0.3 1.6 175764 175764 519 0 176909 52.8 0 184788 1831.6 4.5 172837 0.04 $-$1.67
    50 25 0.065 1.2 2169 2230 42.2 2.8 2191 0.8 1 2169 1.6 0 2169 0.03 0
    50 25 0.065 1.6 5828 6459 267.3 10.8 5828 12.4 0 6155 1801 5.6 5552 0.25 $-$4.74
    50 25 0.175 1.2 19831 20265 228.9 2.2 19890 2 0.3 19831 336.2 0 19831 0.03 0
    50 25 0.175 1.6 54004 57004 517.7 5.6 54004 31.3 0 63287 1802.4 17.2 53396 0.26 $-$1.13
    50 25 0.3 1.2 65593 66253 502.8 1 65593 4.4 0 66319 1802 1.1 65557 0.04 $-$0.05
    50 25 0.3 1.6 179282 186429 538.6 4 179282 58.6 0 189119 1805.3 5.5 176557 0.23 $-$1.52
    50 50 0.065 1.2 7637 7859 297.3 2.9 7664 3.9 0.4 7637 3.5 0 7637 0.01 0
    50 50 0.065 1.6 24933 25545 506.5 2.5 24933 67 0 27110 1802.8 8.7 24103 6.66 $-$3.33
    50 50 0.175 1.2 77253 78717 505.5 1.9 77253 14.3 0 77480 1802.7 0.3 77205 0.02 $-$0.06
    50 50 0.175 1.6 233326 238979 504.1 2.4 233326 209.3 0 256917 1808.6 10.1 230789 2.27 $-$1.09
    50 50 0.3 1.2 248454 251277 536.8 1.1 248454 26.1 0 258330 1806.3 4 248172 0.06 $-$0.11
    50 50 0.3 1.6 712459 728794 575.7 2.3 712459 416.7 0 757750 1800.3 6.4 709286 1.44 $-$0.45
    #Avg 89243.95 91163.59 308.08 3.34 89326.72 41.90 0.75 94374.36 1102.40 3.30 88562.41 0.59 $-$0.82
    #Best 0 1 9 21
    $p$-value 2.73e$-$06 4.59e$-$06 1.35e$-$3
  •   

    Algorithm 1 The main framework of the dynamic programming based local search (DP-LS)

    Input: $G=({\rm~IV},{\rm~IE})$;

    Output: The best found solution $S^{\rm~best}$.

    Randomly generate an initial solution $S$;

    $\theta$ $\leftarrow$ 0;

    while the maximum number of consecutive non-improving global optima is not reached ($\theta~<~\Theta$) do

    $S^{*}$ $\leftarrow$ dpls$(S)$;

    if the optimum solution $S^{*}$ is better than the optimum solution $S^{\rm~best}$ then

    $S^{\rm~best}$ $\leftarrow$ $S^{*}$;

    $\theta$ $\leftarrow$ 0;

    else

    $\theta$ $\leftarrow$ $\theta~+~1$;

    end if

    $S$ $\leftarrow$ Perturbation($S^{\rm~best}$);

    end while

    return $S^{\rm~best}$.

  •   

    Algorithm 1 The main framework of the dynamic programming based local search (DP-LS)

    Input: $G=({\rm~IV},{\rm~IE})$;

    Output: The best found solution $S^{\rm~best}$.

    Randomly generate an initial solution $S$;

    $\theta$ $\leftarrow$ 0;

    while the maximum number of consecutive non-improving global optima is not reached ($\theta~<~\Theta$) do

    $S^{*}$ $\leftarrow$ dpls$(S)$;

    if the optimum solution $S^{*}$ is better than the optimum solution $S^{\rm~best}$ then

    $S^{\rm~best}$ $\leftarrow$ $S^{*}$;

    $\theta$ $\leftarrow$ 0;

    else

    $\theta$ $\leftarrow$ $\theta~+~1$;

    end if

    $S$ $\leftarrow$ Perturbation($S^{\rm~best}$);

    end while

    return $S^{\rm~best}$.

  • Table 2   Results of DP-LS in comparison with algorithm TS+PR and the general solver Gurobi on 9 large-scale instances with 471 vertices
    TS+PR Gurobi DP-LS
    Instance name Best known Cross Time (s) GAP (%) Cross Time (s) GAP (%) Cross Time (s) GAP (%)
    G_00_05_scr_0014_10 47050 47587 524.49 1.14 47050 1829.01 0 46796 1.34 $-$0.54
    G_00_05_scr_0014_20 39523 41740 578.29 5.61 39523 1827.62 0 38235 7.06 $-$3.26
    G_00_05_scr_0014_30 36446 36446 710.91 0 48446 1830.41 32.93 32201 15.89 $-$11.65
    G_00_05_scr_0015_10 45343 45803 534.58 1.01 45343 1864.35 0 45016 0.21 $-$0.72
    G_00_05_scr_0015_20 40142 40142 582.47 0 47580 1836.25 18.53 37629 6.65 $-$6.26
    G_00_05_scr_0015_30 36948 36948 679.92 0 46733 1840.15 26.48 32256 22.29 $-$12.7
    G_00_05_scr_0016_10 44822 44822 512.09 0 53518 1832.23 19.4 43228 0.20 $-$3.56
    G_00_05_scr_0016_20 42348 42348 575.57 0 47913 1836.74 13.14 39222 16.87 $-$7.38
    G_00_05_scr_0016_30 37349 37349 685.11 0 47236 1835.91 26.47 31925 16.09 $-$14.52
    #Avg 41107.89 41465 598.16 0.86 47038 1836.96 15.22 38500.89 9.63 $-$6.73
    #Best 0 0 9
    $p$-value 2.7e$-$3 2.7e$-$3
  •   

    Algorithm 2 The main search procedure of the DPLS algorithm dpls$(S)$

    Input: The current solution $S$;

    Output: The local optimal solution $S^{*}$.

    $S^{*}$ $\leftarrow$ $S$;

    $k$ $\leftarrow$ 1;

    ${\rm~noimprove}\_{\rm~layer}$ $\leftarrow$ 0;

    while the termination condition (i.e., There is no better neighborhood solution for both the first and second layers: ${\rm~noimprove}\_{\rm~layer}$ $\ge$ 2) is not reached do

    According to Eq. (12), calculate the maximum improvement value ${\rm~dp}_k(n_k)$ corresponding to the independent neighborhood move combination (Without loss of generality, assume that the optimal neighborhood move combination contains $q$ neighborhood moves, i.e., ${\rm~Move}_1,~~{\rm~Move}_2,~~\ldots,~~{\rm~Move}_q$);

    if $q$ = 0 then

    ${\rm~noimprove}\_{\rm~layer}~\leftarrow~{\rm~noimprove}\_{\rm~layer}~+~1$;

    else

    $S~\leftarrow~S~\oplus~{\rm~Move}_1~\oplus~{\rm~Move}_2~\oplus~\cdots~\oplus~{\rm~Move}_q$;

    $S^{*}~\leftarrow~S$;

    ${\rm~noimprove}\_{\rm~layer}~\leftarrow~0$;

    end if

    if $k~=~1$ then

    $k~\leftarrow~2$;

    else

    $k~\leftarrow~1$;

    end if

    end while

    return $S^{*}$.

  •   

    Algorithm 2 The main search procedure of the DPLS algorithm dpls$(S)$

    Input: The current solution $S$;

    Output: The local optimal solution $S^{*}$.

    $S^{*}$ $\leftarrow$ $S$;

    $k$ $\leftarrow$ 1;

    ${\rm~noimprove}\_{\rm~layer}$ $\leftarrow$ 0;

    while the termination condition (i.e., There is no better neighborhood solution for both the first and second layers: ${\rm~noimprove}\_{\rm~layer}$ $\ge$ 2) is not reached do

    According to Eq. (12), calculate the maximum improvement value ${\rm~dp}_k(n_k)$ corresponding to the independent neighborhood move combination (Without loss of generality, assume that the optimal neighborhood move combination contains $q$ neighborhood moves, i.e., ${\rm~Move}_1,~~{\rm~Move}_2,~~\ldots,~~{\rm~Move}_q$);

    if $q$ = 0 then

    ${\rm~noimprove}\_{\rm~layer}~\leftarrow~{\rm~noimprove}\_{\rm~layer}~+~1$;

    else

    $S~\leftarrow~S~\oplus~{\rm~Move}_1~\oplus~{\rm~Move}_2~\oplus~\cdots~\oplus~{\rm~Move}_q$;

    $S^{*}~\leftarrow~S$;

    ${\rm~noimprove}\_{\rm~layer}~\leftarrow~0$;

    end if

    if $k~=~1$ then

    $k~\leftarrow~2$;

    else

    $k~\leftarrow~1$;

    end if

    end while

    return $S^{*}$.

  • Table 3   Results of DP-LS in comparison with the reference algorithms (i.e., GRASP, TS(500)+PR, TS+PR, and Gurobi) on the first instance set with $\gamma~=~1.2$ and $1.6$
    Size $(n_1+n_2)$ Algorithm $\gamma~=~1.2$ $\gamma~=~1.6$ #Best
    ACross ATime (s) AGP (%) ACross ATime (s) AGP (%)
    Gurobi 6230.00 27.18 0.00 18553.53 1224.33 4.24
    GRASP 6317.47 33.23 2.17 18056.27 141.83 7.44
    50 TS(500)+PR 6232.20 48.76 0.10 17459.13 1039.53 1.01
    TS+PR 6234.33 8.15 0.16 17489.07 90.12 1.71
    DP-LS 6230.00 0.03 0.00 17376.8 0.74 0.54
    Gurobi 28522.20 781.71 0.24 84088.57 1808.00 7.50
    GRASP 28776.57 228.98 2.52 80917.97 409.31 5.15
    75 TS(500)+PR 28379.10 621.53 0.16 78959.23 1718.27 0.27
    TS+PR 28390.17 61.11 0.21 79161.07 386.90 0.61
    DP-LS 28359.93 0.02 0.09 77791.53 1.24 $-$1.21
    Gurobi 112572.27 1207.01 1.10 343478.67 1891.89 8.70
    GRASP 111381.07 423.60 1.94 328878.53 532.43 3.86
    100 TS(500)+PR 110214.33 1516.66 0.08 322528.33 1687.68 0.00
    TS+PR 110233.07 292.30 0.12 322831.60 514.51 0.23
    DP-LS 110172.60 0.41 $-$0.04 319628.67 3.97 $-$0.89
    #Total TS(500)+PR 83888.83 1121.52 7 (120)
    DP-LS 83213.88 0.96 119 (120)
  • Table 4   Performance results of DP-LS in comparison with the reference algorithms (i.e., GRASP and TS+PR) on the second set of instances
    Size Algorithm ACross ATime (s) AGP (%) #Best
    GRASP 510.82 0.40 4.09
    $21\le~n_1+n_2~\le~57$ TS+PR 497.77 0.09 2.03
    DP-LS 487.79 0.02 $-$2.01
    GRASP 22742.99 18.83 4.69
    $~111~\le~n_1+n_2~\le~122~$ TS+PR 22394.12 7.80 0.06
    DP-LS 22327.91 0.11 $-$0.30
    GRASP 87844.49 319.53 4.97
    $~231~\le~n_1+n_2~\le~471~$ TS+PR 85816.74 232.27 0.01
    DP-LS 84850.02 2.48 $-$1.13
    #Total TS+PR 36928.31 83.67 241 (1000)
    DP-LS 36566.61 0.91 990 (1000)
  • Table 5   Results of DP-LS in comparison with the reference algorithm ILS without dynamic programming mechanism on the 22 typical instances
    $n_1$ $n_2$ Density $\gamma$ Best known DP-LS ILS
    Cross Time (s) GAP (%) Cross Time (s) GAP (%)
    25 25 0.065 1.2 305 305 0.01 0 305 0.05 0
    25 25 0.065 1.6 979 980 1.17 0.1 1006 1.54 2.76
    25 25 0.175 1.2 3922 3922 0.01 0 3922 0.54 0
    25 25 0.175 1.6 11982 11794 0.18 $-$1.57 12417 6.95 3.63
    25 25 0.3 1.2 15036 15036 0.01 0 15036 0.86 0
    25 25 0.3 1.6 39657 39465 0.11 $-$0.48 39597 18.96 $-$0.15
    25 50 0.065 1.2 2173 2173 0.04 0 2173 0.47 0
    25 50 0.175 1.2 19794 19794 0.01 0 19794 2.20 0
    25 50 0.3 1.2 62986 61813 0.02 $-$1.86 62794 7.65 $-$0.3
    25 50 0.3 1.6 175764 172837 0.04 $-$1.67 172841 56.93 $-$1.66
    50 25 0.065 1.2 2169 2169 0.03 0 2169 0.48 0
    50 25 0.065 1.6 5828 5552 0.25 $-$4.74 5699 7.39 $-$2.21
    50 25 0.175 1.2 19831 19831 0.03 0 19831 4.62 0
    50 25 0.175 1.6 54004 53396 0.26 $-$1.13 53387 48.09 $-$1.14
    50 25 0.3 1.2 65593 65557 0.04 $-$0.05 65557 8.40 $-$0.05
    50 25 0.3 1.6 179282 176557 0.23 $-$1.52 184608 33.48 2.97
    50 50 0.065 1.2 7637 7637 0.01 0 7637 1.523 0
    50 50 0.065 1.6 24933 24103 6.66 $-$3.33 24808 19.33 $-$0.5
    50 50 0.175 1.2 77253 77205 0.02 $-$0.06 77205 12.59 $-$0.06
    50 50 0.175 1.6 233326 230789 2.27 $-$1.09 232465 102.41 $-$0.37
    50 50 0.3 1.2 248454 248172 0.06 $-$0.11 248172 49.09 $-$0.11
    50 50 0.3 1.6 712459 709286 1.44 $-$0.45 712157 61.58 $-$0.04
    #Avg 89243.95 88562.41 0.59 $-$0.82 89253.64 20.23 0.13
    #Best 21 10
    $p$-value 2.73e$-$06
  • Table 6   Performance results of DP-LS in comparison with the reference algorithm ILS without dynamic programming mechanism on both two instance sets
    Instance set $n_1~+~n_2$ DP-LS ILS
    ACross ATime(s) #Best ACross ATime(s) #Best
    1 50 11803.4 0.38 30(30) 11963.3 5.74 15(30)
    1 75 53075.73 0.63 60(60) 53531.88 16.32 34(60)
    1 100 214900.63 2.19 30(30) 215631.1 52.53 13(30)
    2 21 49.28 0.01 150(150) 51.01 0.02 104(150)
    2 51 372.36 0.04 119(150) 380.25 0.02 31(150)
    2 57 2149.6 0.02 50(50) 2155.52 0.09 41(50)
    2 111 2002.88 0.09 150(150) 2004.96 0.28 56(150)
    2 122 42652.94 0.12 119(150) 42709.43 4.76 110(150)
    2 231 9254.73 2.07 145(150) 9269.93 6.89 102(150)
    2 242 175692.80 0.43 115(150) 175982.24 8.03 90(150)
    2 471 39107.56 9.82 43(50) 39241.92 19.47 14(50)
    #Total 41564.52 0.91 1011(1120) 41669.01 8.32 610(1120)
  • Table 7   Performance results of DP-LS in comparison with two variations (i.e., DP-LS$_{\rm~insert}$ and DP-LS$_{\rm~swap}$) only including insert moves or swap moves on all the 1120 instances
    Instance set $n_1~+~n_2$ DP-LS DP-LS$_{\rm~insert}$ DP-LS$_{\rm~swap}$
    ACross ATime (s) #Best ACross ATime (s) #Best ACross ATime (s) #Best
    1 50 11803.4 0.38 30(30) 11803.5 0.42 28(30) 12092.17 6.91 0(30)
    1 75 53087.95 0.63 58(60) 53081.35 0.57 52(60) 53778.35 11.64 0(30)
    1 100 214900.63 2.19 29(30) 214902.17 1.15 20(30) 216644.9 16.34 1(30)
    2 21 49.28 0.01 150(150) 49.3 0.01 148(150) 55.62 0.28 32(150)
    2 51 372.36 0.04 148(150) 373.27 0.01 150(150) 411.13 4.43 1(150)
    2 57 2149.6 0.02 49(50) 2149.5 0.01 50(50) 2287.42 5.99 0(50)
    2 111 2002.88 0.09 150(150) 2002.88 0.15 150(150) 2001.86 21.94 0(150)
    2 122 42652.94 0.12 145(150) 42654.05 0.09 143(150) 43852.7 0.92 4(150)
    2 231 9254.73 2.07 149(150) 9255.1 2.49 126(150) 10148.98 30.54 0(150)
    2 242 175692.8 0.43 147(150) 175696.98 0.40 144(150) 179762.27 10.67 1(150)
    2 471 39107.56 9.82 43(50) 39113.3 5.55 30(50) 43087 31.54 0(50)
    #Total 41564.52 0.91 1098(1120) 41566.01 0.74 1041(1120) 42698.59 13.47 39(1120)
  • Table 8   Performance comparison of different parameter settings
    Parameters Average performance
    $\alpha$ $\Theta$ ACross ATime (s) #Best AGP (%)
    0.2 5000 83227.74 0.21 108 4.64
    0.2 10000 83221.72 0.29 111 3.59
    0.2 20000 83221.00 0.50 114 3.25
    0.5 5000 83210.69 0.43 112 0.34
    0.5 10000 83210.61 0.61 113 0.30
    0.5 20000 83210.52 1.08 115 0.19
    0.8 5000 83211.19 0.60 103 0.66
    0.8 10000 83212.23 0.89 108 0.51
    0.8 20000 83210.59 1.65 114 0.10
qqqq

Contact and support