The CLP Procedure

This example uses element and reified constraints to solve a radio link frequency assignment problem (Cabon et al. 1999), in which frequencies must be assigned to communication links from limited spectral resources in such a way that no interference occurs. The simplest case is considered, with only two types of constraints:

Violation of a soft constraint incurs a cost that depends on the cost category that is associated with the constraint.

The data for the CELAR6-SUB0 instance come from MiniZinc Challenge 2016 (Stuckey, Becket, and Fischer 2010), a partial description of which is shown in Table 9.

The instance data are used to generate the SAS macro variables that the CLP procedure uses. In the following SAS statements, f1-f&num_variables are the frequency variables. Other variables include TotalCost and several sets of binary variables for the element and reified constraints. A set of element constraints is created to ensure that each frequency variable takes a value from its noncontiguous domain. A set of linear and element constraints specifies the absolute difference between two frequencies to be the exact given distance. The soft constraints are implemented using binary variables and reified constraints. The binary variable ri indicates whether the corresponding soft constraint is violated and is used in the linear expression that represents the total cost.

%macro celar(maxtime);
   proc clp out=mylib.out varselect=wdeg maxtime=&maxtime timetype=real;
      /* Declare variables */
      var (f1-f&num_variables) = [&min_freq, &max_freq];
      var (TotalCost) = [0, 159];
      var eley = [1, 1];
      /* Each variable takes a value in its domain */
      %do i=1 %to &num_variables;
         %do j=1 %to &num_categories;
            %if (&&domain&i. eq &j.) %then %do;
               element(f&i., (&&elecategory&j.), eley);
            %end;
         %end;
      %end;

      /* Hard constraints */
      %do i=1 %to &num_hardconstraints;
         %let fx = f&&hardctrx&i.;
         %let fy = f&&hardctry&i.;
         %let k = &&hardctrk&i.;
         var (hx&i. hy&i.) = [%eval(-&k), &k];
         lincon hx&i. = &fx - &fy;
         element (hx&i. = (%eval(-&k), &k), (&k, &k), hy&i.);
      %end;

      /* Soft constraints */
      %do i=1 %to &num_softconstraints;
         %let fx = f&&softctrx&i.;
         %let fy = f&&softctry&i;
         var (sa1_&i. sa2_&i. sb1_&i. sb2_&i. ss&i. st&i. r&i.)=[0, 1];
         reify sa1_&i.: (&fx >= &fy);
         reify sa2_&i.: (&fx-&fy <= &&softctrk&i.);
         reify sb1_&i.: (&fx < &fy);
         reify sb2_&i.: (&fy-&fx <= &&softctrk&i.);
         reify ss&i.: (sa1_&i. + sa2_&i. = 2);
         reify st&i.: (sb1_&i. + sb2_&i. = 2);
         reify r&i.: (ss&i. + st&i. = 1);
      %end;

      /* Cost constraint */
      lincon TotalCost = &costw1 * r1
         %do i=2 %to &num_softconstraints;
             + &&costw&i. * r&i.
         %end;;
   run;
   %put &_orclp_;

%mend celar;

The following statement invokes the %celar macro with a maximum time of 1000 seconds to find a feasible solution that corresponds to the known minimum cost of 159:

%celar(maxtime=1000);

The solution summary that corresponds to running in distributed mode with 100 workers is shown in Output 4.8.1.