% 
% CELAR radio link frequency assignment problem in MiniZinc.
%
% B. Cabon, S. de Givry, L. Lobjois, T. Schiex, and J.P. Warners
% Radio Link Frequency Assignment
% Constraints, 4(1):79-89, 1999
%
% The  "Radio  Link   Frequency Assignment Problem"   (RLFAP)  consists in
% assigning frequencies   to communication  links in such   a way  that  no
% interferences  occurs. Domains  are   set  of integers (non   necessarily
% consecutives). In the simplest case  which is  considered here, only two
% types of constraint occur: 
% 1- the absolute  difference  between   two  frequencies   should  be
%   greater than a given number k (|x-y|>k);
% 2- the absolute  difference between two  frequencies should  exactly
%   be equal to a given number k' (|x-y|=k).
% If there is no solution, (1) become soft constraints while (2) remain hard constraints
% and you have to minimize a weighted sum of the violated soft constraints.

% 
% This MiniZinc model was created by Simon de Givry, degivry@toulouse.inra.fr
%

include "globals.mzn"; 

% objective function weights
% (mobility costs are not taken into account)
array[1..4] of int: costs;

% domain categories
int: num_categories;
array[1..num_categories] of set of int: categories;
int:min_freq;
int:max_freq;

% number of frequency variables
int: num_variables;

% domain category index for each variable
array[1..num_variables] of int: domains;

% hard equality constraints
int: num_hardconstraints;
array[1..num_hardconstraints] of int: hardctrx;
array[1..num_hardconstraints] of int: hardctry;
array[1..num_hardconstraints] of int: hardctrk;

% soft inequality constraints
int: num_softconstraints;
array[1..num_softconstraints] of int: softctrx;
array[1..num_softconstraints] of int: softctry;
array[1..num_softconstraints] of int: softctrk;
array[1..num_softconstraints] of int: softctrw;

% the assignments
array[1..num_variables] of var min_freq..max_freq: f;
var int: objective;

% solve minimize objective;
solve :: int_search(f, first_fail, indomain_min, complete) minimize objective;

constraint
   objective = sum(j in 1..num_softconstraints) ( costs[softctrw[j]] * bool2int(abs(f[softctrx[j]] - f[softctry[j]]) <= softctrk[j]) )
   /\ % ensure that each variable takes a value in its domain
   forall(j in 1..num_variables) (
       f[j] in categories[domains[j]]
   )
   /\ % hard equality constraints
   forall(j in 1..num_hardconstraints) (
       abs(f[hardctrx[j]] - f[hardctry[j]]) = hardctrk[j]
   )
%
% solution checker for scen06.dzn: objective=3389
%   /\
%   forall(j in 1..100) (
%   	   f[2*j-1] = [442,366,526,254,414,16,526,254,16,526,30,666,30,414,442,736,114,680,750,16,652,764,428,86,456,254,652,254,512,414,442,380,708,254,142,778,792,366,778,268,44,750,484,100,694,268,268,428,708,750,310,394,778,652,100,338,380,540,470,338,428,352,268,268,540,366,268,324,30,512,456,30,470,30,16,254,526,498,694,694,722,792,778,324,86,30,680,750,282,554,324,428,736,30,680,750,30,470,58,428][j]
%   )
;

output
[
  "f: " ++ show(f) ++ "\n" ++
  "objective: " ++ show(objective)
];