Constrained maximum weighted bipartite matching:a novel approach to radio broadcast scheduling
|
摘要
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.
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.
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.
引文
1 Li Y,Nie F,Huang H,et al.Large-scale multi-view spectral clustering via bipartite graph.In:Proceedings of the29th AAAI Conference on Artificial Intelligence,Austin,2015.2750-2756
2 Gu T L,Chang L,Xu Z B.A novel symbolic algorithm for maximum weighted matching in bipartite graphs.Int JCommun Netw Syst Sci,2011,4:111-121
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
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
5 Zhan C,Xiao F.Coding based wireless broadcast scheduling in real time applications.J Network Comput Appl,2016,64:194-203
6 Kuhn H W.The Hungarian method for the assignment problem.Naval Res Log,1955,2:83-97
7 Munkres J.Algorithms for the assignment and transportation problems.J Soc Industrial Appl Math,1957,5:32-38
8 Mitchell D G.A sat solver primer.Bull EATCS,2005,85:112-132
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
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
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
1)About ITU. 2016. http://www.itu.int/.
2 Gu T L,Chang L,Xu Z B.A novel symbolic algorithm for maximum weighted matching in bipartite graphs.Int JCommun Netw Syst Sci,2011,4:111-121
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
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
5 Zhan C,Xiao F.Coding based wireless broadcast scheduling in real time applications.J Network Comput Appl,2016,64:194-203
6 Kuhn H W.The Hungarian method for the assignment problem.Naval Res Log,1955,2:83-97
7 Munkres J.Algorithms for the assignment and transportation problems.J Soc Industrial Appl Math,1957,5:32-38
8 Mitchell D G.A sat solver primer.Bull EATCS,2005,85:112-132
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
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
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
1)About ITU. 2016. http://www.itu.int/.