Previous Page | Next Page

The LP Procedure

Example 5.10 Restarting an Integer Program

The following example is attributed to Haldi (Garfinkel and Nemhauser 1972) and is used in the literature as a test problem. Notice that the ACTIVEOUT= and the PRIMALOUT= options are used when invoking PROC LP. These cause the LP procedure to save the primal solution in the data set named P and the active tree in the data set named A. If the procedure fails to find an optimal integer solution on the initial call, it can be called later using the A and P data sets as starting information. 


data haldi10;
   input x1-x12 _type_ $ _rhs_;
   datalines;
  0   0   0   0   0   0   1   1   1   1   1   1  MAX   .
  9   7  16   8  24   5   3   7   8   4   6   5  LE  110
 12   6   6   2  20   8   4   6   3   1   5   8  LE   95
 15   5  12   4   4   5   5   5   6   2   1   5  LE   80
 18   4   4  18  28   1   6   4   2   9   7   1  LE  100
-12   0   0   0   0   0   1   0   0   0   0   0  LE    0
  0 -15   0   0   0   0   0   1   0   0   0   0  LE    0
  0   0 -12   0   0   0   0   0   1   0   0   0  LE    0
  0   0   0 -10   0   0   0   0   0   1   0   0  LE    0
  0   0   0   0 -11   0   0   0   0   0   1   0  LE    0
  0   0   0   0   0 -11   0   0   0   0   0   1  LE    0
  1   1   1   1   1   1 1000 1000 1000 1000 1000 1000 UPPERBD .
  1   2   3   4   5   6   7   8   9  10  11  12  INTEGER .
  ;

The ACTIVEOUT= data set contains a representation of the current active problems in the branch-and-bound tree. The PRIMALOUT= data set contains a representation of the solution to the current problem. These two can be used to restore the procedure to an equivalent state to the one it was in when it stopped.

The results from the call to PROC LP is shown in Output 5.10.1. Notice that the procedure performed 100 iterations and then terminated on maximum integer iterations. This is because, by default, IMAXIT=100. The procedure reports the current best integer solution.

Output 5.10.1 Output from the HALDI10 Problem
The LP Procedure

Problem Summary
Objective Function Max _OBS1_
Rhs Variable _rhs_
Type Variable _type_
Problem Density (%) 31.82
   
Variables Number
   
Integer 6
Binary 6
Slack 10
   
Total 22
   
Constraints Number
   
LE 10
Objective 1
   
Total 11

The LP Procedure

Integer Iteration Log
Iter Problem Condition Objective Branched Value Sinfeas Active Proximity
1 0 ACTIVE 18.709524 x9 1.543 1.11905 2 .
2 1 ACTIVE 18.467723 x12 9.371 0.88948 3 .
3 2 ACTIVE 18.460133 x8 0.539 1.04883 4 .
4 -3 ACTIVE 18.453638 x12 8.683 1.12993 5 .
5 4 ACTIVE 18.439678 x10 7.448 1.20125 6 .
6 5 ACTIVE 18.403728 x6 0.645 1.3643 7 .
7 -6 ACTIVE 18.048289 x4 0.7 1.18395 8 .
8 -7 ACTIVE 17.679087 x8 1.833 0.52644 9 .
9 8 ACTIVE 17.52 x10 6.667 0.70111 10 .
10 9 ACTIVE 17.190085 x12 7.551 1.37615 11 .
11 -10 ACTIVE 17.02 x1 0.085 0.255 12 .
12 11 ACTIVE 16.748 x11 0.748 0.47 13 .
13 -12 ACTIVE 16.509091 x9 0.509 0.69091 14 .
14 13 ACTIVE 16.261333 x11 1.261 0.44267 15 .
15 14 ACTIVE 16 x3 0.297 0.45455 16 .
16 15 ACTIVE 16 x5 0.091 0.15758 16 .
17 -16 INFEASIBLE -0.4 . . . 15 .
18 -15 ACTIVE 11.781818 x10 1.782 0.37576 15 .
19 18 ACTIVE 11 x5 0.091 0.15758 15 .
20 -19 INFEASIBLE -6.4 . . . 14 .
21 -14 ACTIVE 11.963636 x5 0.182 0.28485 14 .
22 -21 INFEASIBLE -4.4 . . . 13 .
23 -13 ACTIVE 15.281818 x10 4.282 0.52273 13 .
24 23 ACTIVE 15.041333 x5 0.095 0.286 14 .
25 -24 INFEASIBLE -2.9 . . . 13 .
26 24 INFEASIBLE 14 . . . 12 .
27 12 ACTIVE 16 x3 0.083 0.15 13 .
28 -27 ACTIVE 15.277778 x9 0.278 0.34444 14 .
29 -28 ACTIVE 13.833333 x10 3.833 0.23333 14 .
30 29 ACTIVE 13 x2 0.4 0.4 15 .
31 30 INFEASIBLE 12 . . . 14 .
32 -30 SUBOPTIMAL 10 . . . 13 8
33 28 ACTIVE 15 x2 0.067 0.06667 13 8
34 -33 SUBOPTIMAL 12 . . . 12 6
35 27 ACTIVE 15 x2 0.067 0.06667 12 6
36 -35 SUBOPTIMAL 15 . . . 11 3
37 -11 FATHOMED 14.275 . . . 10 3
38 10 ACTIVE 16.804848 x1 0.158 0.50313 11 3
39 -38 FATHOMED 14.784 . . . 10 3
40 38 ACTIVE 16.40381 x11 1.404 0.68143 11 3
41 -40 ACTIVE 16.367677 x10 5.368 0.69949 12 3
42 41 ACTIVE 16.113203 x11 2.374 1.00059 12 3
43 42 ACTIVE 16 x5 0.182 0.33182 12 3
44 -43 FATHOMED 13.822222 . . . 11 3
45 -41 FATHOMED 12.642424 . . . 10 3
46 40 ACTIVE 16 x5 0.229 0.37857 10 3
47 46 FATHOMED 15 . . . 9 3
48 -9 ACTIVE 17.453333 x7 0.453 0.64111 10 3
49 48 ACTIVE 17.35619 x11 0.356 0.53857 11 3
50 49 ACTIVE 17 x5 0.121 0.27143 12 3
51 50 ACTIVE 17 x3 0.083 0.15 13 3
52 -51 FATHOMED 15.933333 . . . 12 3
53 51 ACTIVE 16 x2 0.067 0.06667 12 3
54 -53 SUBOPTIMAL 16 . . . 8 2
55 -8 ACTIVE 17.655399 x12 7.721 0.56127 9 2
56 55 ACTIVE 17.519375 x10 6.56 0.76125 10 2
57 56 ACTIVE 17.256874 x2 0.265 0.67388 11 2
58 57 INFEASIBLE 17.167622 . . . 10 2
59 -57 FATHOMED 16.521755 . . . 9 2
60 -56 FATHOMED 17.03125 . . . 8 2
61 -55 ACTIVE 17.342857 x9 0.343 0.50476 8 2
62 61 ACTIVE 17.2225 x7 0.16 0.37333 9 2
63 62 ACTIVE 17.1875 x8 2.188 0.33333 9 2
64 63 ACTIVE 17.153651 x11 0.154 0.30095 10 2
65 -64 FATHOMED 12.381818 . . . 9 2
66 64 ACTIVE 17 x2 0.133 0.18571 9 2
67 -66 FATHOMED 13 . . . 8 2
68 -62 FATHOMED 14.2 . . . 7 2
69 7 FATHOMED 15.428583 . . . 6 2
70 6 FATHOMED 16.75599 . . . 5 2
71 -5 ACTIVE 17.25974 x6 0.727 0.82078 5 2
72 -71 FATHOMED 17.142857 . . . 4 2
73 -4 ACTIVE 18.078095 x4 0.792 0.70511 5 2
74 -73 ACTIVE 17.662338 x10 7.505 0.91299 5 2
75 74 ACTIVE 17.301299 x9 0.301 0.57489 5 2
76 75 ACTIVE 17.210909 x7 0.211 0.47697 5 2
77 76 FATHOMED 17.164773 . . . 4 2
78 73 FATHOMED 12.872727 . . . 3 2
79 3 ACTIVE 18.368316 x10 7.602 1.20052 4 2
80 79 ACTIVE 18.198323 x7 1.506 1.85351 5 2
81 80 ACTIVE 18.069847 x12 8.517 1.67277 6 2
82 -81 ACTIVE 17.910909 x4 0.7 0.73015 7 2
83 -82 ACTIVE 17.790909 x7 0.791 0.54015 8 2
84 -83 ACTIVE 17.701299 x9 0.701 0.62229 8 2
85 84 ACTIVE 17.17619 x6 0.818 0.45736 8 2
86 -85 ACTIVE 17.146667 x11 0.147 0.24333 8 2
87 86 ACTIVE 17 x1 0.167 0.16667 8 2
88 87 INFEASIBLE 16 . . . 7 2
89 83 ACTIVE 17.58 x11 0.58 0.73788 8 2
90 -89 FATHOMED 17.114286 . . . 7 2
91 -80 ACTIVE 18.044048 x12 8.542 1.71158 8 2
92 91 ACTIVE 17.954536 x11 0.477 1.90457 9 2
93 92 ACTIVE 17.875084 x4 0.678 1.16624 10 2
94 93 FATHOMED 13.818182 . . . 9 2
95 -93 ACTIVE 17.231221 x6 0.727 0.76182 9 2
96 -95 FATHOMED 17.085714 . . . 8 2
97 -92 FATHOMED 17.723058 . . . 7 2
98 -91 FATHOMED 16.378788 . . . 6 2
99 89 ACTIVE 17 x6 0.818 0.26515 6 2
100 -99 ACTIVE 17 x3 0.083 0.08333 6 2 

WARNING: The maximum number of integer iterations has been exceeded. Increase 
         this limit with the 'IMAXIT=' option on the RESET statement.

The LP Procedure

Solution Summary

Terminated on Maximum Integer Iterations
Integer Feasible Solution
Objective Value 16
   
Phase 1 Iterations 0
Phase 2 Iterations 13
Phase 3 Iterations 161
Integer Iterations 100
Integer Solutions 4
Initial Basic Feasible Variables 12
Time Used (seconds) 0
Number of Inversions 37
   
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

The LP Procedure

Variable Summary
Col Variable Name Status Type Price Activity Reduced Cost
1 x1 DEGEN BINARY 0 0 0
2 x2 ALTER BINARY 0 1 0
3 x3   BINARY 0 0 12
4 x4 ALTER BINARY 0 1 0
5 x5 ALTER BINARY 0 0 0
6 x6 ALTER BINARY 0 1 0
7 x7   INTEGER 1 0 1
8 x8   INTEGER 1 1 1
9 x9 DEGEN INTEGER 1 0 0
10 x10   INTEGER 1 7 1
11 x11   INTEGER 1 0 1
12 x12   INTEGER 1 8 1
13 _OBS2_ BASIC SLACK 0 15 0
14 _OBS3_ BASIC SLACK 0 2 0
15 _OBS4_ BASIC SLACK 0 7 0
16 _OBS5_ BASIC SLACK 0 2 0
17 _OBS6_ ALTER SLACK 0 0 0
18 _OBS7_ BASIC SLACK 0 14 0
19 _OBS8_   SLACK 0 0 -1
20 _OBS9_ BASIC SLACK 0 3 0
21 _OBS10_ DEGEN SLACK 0 0 0
22 _OBS11_ BASIC SLACK 0 3 0

The LP Procedure

Constraint Summary
Row Constraint Name Type S/S Col Rhs Activity Dual Activity
1 _OBS1_ OBJECTVE . 0 16 .
2 _OBS2_ LE 13 110 95 0
3 _OBS3_ LE 14 95 93 0
4 _OBS4_ LE 15 80 73 0
5 _OBS5_ LE 16 100 98 0
6 _OBS6_ LE 17 0 0 0
7 _OBS7_ LE 18 0 -14 0
8 _OBS8_ LE 19 0 0 1
9 _OBS9_ LE 20 0 -3 0
10 _OBS10_ LE 21 0 0 0
11 _OBS11_ LE 22 0 -3 0

To continue with the solution of this problem, invoke PROC LP with the ACTIVEIN= and PRIMALIN= options and reset the IMAXIT= option. This restores the branch-and-bound tree and simplifies calculating a basic feasible solution from which to start processing. 

proc lp data=haldi10 activein=a primalin=p imaxit=250;
run;

The procedure picks up iterating from a equivalent state to where it left off. The problem will still not be solved when IMAXIT=250 occurs.

Previous Page | Next Page | Top of Page

Copyright © SAS Institute, Inc. All Rights Reserved.