In this article, two efficient heuristic algorithms are suggested for the channel allocation problem which minimizes the average blocking probability of the whole network subject to the co-channel, adjacent-site and co-site interference constraints, given the number of available channels. We convert this problem into a convenient form using the piecewise linearization technique and the concept of pattern, and apply Lagrangean relaxation and subgradient optimization techniques. Computational experiments show that this procedure provides high-quality solutions with information about their error ranges for networks with special compatibility matrices. We also suggest a general procedure using a GOS (grade of service) updating scheme, and provide encouraging computational results. (C) 1997 Elsevier Science Ltd.