logo

Journals Books
Advanced Search
Sign in Register

中文

SCIENCE CHINA Information Sciences
Download PDF
SCIENCE CHINA Information Sciences, Volume 62 , Issue 7 : 072102(2019) https://doi.org/10.1007/s11432-017-9324-0

Constrained maximum weighted bipartite matching: a novel approach to radio broadcast scheduling

Shaojiang WANG 1,2, Tianyong WU 1,2, Yuan YAO 2,3, Dongbo BU 4, Shaowei CAI 1,2,*
More info
  • ReceivedJul 28, 2017
  • AcceptedNov 29, 2017
  • PublishedMay 7, 2019
Previous Table of Contents Next
Share
Rating

Abstract


Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant No. 61772503) and National Basic Research Program of China (Grant No. 2014CB340302).


References

[1] Li Y, Nie F, Huang H, et al. Large-scale multi-view spectral clustering via bipartite graph. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence, Austin, 2015. 2750--2756. Google Scholar

[2] Gu T L, Chang L, Xu Z B. A novel symbolic algorithm for maximum weighted matching in bipartite graphs. Int J Commun Netw Syst Sci, 2011, 4: 111--121. Google Scholar

[3] Beale S. Using branch-and-bound with constraint satisfaction in optimization problems. In: Proceedings of the 14th National Conference on Artificial Intelligence and 9th Innovative Applications of Artificial Intelligence Conference, Providence, 1997. 209--214. Google Scholar

[4] Lelis L H S, Otten L, Dechter R. Predicting the size of depth-first branch and bound search trees. In: Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, 2013. Google Scholar

[5] Zhan C, Xiao F. Coding based wireless broadcast scheduling in real time applications. J Network Comput Appl, 2016, 64: 194-203 CrossRef Google Scholar

[6] Kuhn H W. The Hungarian method for the assignment problem. Naval Res Logistics, 1955, 2: 83-97 CrossRef Google Scholar

[7] Munkres J. Algorithms for the Assignment and Transportation Problems. J Soc Industrial Appl Math, 1957, 5: 32-38 CrossRef Google Scholar

[8] Mitchell D G. A sat solver primer. Bull EATCS, 2005, 85: 112--132. Google Scholar

[9] Ma F, Gao X, Yin M, et al. Optimizing shortwave radio broadcast resource allocation via pseudo-boolean constraint solving and local search. In: Proceedings of the 22nd International Conference on Principles and Practice of Constraint Programming, Toulouse, 2016. 650--665. Google Scholar

[10] Pan L, Jin J, Gao X, et al. Integrating ILP and SMT for shortwave radio broadcast resource allocation and frequency assignment. In: Proceedings of the 23rd International Conference on Principles and Practice of Constraint Programming, Melbourne, 2017. 405--413. Google Scholar

[11] Li C M, Quan Z. An efficient branch-and-bound algorithm based on maxsat for the maximum clique problem. In: Proceedings of the 24th AAAI Conference on Artificial Intelligence, Atlanta, 2010. Google Scholar

  • Click to view Download high-quality image

    Figure 1

    An example of radio broadcast scheduling problem.

  • Click to view Download high-quality image

    Figure 4

    CMBM model for 3SAT problem.

  • Click to view Download high-quality image

    Figure 7

    Tree structure of translated graphs.

  • Click to view Download high-quality image

    Figure 8

    Experimental results of random data.

  • Table 1   Results of different versions of our method on application benchmark$^{\rm~a)}$
    P D NoneWeightWeight+EdgeWeight+Edge+Conflict
    #QSTime (s)#QSTime (s) #QSTime (s) #QSTime (s)
    2 50 94* $<$0.04 94* $<$0.05 94* $<$0.01 94* $<$0.001
    5 50 103* 3.92 103* 5.14 103* 5.11 103* 0.141
    2 100 94* 0.012 94* 0.011 94* 0.01 94* $<$0.001
    5 100 103* 9.43 103* 5 103* 11.45 103* 0.23
    2 200 121* 0.016 121* 0.013 121* 0.016 121* $<$0.001
    5 200 206 13.5 238* 5 238* 2.03 238* 2.04
    10 200 393 180 645 40.6 645 40.2 645 42.9
    2 400 187* 0.017 187* 0.16 187* 0.016 187* $<$0.001
    5 400 406 142 438* 20.8 438* 21 438 20.8
    10 400 416 85.2 845 46.1 845 46.2 845 46.7
    20 400 588 84.9 761 175 761 169 761 160
    2 800 212* 0.448 212* 0.434 212* 0.427 212* $<$0.001
    5 800 408 140 447 0.22 447 0.222 447 0.222
    50 4000 2837 129 4471 0.043 4471 0.045 4471 0.049
    60 4000 3073 103 5143 0.239 5143 0.24 5143 0.238
    70 4000 3780 25.2 6057 0.306 6057 0.35 6057 0.326
    87 4000 4776 160 6824 0.144 6824 0.138 6824 0.141
    50 5000 2802 54.7 4613 0.223 4612 0.22 4612 0.22
    60 5000 3073 151 5313 0.284 5313 0.286 5313 0.278
    70 5000 3780 37.3 6277 0.143 6280 0.294 6280 0.3
    87 5000 4771 96.2 7099 0.19 7099 0.18 7099 0.18
    50 6000 2826 72.5 4989 2.6 4989 2.63 4989 2.59
    60 6000 3054 158 5784 2.18 5784 2.18 5784 0.189
    70 6000 3804 51.4 6861 49.4 6861 49.3 6861 49
    87 6000 4795 136 7745 165 7742 0.748 7742 0.754
    50 7061 2826 76 5006 5.33 5006 5.43 5006 5.24
    60 7061 3054 167 5821 53.1 5821 53.1 5820 0.554
    70 7061 3804 54.2 6948 0.189 6948 0.181 6948 0.182
    87 7061 4795 144 7893 1.81 7902 0.633 7902 0.619

    a

  •   

    Algorithm 1 BnB algorithm for the constrained maximum weighted graph matching problem (CMGM)

    Input: Constrained weighted bipartite graph $G$; Output: A matching $M$ and its weight sum opt such that $M$ satisfies the constraints and opt is maximum.

    Priority queue $q$ = $\emptyset$, opt = 0;

    Create a new state $n$ such that $n.sv$ = $\emptyset$, $n.{\rm~pri}~=~0$;

    $q$.push($n$);

    while $q$ is not empty do

    $n~=~q.{\rm~front}()$, $q.{\rm~pop}()$;

    if $n.$sv in not a maximal non-conflict device set then

    ub = estimate_upper_bound ($n$, $G$);

    if ub $>$ opt then

    for each unvisited and non-conflicted vertex $v~\in~V_2$

    Create a new state $n&apos;$ such that $n&apos;.$sv = $n.$sv $\cup$ $v$, $n&apos;.$pri = cal_priority$(v)$;

    $q.{\rm~push}(n)$;

    end for

    end if

    else

    $G^*$ = translate_graph$(G,~n)$;

    $(m,$ val) = KM$(G^*)$;

    if val $>$ opt then

    $M~=~m$, opt = val;

    end if

    end if

    end while

  • Table 2   Summary on comparisons between different versions
    Strategy Improving Equal Worse
    Weight vs. None 29 0 0
    Weight+Edge vs. Weight 18 3 8
    Weight+Edge+Conflict vs. Weight 25 2 2
  • Table 3   Experimental results on application benchmark$^{\rm~a)}$
    P D CLASPCPLEXLSOurs
    #QSTime (s)#QSTime (s) #QSTime (s) #QSTime (s)
    2 50 94* $<$0.01 94* $<$0.01 94(94) $<$0.01 94* $<$0.001
    5 50 103* 0.171 103* 0.19 103(103) $<$0.01 103* 0.141
    2 100 94* 0.016 94* $<$0.01 94(94) $<$0.01 94* $<$0.001
    5 100 103* 0.171 103* 0.14 103(103) $<$0.01 103* 0.23
    2 200 121* 0.078 121* 0.14 121(121) $<$0.01 121* $<$0.001
    5 200 238 7.269 238* 0.16 238(238) $<$0.01 238* 2.04
    10 200 762 273.995 762* 0.27 762(762) 0.014 654 42.9
    2 400 187* 0.577 187* 0.13 187(187) $<$0.01 187* $<$0.001
    5 400 438 25.569 438* 0.09 438(438) 0.015 438 20.8
    10 400 965 473.975 965* 0.19 965(965) 0.047 845 46.7
    20 400 1228 3200.502 1232* 0.28 1232(1231.9) 3.411 761 160
    2 800 212* 6.209 212* 0.16 212(212) 0.026 212* $<$0.001
    5 800 501 1589.128 501* 0.14 501(501) 0.127 447 0.222
    50 4000 1060 3004.924 – – 4577(4541.7) 8.500 4471 0.049
    60 4000 – – – – 5387(5329.4) 9.884 5143 0.238
    70 4000 – – – – 6284(6249.9) 9.806 6057 0.326
    87 4000 – – – – 7029(6986) 9.824 6824 0.141
    50 5000 927 2892.373 – – 4708(4681.5) 9.845 4612 0.22
    60 5000 – – – – 5496(5416.4) 9.912 5143 0.238
    70 5000 – – – – 6373(6318) 9.795 6280 0.3
    87 5000 – – – – 7186(7142.9) 9.712 7099 0.18
    50 6000 – – – – 5030(4990.4) 9.803 4989 2.59
    60 6000 – – – – 5856(5788.9) 9.826 5784 0.189
    70 6000 – – – – 6878(6797.5) 9.842 6861 49
    87 6000 – – – – 7854(7667) 9.687 7742 0.754
    50 7061 – – – – 5068(5045.9) 9.828 5006 5.24
    60 7061 – – – – 5883(5805.7) 9.909 5820 0.554
    70 7061 – – – – 6860(6800.0) 9.779 6948 0.182
    87 7061 – – – – 7739(7629.6) 9.620 7902 0.619

    a