Optimizing Shortwave Radio Broadcast Resource Allocation via Pseudo-Boolean Constraint Solving and Local Search

Shortwave radio broadcasting is the principal way for broadcasting of voice in many countries. An important problem in shortwave radio broadcasting is how to allocate transmission devices to radio programs, so that all radio programs are broadcasted properly and the overall broadcasting effect is optimized. The broadcasting effect of a program is determined by various factors, such as time, location, and device parameters. There are also restrictions on the usage of transmission devices. In this paper, we describe the allocation of shortwave radio broadcast resources as a constrained optimization problem and prove that it is NP-hard. A Pseudo-Boolean constraint formulation for the problem is presented. We also propose an efficient local search algorithm to solve the problem. Both methods are evaluated using real data. Experimental results suggest that we can find an allocation plan with good broadcasting effect quite efficiently.