The LP Procedure

Example 6.16 Migration to OPTMODEL: Assignment

The following example shows how to solve Example 6.12 using PROC OPTMODEL. The OBJECT, DEMAND, and RESOURCE data sets are the same as in that example. A new data set, GRADE, is added to aid in separating the data from the model.

title 'An Assignment Problem';

data grade(drop=i);
   do i = 1 to 6;
      grade = 'grade'||put(i,1.);

The following PROC OPTMODEL statements read the data sets, build the linear programming model, solve the model, and output the optimal solution to a SAS data set called SOLUTION:

proc optmodel;
   /* declare index sets */
   set <str> GRADES;
   set MACHINES;

   /* declare parameters */
   num return {CUSTOMERS, GRADES, MACHINES} init 0;
   num demand {CUSTOMERS, GRADES};
   num cost {GRADES, MACHINES} init 0;
   num avail {MACHINES};

   /* read the set of grades */
   read data grade into GRADES=[grade];

   /* read the set of customers and their demands */
   read data demand
      into CUSTOMERS=[customer]
      {j in GRADES} <demand[customer,j]=col(j)>;

   /* read the set of machines, costs, and availability */
   read data resource nomiss
      into MACHINES=[machine] 
      {j in GRADES} <cost[j,machine]=col(j)>

   /* read objective data */
   read data object nomiss
      into [machine customer]
      {j in GRADES} <return[customer,j,machine]=col(j)>;

   /* declare the model */
   var AmountProduced {CUSTOMERS, GRADES, MACHINES} >= 0;
   max TotalReturn = sum {i in CUSTOMERS, j in GRADES, k in MACHINES}
      return[i,j,k] * AmountProduced[i,j,k];
   con req_demand {i in CUSTOMERS, j in GRADES}:
      sum {k in MACHINES} AmountProduced[i,j,k] = demand[i,j];
   con req_avail {k in MACHINES}:
      sum {i in CUSTOMERS, j in GRADES} 
         cost[j,k] * AmountProduced[i,j,k] <= avail[k];

   /* call the solver and save the results */
   create data solution 
      from [customer grade machine] = {i in CUSTOMERS, j in GRADES, 
         k in MACHINES: AmountProduced[i,j,k].sol ne 0}

   /* print optimal solution */
   print AmountProduced;

The statements use both numeric (NUM) and character (STR) index sets, which are populated from the corresponding data set variables in the READ DATA statements. The OPTMODEL parameters can be either single-dimensional (AVAIL) or multiple-dimensional (COST, DEMAND, RETURN). The RETURN and COST parameters are given initial values of 0, and the NOMISS option in the READ DATA statement tells OPTMODEL to read only the nonmissing values from the input data sets. The model declaration is nearly identical to the mathematical formulation. The logical condition AmountProduced[i,j,k].sol ne 0 in the CREATE DATA statement makes sure that only the nonzero parts of the solution appear in the SOLUTION data set. In Example 6.12, the creation of this data set required postprocessing of the PROC LP output data set.

The main point is that the PROC OPTMODEL statements are much easier to read and maintain than the corresponding DATA step statements required for PROC LP.

The SOLUTION data set can be processed by PROC TABULATE as follows to create a compact representation of the solution:

proc tabulate data=solution; 
   class customer grade machine; 
   var   amount; 
   table (machine*customer), (grade*amount=''*sum=''); 

The output is the same as Output 6.12.2. The log is displayed in Output 6.16.1.

Output 6.16.1: OPTMODEL Log

An Assignment Problem

NOTE: There were 6 observations read from the data set WORK.GRADE.              
NOTE: There were 5 observations read from the data set WORK.DEMAND.             
NOTE: There were 4 observations read from the data set WORK.RESOURCE.           
NOTE: There were 20 observations read from the data set WORK.OBJECT.            
NOTE: The problem has 120 variables (0 free, 0 fixed).                          
NOTE: The problem has 34 linear constraints (4 LE, 30 EQ, 0 GE, 0 range).       
NOTE: The problem has 220 linear constraint coefficients.                       
NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).      
NOTE: The OPTMODEL presolver is disabled for linear problems.                   
NOTE: The OPTLP presolver value AUTOMATIC is applied.                           
NOTE: The OPTLP presolver removed 43 variables and 7 constraints.               
NOTE: The OPTLP presolver removed 66 constraint coefficients.                   
NOTE: The presolved problem has 77 variables, 27 constraints, and 154           
      constraint coefficients.                                                  
NOTE: The DUAL SIMPLEX solver is called.                                        
      Phase Iteration  Value                                                    
        2           1       2052796                                             
        2          45        871426                                             
NOTE: Optimal.                                                                  
NOTE: Objective = 871426.038.                                                   
NOTE: The data set WORK.SOLUTION has 26 observations and 4 variables.