Introduction to Optimization: PROC OPTLP :: SAS/OR(R) 9.22 User's Guide: Mathematical Programming

Introduction to Optimization

PROC OPTLP

A small product-mix problem serves as a starting point for a discussion of different types of model formats supported in SAS/OR software.

A candy manufacturer makes two products: chocolates and toffee. What combination of chocolates and toffee should be produced in a day in order to maximize the company’s profit? Chocolates contribute $0.25 per pound to profit, and toffee contributes $0.75 per pound. The decision variables are chocolates and toffee.

Four processes are used to manufacture the candy:

Process 1 combines and cooks the basic ingredients for both chocolates and toffee.
Process 2 adds colors and flavors to the toffee, then cools and shapes the confection.
Process 3 chops and mixes nuts and raisins, adds them to the chocolates, and then cools and cuts the bars.
Process 4 is packaging: chocolates are placed in individual paper shells; toffee is wrapped in cellophane packages.

During the day, there are 7.5 hours (27,000 seconds) available for each process.

Firm time standards have been established for each process. For Process 1, mixing and cooking take 15 seconds for each pound of chocolate, and 40 seconds for each pound of toffee. Process 2 takes 56.25 seconds per pound of toffee. For Process 3, each pound of chocolate requires 18.75 seconds of processing. In packaging, a pound of chocolates can be wrapped in 12 seconds, whereas a pound of toffee requires 50 seconds. These data are summarized as follows:

                      Available       Required per Pound
                        Time         chocolates     toffee
     Process            (sec)          (sec)         (sec)
   1 Cooking            27,000           15          40
   2 Color/Flavor       27,000                      56.25
   3 Condiments         27,000          18.75
   4 Packaging          27,000           12          50

The objective is to

Maximize: 0.25(chocolates) + 0.75(toffee)

which is the company’s total profit.

The production of the candy is limited by the time available for each process. The limits placed on production by Process 1 are expressed by the following inequality:

Process 1: 15(chocolates) + 40(toffee) $\text{[math]}$ 27,000

Process 1 can handle any combination of chocolates and toffee that satisfies this inequality.

The limits on production by other processes generate constraints described by the following inequalities:

Process 2: 56.25(toffee) $\text{[math]}$ 27,000

Process 3: 18.75(chocolates) $\text{[math]}$ 27,000

Process 4: 12(chocolates) + 50(toffee) $\text{[math]}$ 27,000

This linear program illustrates the type of problem known as a product mix example. The mix of products that maximizes the objective without violating the constraints is the solution. This model can be represented in an MPS-format SAS data set.

Dense Format

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 equations corresponding to 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;

Sparse Format

Typically, mathematical programming models are sparse; that is, few of the coefficients in the constraint matrix are nonzero. The OPTLP procedure accepts data in an MPS-format SAS data set, which is an efficient way to represent sparse models. Only the nonzero coefficients must be specified. It is consistent with the standard MPS sparse format, and much more flexible; models using the MPS format can be easily converted to the LP format. The appendix at the end of this book describes a SAS macro for conversion.

An example of an MPS-format SAS data set is illustrated 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 OPTLP, specify the following:

proc lp data=sp_factory sparsedata; 
run;

The Solution Summary (shown in Figure 3.1) gives information about the solution that was found, including whether the optimizer terminated successfully after finding the optimum.

When PROC OPTLP solves a problem, it uses an iterative process. First, the procedure finds a feasible solution that satisfies the constraints. Second, it finds the optimal solution from the set of feasible solutions. The Solution Summary 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.

Figure 3.1 Solution Summary

The LP Procedure

Solution Summary
Terminated Successfully
Objective Value	475

Phase 1 Iterations	0
Phase 2 Iterations	3
Phase 3 Iterations	0
Integer Iterations	0
Integer Solutions	0
Initial Basic Feasible Variables	6
Time Used (seconds)	0
Number of Inversions	3

Epsilon	1E-8
Infinity	1.797693E308
Maximum Phase 1 Iterations	100
Maximum Phase 2 Iterations	100
Maximum Phase 3 Iterations	99999999
Maximum Integer Iterations	100
Time Limit (seconds)	120

Separating the Data from the Model Structure

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, 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 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 use the candy data to build a sparse format model to solve the product mix problem.

data model;
array process 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 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 3.2.

Figure 3.2 Sparse Data Format

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

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 having hundreds of processes and products can be solved.

Top of Page