A potential reduction approach to the Radio Link Frequency Assignment Problem

Joost P. Warners

More recently, Karmarkar and his colleagues extended the potential reduction idea to solve difficult combinatorial optimization problems. A combinatorial problem can be modelled as a binary linear programming problem. Karmarkar designed a (nonlinear) potential function that, when minimized, forces the variables to binary values and developed an IPM to minimize it. However, this potential function has many local minima, that do not yield binary solutions. Therefore, his so-called potential reduction method is a heuristic method, and there is no guarantee that it will generate satisfactory solutions. To increase the chance of success, Karmarkar also incorporated a rounding scheme in his algorithm.

Within the framework of the international CALMA project of the ministries of defence of Britain, France and the Netherlands, Karmarkar's method has been applied to solve a variant of the frequency assignment problem; the Radio Link Frequency Assignment Problem (RLFAP). The objective of the problem is to assign frequencies to radio links such that no interference occurs and the number of used frequencies is minimal, or the amount of interference is minimized. The RLFAP is a combinatorial problem. So, the potential reduction method can be applied.

Unfortunately, the first observation is that Karmarkar's potential function is not appropriate for solving large scale optimization problems, as it involves solving linear systems with completely dense matrices, whose size increases with the problem size. Therefore, we first have designed an appropriate potential function that does not have this property. With the new potential function, computational experience with randomly generated instances of the well-known Satisfiability problem shows that larger problems can be solved, in less time.

Furthermore, for a special class of combinatorial problems, to which among others the RLFAP, the graph coloring and the maximum independent set belong, a new quadratic model is developed. This model can be obtained from a binary linear model for a problem in the appropriate class. It is very compact, as all inequality constraints are incorporated in the objective function. This can result in a reduction with tens of thousands of constraints. Furthermore, by solving the quadratic model, instead of just one, multiple solutions may be found simultaneously. Unfortunately, the model is nonconvex. There are no known methods which are guaranteed to find an optimal solution efficiently. We can however adapt Karmarkar's potential reduction method to solve the model, using an appropriate potential function.

For the RLFAP both the linear and quadratic model are explicitly formulated, also making use of a special structure of the problem, to reduce the problem size as far as possible.

To reduce the size of the problem even further, several preprocessing techniques, both heuristic and exact, are developed.

We discuss all the algorithmic details to apply the potential reduction method to both the linear and quadratic model. Several rounding schemes for all variants of the RLFAP are developed and techniques to avoid and escape from local minima are specified. Furthermore, we point out that the nonzero structure and the density of the linear systems that have to be solved are completely the same, using either the improved potential function for the linear model or the potential function for the quadratic model.

The full algorithm has been applied to a set of RLFAPs, varying in size from a couple of hundred to over eighteen thousand variables. When solving the linear model, only small problems could be solved, up to 750 variables. This already required substantial computational effort. Using the new quadratic formulation and its corresponding potential function however, for all problems feasible assignments were found within minutes. For a large number of problems optimal assignments are found; for the other problems the assignments are within reasonable distance of the optimal or best known assignment.

Furthermore, some preliminary experiments show that when we let the algorithm run, vast amounts of feasible assignments can be found simultaneously. For example, for one of the test problems the number of feasible assignments found is literally billions. However, this does take substantial time (about half an hour to two hours).

When comparing results with other participants in the CALMA project, it turns out that the results are comparable to the results obtained by well established heuristic methods such as simulated annealing, tabu search and genetic algorithms. To make the method really competitive with the most successful heuristic algorithms such as various local search techniques, more research is required. But, taking into consideration the short history of the method, the outlook is promising.

05-04-2000

  Info: