OKlibrary  0.2.1.6
general.hpp File Reference

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

Go to the source code of this file.

Namespaces

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.

Todo:
Update namespaces.
Todo:
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
  @TechReport{ZIB2001FAP,
  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.

Todo:
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).
Todo:
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).
Todo:
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.
Todo:
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.