Introduction to Optimization

The following DATA step creates a SAS data set for this product mix problem. Notice that the values of CHOCO and TOFFEE in the data set are the coefficients of those variables in the objective function and constraints. The variable _id_ contains a character string that names the rows in the data set. The variable _type_ is a character variable that contains keywords that describe the type of each row in the problem data set. The variable _rhs_ contains the right-hand-side values.

data factory;
   input _id_ $ CHOCO TOFFEE _type_ $ _rhs_;
   datalines;
object      0.25    0.75   MAX     .
process1   15.00   40.00   LE  27000
process2    0.00   56.25   LE  27000
process3   18.75    0.00   LE  27000
process4   12.00   50.00   LE  27000
;

To solve this problem by using PROC LP, specify the following:

proc lp data=factory;
run;

Typically, mathematical programming models are sparse; that is, few of the coefficients in the constraint matrix are nonzero. For this reason the LP procedure also accepts data in a sparse format SAS data set. In this format only the nonzero coefficients for the constraints and objective function must be specified.

An example of a sparse format data set is shown here. The following data set contains the data from the product mix problem of the preceding section.

data sp_factory;
   format _type_ $8. _row_ $10. _col_ $10.;
   input _type_ $_row_ $ _col_ $ _coef_;
   datalines;
max      object     .            .
.        object     chocolate    .25
.        object     toffee       .75
le       process1   .            .
.        process1   chocolate    15
.        process1   toffee       40
.        process1   _RHS_        27000
le       process2   .            .
.        process2   toffee       56.25
.        process2   _RHS_        27000
le       process3   .            .
.        process3   chocolate    18.75
.        process3   _RHS_        27000
le       process4   .            .
.        process4   chocolate    12
.        process4   toffee       50
.        process4   _RHS_        27000
;

To solve this problem by using PROC LP, specify the following:

proc lp data=sp_factory sparsedata;
run;

The “Solution Summary” table (shown in Figure 2.1) contains information about the solution that was found, including whether the optimizer terminated successfully after finding the optimum.

PROC LP uses an iterative process to solve problems. First, the procedure finds a feasible solution that satisfies the constraints. Second, it finds an optimal solution from the set of feasible solutions. The “Solution Summary” table lists information about the optimization process such as the number of iterations, the infeasibilities of the solution, and the time required to solve the problem.

It is often desirable to keep the data separate from the structure of the model. This is useful for large models with numerous identifiable components. The data are best organized in rectangular tables that can be easily examined and modified. Then, before the problem is solved, the model is built using the stored data. This process of model building is known as matrix generation. In conjunction with the sparse format used by the legacy procedures, the SAS DATA step provides a good matrix generation language.

For example, consider the candy manufacturing example introduced previously. Suppose that, for the user interface, it is more convenient to organize the data so that each record describes the information related to each product (namely, the contribution to the objective function and the unit amount needed for each process). A DATA step for saving the data might look like this:

data manfg;
   format product $12.;
   input product $ object process1 - process4 ;
   datalines;
chocolate        .25    15  0.00 18.75    12
toffee           .75    40 56.25  0.00    50
licorice        1.00    29 30.00 20.00    20
jelly_beans      .85    10  0.00 30.00    10
_RHS_            .   27000 27000 27000 27000
;

Notice that there is a special record at the end that has product _RHS_. This record gives the amounts of time available for each of the processes. This information could have been stored in another data set. The next example illustrates a model in which the data are stored in separate data sets.

Building the model involves adding the data to the structure. There are as many ways to add data as there are programmers and problems. The following DATA step shows one way to use the candy data to build a sparse format model to solve the product mix problem:

data model;
   array process {5} object process1-process4;
   format _type_ $8. _row_ $12. _col_ $12. ;
   keep _type_ _row_ _col_ _coef_;

   set manfg;         /* read the manufacturing data */

   /* build the object function */

   if _n_=1 then do;
      _type_='max'; _row_='object'; _col_=' '; _coef_=.;
      output;
   end;

   /* build the constraints */

   do i=1 to 5;
      if i>1 then do;
         _type_='le'; _row_='process'||put(_i_-1,1.);
      end;
      else            _row_='object';
      _col_=product; _coef_=process[i];
      output;
   end;
run;

The sparse format data set is shown in Figure 2.2.

The model data set looks a little different from the sparse representation of the candy model shown earlier. It not only includes additional products (licorice and jelly beans), but it also defines the model in a different order. Since the sparse format is robust, the model can be generated in ways that are convenient for the DATA step program.

If the problem had more products, you could increase the size of the manfg data set to include the new product data. Also, if the problem had more than four processes, you could add the new process variables to the manfg data set and increase the size of the process array in the model data set. With these two simple changes and additional data, a product mix problem that has hundreds of processes and products can be modeled and solved.