The OPTMILP Procedure

Example 13.1 Simple Integer Linear Program

This example illustrates a model in an MPS-format SAS data set. This data set is passed to PROC OPTMILP, and a solution is found.

Consider a scenario where you have a container with a set of limiting attributes (volume V and weight W) and a set I of items that you want to pack. Each item type i has a certain value $p_ i$, a volume $v_ i$, and a weight $w_ i$. You must choose at most four items of each type so that the total value is maximized and all the chosen items fit into the container. Let $x_ i$ be the number of items of type i to be included in the container. This model can be formulated as the following integer linear program:

\[  \begin{array}{llllll} \max &  \displaystyle \sum _{i \in I} p_ i x_ i & \\ \mr{s.t.} &  \displaystyle \sum _{i \in I} v_ i x_ i &  \leq &  V & &  \mr{(volume\_ con)}\\ &  \displaystyle \sum _{i \in I} w_ i x_ i &  \leq &  W & &  \mr{(weight\_ con)}\\ &  x_ i &  \leq &  4 &  \forall i \in I\\ &  x_ i \in \mathbb {Z}^{+} & & &  \forall i \in I\\ \end{array}  \]

Constraint (volume_con) enforces the volume capacity limit, while constraint (weight_con) enforces the weight capacity limit. An instance of this problem can be saved in an MPS-format SAS data set by using the following code:

data ex1data;
    input field1 $ field2 $ field3 $ field4 field5 $ field6;
    datalines;
NAME       .             ex1data           .     .                 .
ROWS       .             .                 .     .                 .
MAX        z             .                 .     .                 .
L          volume_con    .                 .     .                 .
L          weight_con    .                 .     .                 .
COLUMNS    .             .                 .     .                 .
.          .MRK0         'MARKER'          .     'INTORG'          .
.          x[1]          z                 1     volume_con       10
.          x[1]          weight_con       12     .                 .
.          x[2]          z                 2     volume_con      300
.          x[2]          weight_con       15     .                 .
.          x[3]          z                 3     volume_con      250
.          x[3]          weight_con       72     .                 .
.          x[4]          z                 4     volume_con      610
.          x[4]          weight_con      100     .                 .
.          x[5]          z                 5     volume_con      500
.          x[5]          weight_con      223     .                 .
.          x[6]          z                 6     volume_con      120
.          x[6]          weight_con       16     .                 .
.          x[7]          z                 7     volume_con       45
.          x[7]          weight_con       73     .                 .
.          x[8]          z                 8     volume_con      100
.          x[8]          weight_con       12     .                 .
.          x[9]          z                 9     volume_con      200
.          x[9]          weight_con      200     .                 .
.          x[10]         z                10     volume_con       61
.          x[10]         weight_con      110     .                 .
.          .MRK1         'MARKER'          .     'INTEND'          .
RHS        .             .                 .     .                 .
.          .RHS.         volume_con     1000     .                 .
.          .RHS.         weight_con      500     .                 .
BOUNDS     .             .                 .     .                 .
UP         .BOUNDS.      x[1]              4     .                 .
UP         .BOUNDS.      x[2]              4     .                 .
UP         .BOUNDS.      x[3]              4     .                 .
UP         .BOUNDS.      x[4]              4     .                 .
UP         .BOUNDS.      x[5]              4     .                 .
UP         .BOUNDS.      x[6]              4     .                 .
UP         .BOUNDS.      x[7]              4     .                 .
UP         .BOUNDS.      x[8]              4     .                 .
UP         .BOUNDS.      x[9]              4     .                 .
UP         .BOUNDS.      x[10]             4     .                 .
ENDATA     .             .                 .     .                 .
;

In the COLUMNS section of this data set, the name of the objective is z, and the objective coefficients $p_ i$ appear in field4. The coefficients $v_ i$ of (volume_con) appear in field6. The coefficients $w_ i$ of (weight_con) appear in field4. In the RHS section, the bounds V and W appear in field4. This problem can be solved by using the following statements to call the OPTMILP procedure:


proc optmodel;
    num nItems          = 10;
    num volume_capacity = 1000;
    num weight_capacity = 500;
    set<num> Items = {1..nItems};
    num value{Items}  = [1,2,3,4,5,6,7,8,9,10];
    num volume{Items} = [10, 300, 250, 610, 500, 120, 45, 100, 200, 61 ];
    num weight{Items} = [12,  15,  72, 100, 223,  16, 73,  12, 200, 110];
    var x{Items} integer >= 0 <= 4;
    max z = sum{i in Items} value[i] * x[i];
    con volume_con: sum{i in Items} volume[i] * x[i] <= volume_capacity;
    con weight_con: sum{i in Items} weight[i] * x[i] <= weight_capacity;
    save mps ex1data;
  quit;
run;
proc optmilp data=ex1data primalout=ex1soln;
run;

The progress of the solver is shown in Output 13.1.1.

Output 13.1.1: Simple Integer Linear Program PROC OPTMILP Log

NOTE: The OPTMILP procedure is executing in single-machine mode.                
NOTE: The problem ex1data has 10 variables (0 binary, 10 integer, 0 free, 0     
      fixed).                                                                   
NOTE: The problem has 2 constraints (2 LE, 0 EQ, 0 GE, 0 range).                
NOTE: The problem has 20 constraint coefficients.                               
NOTE: The MILP presolver value AUTOMATIC is applied.                            
NOTE: The MILP presolver removed 0 variables and 0 constraints.                 
NOTE: The MILP presolver removed 0 constraint coefficients.                     
NOTE: The MILP presolver modified 0 constraint coefficients.                    
NOTE: The presolved problem has 10 variables, 2 constraints, and 20 constraint  
      coefficients.                                                             
NOTE: The MILP solver is called.                                                
          Node  Active    Sols    BestInteger      BestBound      Gap    Time   
             0       1       3     85.0000000    178.0000000   52.25%       0   
             0       1       3     85.0000000     88.0955497    3.51%       0   
             0       1       3     85.0000000     88.0955497    3.51%       0   
             0       1       3     85.0000000     88.0955497    3.51%       0   
NOTE: The MILP presolver is applied again.                                      
             0       1       3     85.0000000     88.0955497    3.51%       0   
             0       1       3     85.0000000     88.0955497    3.51%       0   
             0       1       3     85.0000000     88.0626822    3.48%       0   
             0       1       3     85.0000000     87.8820655    3.28%       0   
             0       1       4     85.0000000     87.8539763    3.25%       0   
             0       1       4     85.0000000     87.7208690    3.10%       0   
             0       1       4     85.0000000     87.7180302    3.10%       0   
             0       1       4     85.0000000     87.7133502    3.09%       0   
             0       1       4     85.0000000     87.7128245    3.09%       0   
             0       1       4     85.0000000     87.7124806    3.09%       0   
NOTE: The MILP solver added 2 cuts with 8 cut coefficients at the root.         
             5       3       5     87.0000000     87.0000000    0.00%       0   
NOTE: Optimal.                                                                  
NOTE: Objective = 87.                                                           
NOTE: The data set WORK.EX1SOLN has 10 observations and 8 variables.            



The data set ex1soln is shown in Output 13.1.2.

Output 13.1.2: Simple Integer Linear Program Solution

Example 1 Solution Data

Objective
Function ID
RHS ID Variable Name Variable
Type
Objective
Coefficient
Lower
Bound
Upper
Bound
Variable
Value
z .RHS. x[1] I 1 0 4 0
z .RHS. x[2] I 2 0 4 0
z .RHS. x[3] I 3 0 4 0
z .RHS. x[4] I 4 0 4 0
z .RHS. x[5] I 5 0 4 0
z .RHS. x[6] I 6 0 4 3
z .RHS. x[7] I 7 0 4 1
z .RHS. x[8] I 8 0 4 4
z .RHS. x[9] I 9 0 4 0
z .RHS. x[10] I 10 0 4 3



The optimal solution is $x_6 = 3, x_7 = 1, x_8 = 4$, and $x_{10} = 3$, with a total value of 87. From this solution, you can compute the total volume used, which is 988 ($\leq V = 1000$); the total weight used is 499 ($\leq W = 500$). The problem summary and solution summary are shown in Output 13.1.3.


proc optmodel;
    num nItems          = 10;
    num volume_capacity = 1000;
    num weight_capacity = 500;
    set<num> Items = {1..nItems};
    num value{Items}  = [1,2,3,4,5,6,7,8,9,10];
    num volume{Items} = [10, 300, 250, 610, 500, 120, 45, 100, 200, 61 ];
    num weight{Items} = [12,  15,  72, 100, 223,  16, 73,  12, 200, 110];
    var x{Items} integer >= 0 <= 4;
    max z = sum{i in Items} value[i] * x[i];
    con volume_con: sum{i in Items} volume[i] * x[i] <= volume_capacity;
    con weight_con: sum{i in Items} weight[i] * x[i] <= weight_capacity;
    save mps ex1data;
  quit;
run;
proc optmilp data=ex1data primalout=ex1soln;
title ' ';
run;

Output 13.1.3: Simple Integer Linear Program Summary

 

The OPTMILP Procedure

Problem Summary
Problem Name ex1data
Objective Sense Maximization
Objective Function z
RHS .RHS.
   
Number of Variables 10
Bounded Above 0
Bounded Below 0
Bounded Above and Below 10
Free 0
Fixed 0
Binary 0
Integer 10
   
Number of Constraints 2
LE (<=) 2
EQ (=) 0
GE (>=) 0
Range 0
   
Constraint Coefficients 20

Performance Information
Execution Mode Single-Machine
Number of Threads 1

Solution Summary
Solver MILP
Algorithm Branch and Cut
Objective Function z
Solution Status Optimal
Objective Value 87
   
Relative Gap 0
Absolute Gap 0
Primal Infeasibility 0
Bound Infeasibility 0
Integer Infeasibility 0
   
Best Bound 87
Nodes 6
Iterations 95
Presolve Time 0.00
Solution Time 0.00