general.hpp File Reference

Plans for the module on frequency assignment. More...

Go to the source code of this file.


namespace  OKlib::FrequencyAssignment

Active clause-sets for frequency assignment.

namespace  OKlib

All components of the OKlibrary.

Detailed Description

Plans for the module on frequency assignment.

Update namespaces.
First the most important notions of frequency assignments have to be captured and formulated as generalised satisfiability problems. A good entry seems to be provided by
  author =       {Karen I. Aardal and Stan %P.M. van Hoesel and Arie %M.C.A. Koster and Carlo Mannino and Antonio Sassano},
  title =        {Models and Solution Techniques for Frequency Assignment Problems},
  institution =  {Konrad-Zuse-Zentrum f\"ur Informationstechnik Berlin (ZIB)},
  year =         2001,
  number =       {ZIB-Report 01-40},
  month =        {December},
  annote =       {pdf-Datei vorhanden.}

The most important models seem MO-FAP, MS-FAP, MB-FAP, MI-FAP. Likely we can make use of the greater generality provided by our framework, and don't need to stick to the special formulations.

The above technical report mentions several benchmark collections; we need parsers. Perhaps the problem structures presented here are more important to us than those basic theoretical forms of FAP's (since we generalise them anyway).
MO-FAP: (G, D, c, T, K)
  • for vertex v in V(G) with requested number c(v) of frequencies and set D(v) <= NN_0 of possible frequencies we have variables v_1, ..., v_{c(v)}, each with domain D(v), and the constraint INJ({v_1, ..., v_{c(v)}}) (see module InjectivityConstraints);
  • for every edge {u,v} in E(G) we have an active constraint forbidding the differences in T({u,v}) (it seems questionable to me whether the compression enabled by T is worth to pursue, or whether we better consider the more general constraint, which allows to forbid specific pairs of frequencies (then perhaps we should gather all these constraints in a ("real") clause-set); if T just demands, that the distance is at least a certain threshold t, then T might be worth its own active clause-set (and other systematic situations are conceivable), if T however is just "random", then perhaps it's not worth a special active clause-set);
  • for all variables together (gathered in set VA) we have the upper bound constraint UPPER_V(VA, K) (see module LinearInequalities).
MS-FAP: We MO-FAP, but the third condition (the constraint on K) is replaced by:
  • maximal value for v in VA - minimal value for v in VA <= K.
Are there competitions on the subject? (We look only at the decision side; likely most activities in this field concentrate on optimisation?!)

Definition in file general.hpp.