Chapter Contents
Chapter Contents
Previous
Previous
Next
Next
The LP Procedure

Example 3.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 .
     ;

   proc lp ACTIVEOUT=a PRIMALOUT=p;
   run;

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

Output 3.10.1: (continued)

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.676973 X11 0.487 1.96707 3 .
3 -2 ACTIVE 18.642641 X9 2.482 1.49839 4 .
4 -3 ACTIVE 18.402785 X12 7.379 1.62351 5 .
5 4 ACTIVE 18.296842 X6 0.636 1.94504 6 .
6 -5 ACTIVE 18.056766 X4 0.687 0.99534 7 .
7 6 ACTIVE 15.796152 X12 1.532 2.27511 8 .
8 7 ACTIVE 15.69596 X1 0.434 2.48667 9 .
9 8 ACTIVE 13.547078 X8 8.547 1.22403 10 .
10 9 ACTIVE 13.499259 X11 1.499 1.35222 11 .
11 -10 ACTIVE 13.451299 X2 0.497 1.37987 12 .
12 11 ACTIVE 12.8 X3 0.25 0.65 12 .
13 -12 ACTIVE 11.454545 X9 8.455 0.63636 13 .
14 13 ACTIVE 11.444444 X11 2.444 0.66667 14 .
15 -14 ACTIVE 11.431818 X9 7.432 0.70455 15 .
16 15 ACTIVE 11.422222 X11 3.422 0.73333 16 .
17 -16 ACTIVE 11.409091 X9 6.409 0.77273 17 .
18 17 ACTIVE 11.4 X11 4.4 0.8 18 .
19 -18 ACTIVE 11.386364 X5 0.455 0.84091 18 .
20 -19 SUBOPTIMAL 10 . . . 17 8
21 18 ACTIVE 11 X5 0.5 0.5 18 8
22 -21 FATHOMED 9.5 . . . 17 8
23 21 FATHOMED 7 . . . 16 8
24 -17 FATHOMED 11.054545 . . . 15 8
25 16 ACTIVE 11 X5 0.417 0.41667 16 8
26 -25 FATHOMED 9.25 . . . 15 8
27 25 FATHOMED 8 . . . 14 8
28 -15 FATHOMED 11.090909 . . . 13 8
29 14 ACTIVE 11 X5 0.333 0.33333 14 8
30 -29 FATHOMED 9.8571429 . . . 13 8
31 29 FATHOMED 9 . . . 12 8
32 -13 FATHOMED 11.127273 . . . 11 8
33 -11 ACTIVE 12.948052 X3 0.25 0.48377 11 8
34 -33 ACTIVE 11.233766 X8 5.234 0.41558 11 8
35 34 ACTIVE 11.204545 X9 3.205 0.38636 12 8
36 35 ACTIVE 11.2 X11 2.2 0.4 13 8
37 -36 FATHOMED 11.064935 . . . 12 8
38 36 ACTIVE 11 X5 0.25 0.25 13 8
39 -38 FATHOMED 9.9015152 . . . 12 8
40 38 FATHOMED 9 . . . 11 8
41 -35 FATHOMED 11.090909 . . . 10 8
42 10 ACTIVE 13.437662 X2 0.533 1.28171 11 8
43 42 ACTIVE 11.805195 X9 9.805 0.46861 12 8
44 -43 ACTIVE 11.69697 X12 0.697 0.56061 13 8
45 -44 INFEASIBLE 11.59596 . . . 12 8
46 44 ACTIVE 11.373377 X9 10.37 0.59984 13 8
47 -46 INFEASIBLE 10.440404 . . . 12 8
48 46 ACTIVE 11 X5 0.236 0.40278 13 8
49 -48 FATHOMED 9.5714286 . . . 12 8

Output 3.10.1: (continued)

The LP Procedure

Integer Iteration Log
Iter Problem Condition Objective Branched Value Sinfeas Active Proximity
50 48 INFEASIBLE 10 . . . 11 8
51 43 ACTIVE 11 X3 0.75 0.34091 11 8
52 -51 ACTIVE 11 X5 0.091 0.09091 11 8
53 -52 FATHOMED 9.3181818 . . . 10 8
54 -42 ACTIVE 13.087662 X3 0.257 0.43588 10 8
55 -54 ACTIVE 11.402597 X8 6.403 0.49351 11 8
56 55 ACTIVE 11.352273 X9 3.352 0.44318 12 8
57 5 ACTIVE 16.338433 X10 3.532 2.59511 13 8
58 57 ACTIVE 16.305108 X11 1.441 2.04051 14 8
59 -58 ACTIVE 16.262829 X2 0.376 2.29921 15 8
60 59 ACTIVE 15.823255 X11 2.504 2.47733 16 8
61 -60 ACTIVE 15.815163 X3 0.522 2.15025 17 8
62 61 INFEASIBLE 13.195402 . . . 16 8
63 -61 ACTIVE 14.859188 X1 0.354 1.71629 17 8
64 63 ACTIVE 12.881818 X4 0.3 0.69091 18 8
65 64 ACTIVE 11.681818 X9 8.682 0.59091 19 8
66 65 ACTIVE 11.666667 X5 0.333 0.66667 19 8
67 -66 FATHOMED 10.666667 . . . 18 8
68 -65 INFEASIBLE 11.321212 . . . 17 8
69 -64 ACTIVE 12.181818 X5 0.273 0.45455 17 8
70 -69 FATHOMED 9.7272727 . . . 16 8
71 -63 ACTIVE 13.121891 X5 0.423 1.24129 16 8
72 71 INFEASIBLE 11.755 . . . 15 8
73 60 ACTIVE 15.507892 X3 0.489 1.84958 16 8
74 73 INFEASIBLE 13.444444 . . . 15 8
75 -73 ACTIVE 14.549752 X9 6.453 1.28964 16 8
76 75 ACTIVE 14.531636 X7 3.532 1.24448 17 8
77 -76 ACTIVE 14.512121 X9 5.512 1.30303 18 8
78 77 ACTIVE 14.491636 X7 4.492 1.34776 19 8
79 -78 ACTIVE 14.354545 X9 4.548 1.52462 20 8
80 79 ACTIVE 14.111111 X1 0.472 1.68182 21 8
81 -80 ACTIVE 12.441212 X9 3.393 0.82788 22 8
82 81 ACTIVE 12.385675 X7 5.595 0.97521 23 8
83 -82 ACTIVE 11.94697 X5 0.182 0.32955 23 8
84 83 INFEASIBLE 11.083333 . . . 22 8
85 82 ACTIVE 12.121212 X4 0.212 0.51515 22 8
86 -85 FATHOMED 10.545455 . . . 21 8
87 -81 ACTIVE 11.530303 X10 0.53 0.70455 22 8
88 87 ACTIVE 11.254545 X7 5.255 0.43636 22 8
89 88 ACTIVE 11 X5 0.182 0.18182 22 8
90 -89 FATHOMED 9 . . . 21 8
91 -87 INFEASIBLE 11.173333 . . . 20 8
92 80 INFEASIBLE 12.380471 . . . 19 8
93 -79 FATHOMED 13.676136 . . . 18 8
94 78 ACTIVE 14 X1 0.538 0.94364 19 8
95 -94 ACTIVE 12.534545 X10 2.482 0.96455 20 8
96 95 ACTIVE 12.245455 X9 4.245 0.62727 21 8
97 -96 FATHOMED 11.113636 . . . 20 8
98 96 ACTIVE 12 X4 0.2 0.38182 21 8
99 -98 FATHOMED 10.989899 . . . 20 8
100 98 FATHOMED 10 . . . 19 8


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

Output 3.10.1: (continued)

The LP Procedure

Solution Summary

Terminated on Maximum Integer Iterations
Integer Feasible Solution
Objective Value 10
   
Phase 1 Iterations 0
Phase 2 Iterations 16
Phase 3 Iterations 240
Integer Iterations 100
Integer Solutions 1
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

Output 3.10.1: (continued)

The LP Procedure

Variable Summary
Col Variable Name Status Type Price Activity Reduced Cost
1 X1   BINARY 0 0 4.5
2 X2 DEGEN BINARY 0 0 0
3 X3   BINARY 0 1 -2.666667
4 X4   BINARY 0 0 2
5 X5   BINARY 0 1 -4
6 X6   BINARY 0 1 -0.833333
7 X7 DEGEN INTEGER 1 0 0
8 X8   INTEGER 1 0 -0.244444
9 X9   INTEGER 1 3 -0.333333
10 X10 DEGEN INTEGER 1 0 0
11 X11 BASIC INTEGER 1 6 0
12 X12   INTEGER 1 1 0.1666667
13 _OBS2_   SLACK 0 0 -0.166667
14 _OBS3_ BASIC SLACK 0 14 0
15 _OBS4_ BASIC SLACK 0 30 0
16 _OBS5_ BASIC SLACK 0 18 0
17 _OBS6_   SLACK 0 0 -0.5
18 _OBS7_   SLACK 0 0 -0.077778
19 _OBS8_ BASIC SLACK 0 9 0
20 _OBS9_   SLACK 0 0 -0.333333
21 _OBS10_ BASIC SLACK 0 5 0
22 _OBS11_ BASIC SLACK 0 10 0

Output 3.10.1: (continued)

The LP Procedure

Constraint Summary
Row Constraint Name Type S/S Col Rhs Activity Dual Activity
1 _OBS1_ OBJECTVE . 0 10 .
2 _OBS2_ LE 13 110 110 0.1666667
3 _OBS3_ LE 14 95 81 0
4 _OBS4_ LE 15 80 50 0
5 _OBS5_ LE 16 100 82 0
6 _OBS6_ LE 17 0 0 0.5
7 _OBS7_ LE 18 0 0 0.0777778
8 _OBS8_ LE 19 0 -9 0
9 _OBS9_ LE 20 0 0 0.3333333
10 _OBS10_ LE 21 0 -5 0
11 _OBS11_ LE 22 0 -10 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.

Chapter Contents
Chapter Contents
Previous
Previous
Next
Next
Top
Top

Copyright © 1999 by SAS Institute Inc., Cary, NC, USA. All rights reserved.