Introduction to Optimization

Model Building

It is often desireable 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, 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 have 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) needed by each product. A DATA step for saving these data might look like this:

   data manfg; 
      input product $16. 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 having 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 where the data are stored in separate data sets.

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

   data model;
      array process object process1-process4;
      format _type_ $8. _row_ $16. _col_ $16. ;
      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 over process;   
         if _i_>1 then do; 
            _type_='le'; _row_='process'||put(_i_-1,1.);
            end;
         else            _row_='object';
         _col_=product; _coef_=process;
         output;
         end;
    run;

The sparse format data set is shown in Figure 1.18.

Obs	_type_	_row_	_col_	_coef_
1	max	object		.
2	max	object	chocolate	0.25
3	le	process1	chocolate	15.00
4	le	process2	chocolate	0.00
5	le	process3	chocolate	18.75
6	le	process4	chocolate	12.00
7		object	toffee	0.75
8	le	process1	toffee	40.00
9	le	process2	toffee	56.25
10	le	process3	toffee	0.00
11	le	process4	toffee	50.00
12		object	licorice	1.00
13	le	process1	licorice	29.00
14	le	process2	licorice	30.00
15	le	process3	licorice	20.00
16	le	process4	licorice	20.00
17		object	jelly_beans	0.85
18	le	process1	jelly_beans	10.00
19	le	process2	jelly_beans	0.00
20	le	process3	jelly_beans	30.00
21	le	process4	jelly_beans	10.00
22		object	_RHS_	.
23	le	process1	_RHS_	27000.00
24	le	process2	_RHS_	27000.00
25	le	process3	_RHS_	27000.00
26	le	process4	_RHS_	27000.00

Figure 1.18: Sparse data format

The model data set looks a little different from the sparse representation of the candy model shown earlier. It not only includes the 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, increase the size of the manfg data set to include the new product data. Also, if the problem had more than 4 processes, 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 having hundreds of processes and products can be solved.

Chapter Contents
Previous
Next
Top