The OPTMILP Procedure

Example 7.1 Simple Integer Linear Program

This example illustrates a model in an MPS-format data table. This data table 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 , a volume , and a weight . 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 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:

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 data table by using the following code:

data mycas.ex1data;
   input _id_ field1 $ field2 $ field3 $ field4 field5 $ field6;
   datalines;
1  NAME       .             ex1data           .     .                 .
2  ROWS       .             .                 .     .                 .
3  MAX        z             .                 .     .                 .
4  L          volume_con    .                 .     .                 .
5  L          weight_con    .                 .     .                 .
6  COLUMNS    .             .                 .     .                 .
7  .          .MRK0         'MARKER'          .     'INTORG'          .
8  .          x[1]          z                 1     volume_con       10
9  .          x[1]          weight_con       12     .                 .
10 .          x[2]          z                 2     volume_con      300
11 .          x[2]          weight_con       15     .                 .
12 .          x[3]          z                 3     volume_con      250
13 .          x[3]          weight_con       72     .                 .
14 .          x[4]          z                 4     volume_con      610
15 .          x[4]          weight_con      100     .                 .
16 .          x[5]          z                 5     volume_con      500
17 .          x[5]          weight_con      223     .                 .
18 .          x[6]          z                 6     volume_con      120
19 .          x[6]          weight_con       16     .                 .
20 .          x[7]          z                 7     volume_con       45
21 .          x[7]          weight_con       73     .                 .
22 .          x[8]          z                 8     volume_con      100
23 .          x[8]          weight_con       12     .                 .
24 .          x[9]          z                 9     volume_con      200
25 .          x[9]          weight_con      200     .                 .
26 .          x[10]         z                10     volume_con       61
27 .          x[10]         weight_con      110     .                 .
28 .          .MRK1         'MARKER'          .     'INTEND'          .
29 RHS        .             .                 .     .                 .
30 .          .RHS.         volume_con     1000     .                 .
31 .          .RHS.         weight_con      500     .                 .
32 BOUNDS     .             .                 .     .                 .
33 UP         .BOUNDS.      x[1]              4     .                 .
34 UP         .BOUNDS.      x[2]              4     .                 .
35 UP         .BOUNDS.      x[3]              4     .                 .
36 UP         .BOUNDS.      x[4]              4     .                 .
37 UP         .BOUNDS.      x[5]              4     .                 .
38 UP         .BOUNDS.      x[6]              4     .                 .
39 UP         .BOUNDS.      x[7]              4     .                 .
40 UP         .BOUNDS.      x[8]              4     .                 .
41 UP         .BOUNDS.      x[9]              4     .                 .
42 UP         .BOUNDS.      x[10]             4     .                 .
43 ENDATA     .             .                 .     .                 .
;

In the COLUMNS section of this data table, the name of the objective is z, and the objective coefficients appear in field4. The coefficients of (volume_con) appear in field6. The coefficients of (weight_con) appear in field4. In the RHS section, the bounds V and W appear in field4. The _id_ column ensures that the data can be read in the right order even if the table is stored on separate machines in CAS. This problem can be solved by using the following statements to call the OPTMILP procedure:

proc optmilp data=mycas.ex1data primalout=mycas.ex1soln;
run;

The progress of the solver is shown in Output 7.1.1.

Output 7.1.1: Simple Integer Linear Program PROC OPTMILP Log

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 initial MILP heuristics are applied.

NOTE: The MILP presolver value AUTOMATIC is applied.

NOTE: The MILP presolver removed 2 variables and 0 constraints.

NOTE: The MILP presolver removed 4 constraint coefficients.

NOTE: The MILP presolver modified 0 constraint coefficients.

NOTE: The presolved problem has 8 variables, 2 constraints, and 16 constraint

coefficients.

NOTE: The MILP solver is called.

NOTE: The parallel Branch and Cut algorithm is used.

NOTE: The Branch and Cut algorithm is using up to 32 threads.

Node Active Sols BestInteger BestBound Gap Time

0 1 3 85.0000000 158.0000000 46.20% 0

0 1 3 85.0000000 88.0955497 3.51% 0

0 1 3 85.0000000 87.4545455 2.81% 0

NOTE: The MILP presolver is applied again.

0 1 4 87.0000000 87.4545455 0.52% 0

NOTE: Optimal.

NOTE: Objective = 87.

NOTE: The Cloud Analytic Services server processed the request in 0.071343

seconds.

NOTE: The data set MYCAS.EX1SOLN has 10 observations and 9 variables.

The data table ex1soln is shown in Output 7.1.2.

Output 7.1.2: Simple Integer Linear Program Solution

Example 1 Solution Data

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

The optimal solution is , and , with a total value of 87. From this solution, you can compute the total volume used, which is 988 (); the total weight used is 499 (). The problem summary and solution summary are shown in Output 7.1.3.

Output 7.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

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	1
Solutions Found	4
Iterations	14

Presolve Time	0.00
Solution Time	0.02

Last updated: June 14, 2018