logo

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

More info
  • ReceivedJul 28, 2017
  • AcceptedNov 29, 2017
  • PublishedMay 7, 2019

Abstract

Given a set of radio broadcast programs, the radio broadcast scheduling problem is to allocate a set of devices to transmit the programs to achieve the optimal sound quality. In this article, we propose a complete algorithm to solve the problem, which is based on a branch-and-bound (BnB) algorithm. We formulate the problem with a new model, called constrained maximum weighted bipartite matching (CMBM), i.e., the maximum matching problem on a weighted bipartite graph with constraints. For the reduced matching problem, we propose a novel BnB algorithm by introducing three new strategies, including the highest quality first, the least conflict first and the more edge first. We also establish an upper bound estimating function for pruning the search space of the algorithm. The experimental results show that our new algorithm can quickly find the optimal solution for the radio broadcast scheduling problem at small scales, and has higher scalability for the problems at large scales than the existing complete algorithm.


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

  • Figure 1

    An example of radio broadcast scheduling problem.

  • Figure 4

    CMBM model for 3SAT problem.

  • Figure 7

    Tree structure of translated graphs.

  • 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

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1