A novel neural-network approach called gradual neural network (GNN) is presented for a class of combinatorial optimization problems of requiring the constraint satisfaction and the goal function optimization simultaneously. The frequency assignment problem in the satellite communication system is efficiently solved by GNN as the typical problem of this class in this paper. The goal of this NP-complete problem is to minimize the cochannel interference between satellite communication systems by rearranging the frequency assignment so that they can accommodate the increasing demands. The GNN consists of N × M binary neurons for the N-carrier-M-segment system with the gradual expansion scheme of activated neurons. The binary neural network achieves the constrain satisfaction with the help of heuristic methods, whereas the gradual expansion scheme seeks the cost optimization. The capability of GNN is demonstrated through solving 15 instances in practical size systems, where GNN can find far better solutions than the existing algorithm. © 1997 IEEE.