Optimizing a Constraint: Reconstructing an Integer Programming Constraint More Simply

The following PROC TRANSPOSE statements and DATA step create an input data set for the CLP procedure in SAS/OR software:

proc transpose data=a_data out=trans(drop=_name_) prefix=x;
run;

data condata_feas(drop=j);
   length _type_ $8;
   array x[&n];
   set trans;
   _type_ = 'le';
   _rhs_ = &b;
   output;
   do j = 1 to &n;
      x[j] = 1;
   end;
   _type_ = 'binary';
   _rhs_ = .;
   output;
run;

The following PROC CLP statements find all feasible solutions and save them in the out_feas data set:

proc clp data=condata_feas out=out_feas allsolns usecondatavars=1;
run;

The following DATA step creates another input data set for PROC CLP, for the purpose of finding all binary solutions that violate the original constraint:

data condata_infeas;
   set condata_feas;
   if _N_ = 1 then do;
      _type_ = 'ge';
      _rhs_ = _rhs_ + 1;
   end;
run;

The following PROC CLP statements find all such solutions and save them in the out_infeas data set:

proc clp data=condata_infeas out=out_infeas allsolns usecondatavars=1;
run;

The first several PROC OPTMODEL statements declare sets and parameters and read the original constraint data:

proc optmodel;
   set VARS;
   set VARS0 = VARS union {0};
   num a {VARS0};
   read data a_data into VARS=[_N_] a;
   a[0] = &b;

The following statements declare the set and the parameter and populate them by reading the out_feas data set:

   set FEAS_POINTS;
   num x_feas {FEAS_POINTS, VARS};
   read data out_feas into FEAS_POINTS=[_N_]
      {j in VARS} <x_feas[_N_,j]=col('x'||j)>;

The following statements declare the set and the parameter and populate them by reading the out_infeas data set:

   set INFEAS_POINTS;
   num x_infeas {INFEAS_POINTS, VARS};
   read data out_infeas into INFEAS_POINTS=[_N_]
      {j in VARS} <x_infeas[_N_,j]=col('x'||j)>;

The following statements declare the variables and constraints:

   var Scale {VARS0} >= 0;
   impvar Alpha {j in VARS0} = a[j] * Scale[j];

   con Feas_con {point in FEAS_POINTS}:
      sum {j in VARS} Alpha[j] * x_feas[point,j] <= Alpha[0];
   con Infeas_con {point in INFEAS_POINTS}:
      sum {j in VARS} Alpha[j] * x_infeas[point,j] >= Alpha[0] + 1;

The following statements solve the problem by using the first objective and then print the solution:

   min Objective1 = abs(a[0]) * Scale[0];
   solve;
   print a Scale Alpha;

Figure 18.1 shows the output from the linear programming solver for the first objective.

The following statements solve the problem by using the second objective and then print the solution:

   min Objective2 = sum {j in VARS} abs(a[j]) * Scale[j];
   solve;
   print a Scale Alpha;
quit;

Figure 18.2 shows the output from the linear programming solver for the second objective.

For this test instance, it turns out that the optimal solutions for the two different objectives agree.

In SAS/OR 13.2, you can also access the CLP solver from within PROC OPTMODEL by using the SOLVE WITH CLP statement. The first several PROC OPTMODEL statements are the same as before:

proc optmodel;
   set VARS;
   set VARS0 = VARS union {0};
   num a {VARS0};
   read data a_data into VARS=[_N_] a;
   a[0] = &b;

The following statements declare variables and a constraint for the CLP problem:

   var X {VARS} binary;
   con CLP_con:
      sum {j in VARS} a[j] * X[j] <= a[0];

The following statements call the CLP solver and use the FINDALLSOLNS option to find all solutions, and then they use the predeclared numeric parameter _NSOL_ and the .sol variable suffix to retrieve the resulting solutions:

   solve with CLP / findallsolns;
   set FEAS_POINTS;
   FEAS_POINTS = 1.._NSOL_;
   num x_feas {FEAS_POINTS, VARS};
   for {s in FEAS_POINTS, j in VARS} x_feas[s,j]=X[j].sol[s];

The following statements modify the right-hand side of the constraint by changing the .lb constraint suffix and then use the CONSTANT function to effectively remove the previously declared upper bound by replacing it with the largest machine-representable number:

   CLP_con.lb = CLP_con.ub + 1;
   CLP_con.ub = constant('BIG');

The following statements call the CLP solver again and retrieve the resulting solutions:

   solve with CLP / findallsolns;
   set INFEAS_POINTS;
   INFEAS_POINTS = 1.._NSOL_;
   num x_infeas {INFEAS_POINTS, VARS};
   for {s in INFEAS_POINTS, j in VARS} x_infeas[s,j]=X[j].sol[s];

The remaining statements are the same as before, except that now the PROBLEM and USE PROBLEM statements are used to switch the focus from the CLP problem to the LP problem:

   var Scale {VARS0} >= 0;
   impvar Alpha {j in VARS0} = a[j] * Scale[j];

   con Feas_con {point in FEAS_POINTS}:
      sum {j in VARS} Alpha[j] * x_feas[point,j] <= Alpha[0];
   con Infeas_con {point in INFEAS_POINTS}:
      sum {j in VARS} Alpha[j] * x_infeas[point,j] >= Alpha[0] + 1;

   min Objective1 = abs(a[0]) * Scale[0];

   problem LP_problem include Scale Feas_con Infeas_con Objective1;
   use problem LP_problem;

   solve;
   print a Scale Alpha;

   min Objective2 = sum {j in VARS} abs(a[j]) * Scale[j];
   solve;
   print a Scale Alpha;
quit;