Introduction to Optimization

PROC OPTLP

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:

1. Process 1 combines and cooks the basic ingredients for both chocolates and toffee.
2. Process 2 adds colors and flavors to the toffee, then cools and shapes the confection.
3. Process 3 chops and mixes nuts and raisins, adds them to the chocolates, and then cools and cuts the bars.
4. 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) 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) 27,000

  Process 3:    18.75(chocolates) 27,000

  Process 4:    12(chocolates) + 50(toffee) 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.

MPS-Format SAS Data Set

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.

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; 
            length field2 field3 field5 $10; 
            input field1 $ field2 $ field3 $ field4 field5 $ field6; 
    datalines; 
    NAME     .         factory   .         .         . 
    ROWS     .         .         .         .         . 
    MAX      object    .         .         .         . 
    L        process1  .         .         .         . 
    L        process2  .         .         .         . 
    L        process3  .         .         .         . 
    L        process4  .         .         .         . 
    COLUMNS  .         .         .         .         . 
    .        chocolate object    .25       process1  15 
    .        chocolate process3  18.75     process4  12 
    .        toffee    object    .75       process1  40 
    .        toffee    process2  56.25     process4  50 
    RHS      .         .         .         .         . 
    .        _RHS_     process1  27000     .         . 
    .        _RHS_     process2  27000     .         . 
    .        _RHS_     process3  27000     .         . 
    .        _RHS_     process4  27000     .         . 
    ENDATA   .         .         .         .         . 
    ;
 

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

  
    proc optlp data = sp_factory; 
    run;
 

The Solution Summary (shown in Figure 1.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.

The OPTLP Procedure Solution Summary Solver Dual simplex Objective Function object Solution Status Optimal Objective Value 475     Primal Infeasibility 0 Dual Infeasibility 0 Bound Infeasibility 0     Iterations 2 Presolve Time 0.00 Solution Time 0.00

Figure 1.1: Solution Summary