This work was supported by National Natural Science Foundation of China (Grant No. 61772503) and National Basic Research Program of China (Grant No. 2014CB340302).
[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.
P | D | None | Weight | Weight+Edge | Weight+Edge+Conflict | ||||
#QS | Time (s) | #QS | Time (s) | #QS | Time (s) | #QS | Time (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
Priority queue $q$ = $\emptyset$, opt = 0; |
Create a new state $n$ such that $n.sv$ = $\emptyset$, $n.{\rm~pri}~=~0$; |
$q$.push($n$); |
$n~=~q.{\rm~front}()$, $q.{\rm~pop}()$; |
|
ub = estimate_upper_bound ($n$, $G$); |
|
|
Create a new state $n'$ such that $n'.$sv = $n.$sv $\cup$ $v$, $n'.$pri = cal_priority$(v)$; |
$q.{\rm~push}(n)$; |
|
|
|
$G^*$ = translate_graph$(G,~n)$; |
$(m,$ val) = KM$(G^*)$; |
|
$M~=~m$, opt = val; |
|
|
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 |
P | D | CLASP | CPLEX | LS | Ours | ||||
#QS | Time (s) | #QS | Time (s) | #QS | Time (s) | #QS | Time (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