Chapter Contents
Chapter Contents		 Previous
Previous		 Next
Next
The LP Procedure

Example 3.11: Alternative Search of the Branch and Bound Tree

In this example, the HALDI10 problem is solved. However, here the default strategy for searching the branch and bound tree is modified. By default, the search strategy has VARSELECT=FAR. This means that when searching for an integer variable on which to branch, the procedure uses the one that has a value farthest from an integer value. An alternative strategy has VARSELECT=PENALTY. This strategy causes PROC LP to look at the cost, in terms of the objective function, of branching on an integer variable. The procedure looks at PENALTYDEPTH= integer variables before choosing the one with the largest cost. This is a much more expensive strategy (in terms of execution time) than the VARSELECT=FAR strategy, but it can be beneficial if fewer integer iterations must be done to find an optimal solution. 

   proc lp VARSELECT=PENALTY;
   run;

Compare the number of integer iterations needed to solve the problem using this heuristic with the default strategy used in Example 3.10. In this example, the difference is profound; in general, solution times can vary significantly with the search technique. See Output 3.11.1.

Output 3.11.1: Summaries and an Integer Programming Iteration Log: Using VARSELECT=PENALTY

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.11.1: (continued)

The LP Procedure

Integer Iteration Log
Iter Problem Condition Objective Branched Value Sinfeas Active Proximity
1 0 ACTIVE 18.709524 X3 0.129 1.11905 2 .
2 -1 ACTIVE 17.063758 X4 0.694 0.89262 3 .
3 2 ACTIVE 15.225596 X5 0.459 2.34336 4 .
4 3 ACTIVE 12.7375 X2 0.812 0.875 5 .
5 -4 ACTIVE 12.55 X6 0.05 0.5 6 .
6 5 ACTIVE 12.54 X7 0.24 0.56 7 .
7 -6 ACTIVE 12.35 X1 0.083 0.43333 7 .
8 -7 ACTIVE 9.6 X8 8.6 0.4 8 .
9 8 ACTIVE 9.6 X7 1.6 0.4 9 .
10 -9 ACTIVE 9.6 X8 7.6 0.4 10 .
11 10 ACTIVE 9.6 X7 2.6 0.4 11 .
12 -11 ACTIVE 9.6 X8 6.6 0.4 12 .
13 12 ACTIVE 9.6 X7 3.6 0.4 13 .
14 -13 ACTIVE 9.6 X8 5.6 0.4 14 .
15 14 ACTIVE 9.6 X7 4.6 0.4 15 .
16 -15 ACTIVE 9.6 X8 4.6 0.4 16 .
17 16 ACTIVE 9.6 X7 5.6 0.4 17 .
18 -17 ACTIVE 9.6 X8 3.6 0.4 18 .
19 18 ACTIVE 9.6 X7 6.6 0.4 19 .
20 -19 ACTIVE 9.6 X8 2.6 0.4 20 .
21 20 ACTIVE 9.6 X7 7.6 0.4 21 .
22 -21 ACTIVE 9.6 X8 1.6 0.4 22 .
23 22 ACTIVE 9.6 X7 8.6 0.4 23 .
24 -23 ACTIVE 9.6 X8 0.6 0.4 24 .
25 24 ACTIVE 9.6 X7 9.6 0.4 25 .
26 -25 INFEASIBLE 8.5333333 . . . 24 .
27 25 ACTIVE 9.5 X9 0.5 0.5 25 .
28 -27 INFEASIBLE 7.8 . . . 24 .
29 27 SUBOPTIMAL 9 . . . 6 9
30 6 ACTIVE 12.428571 X8 12.43 0.42857 7 9
31 30 ACTIVE 12.375 X9 0.375 0.375 8 9
32 31 SUBOPTIMAL 12 . . . 3 6
33 -3 FATHOMED 13.063239 . . . 2 6
34 -2 ACTIVE 16.547134 X6 0.816 0.78733 3 6
35 34 ACTIVE 14.46789 X1 0.128 0.91743 4 6
36 35 ACTIVE 14.28125 X9 7.219 0.28125 5 6
37 36 ACTIVE 14.257979 X8 0.279 0.31915 6 6
38 -37 ACTIVE 14.197917 X2 0.067 0.73958 6 6
39 -38 ACTIVE 13.25 X10 6.5 0.75 7 6
40 39 ACTIVE 13.222222 X9 4.444 0.66667 8 6
41 40 ACTIVE 13.212766 X10 5.83 0.55319 9 6
42 41 ACTIVE 13.166667 X8 6.333 0.5 10 6
43 -42 ACTIVE 13.15625 X10 4.812 0.53125 11 6
44 43 SUBOPTIMAL 13 . . . 4 5
45 37 ACTIVE 14.111111 X10 7.111 0.11111 4 5
46 45 ACTIVE 14.104762 X5 0.01 0.11429 5 5
47 -46 FATHOMED 10.230769 . . . 4 5
48 46 SUBOPTIMAL 14 . . . 2 4
49 -34 ACTIVE 16.363499 X12 8.796 0.78733 3 4

Output 3.11.1: (continued)

The LP Procedure

Integer Iteration Log
Iter Problem Condition Objective Branched Value Sinfeas Active Proximity
50 49 ACTIVE 16.220741 X9 0.782 0.86074 4 4
51 -50 ACTIVE 16.179592 X12 7.776 0.72653 5 4
52 51 ACTIVE 15.997778 X9 1.633 1.07778 6 4
53 52 ACTIVE 15.927381 X2 0.054 0.77381 7 4
54 53 ACTIVE 15.660606 X1 0.053 0.45253 8 4
55 -54 FATHOMED 13.386667 . . . 7 4
56 54 ACTIVE 15.555556 X10 7.556 0.44444 8 4
57 56 ACTIVE 15.52381 X5 0.048 0.52381 9 4
58 -57 FATHOMED 12.853333 . . . 8 4
59 57 SUBOPTIMAL 15 . . . 3 3
60 50 FATHOMED 16.117029 . . . 2 3
61 -49 SUBOPTIMAL 16 . . . 1 2
62 1 ACTIVE 18.0223 X4 0.827 0.81338 2 2
63 62 FATHOMED 15.927292 . . . 1 1
64 -62 ACTIVE 17.67723 X10 7.93 0.43662 2 1
65 64 ACTIVE 17.488782 X6 0.737 0.91026 3 1
66 -65 ACTIVE 17.225962 X8 2.38 0.69231 4 1
67 66 ACTIVE 17.221818 X1 0.016 0.37111 5 1
68 -67 FATHOMED 14.5 . . . 4 1
69 67 FATHOMED 17.172375 . . . 3 1
70 -66 FATHOMED 17.138028 . . . 2 1
71 65 FATHOMED 15.784375 . . . 1 1
72 -64 ACTIVE 17.166667 X6 0.833 0.33333 1 1
73 -72 SUBOPTIMAL 17 . . . 0 .

Output 3.11.1: (continued)

The LP Procedure

Solution Summary

Integer Optimal Solution
Objective Value 17
   
Phase 1 Iterations 0
Phase 2 Iterations 16
Phase 3 Iterations 111
Integer Iterations 73
Integer Solutions 7
Initial Basic Feasible Variables 12
Time Used (seconds) 0
Number of Inversions 20
   
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.11.1: (continued)

The LP Procedure

Variable Summary
Col Variable Name Status Type Price Activity Reduced Cost
1 X1 DEGEN BINARY 0 0 0
2 X2 DEGEN BINARY 0 0 0
3 X3 DEGEN BINARY 0 0 0
4 X4   BINARY 0 1 -18
5 X5 DEGEN BINARY 0 0 0
6 X6   BINARY 0 1 -1
7 X7   INTEGER 1 0 -6.5
8 X8   INTEGER 1 0 -3.266667
9 X9   INTEGER 1 0 -1.333333
10 X10   INTEGER 1 8 -8
11 X11   INTEGER 1 0 -8.545455
12 X12 BASIC INTEGER 1 9 0
13 _OBS2_ BASIC SLACK 0 20 0
14 _OBS3_ BASIC SLACK 0 5 0
15 _OBS4_ BASIC SLACK 0 10 0
16 _OBS5_   SLACK 0 0 -1
17 _OBS6_   SLACK 0 0 -1.5
18 _OBS7_   SLACK 0 0 -0.266667
19 _OBS8_   SLACK 0 0 -0.333333
20 _OBS9_ BASIC SLACK 0 2 0
21 _OBS10_   SLACK 0 0 -2.545455
22 _OBS11_ BASIC SLACK 0 2 0

Output 3.11.1: (continued)

The LP Procedure

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


Although the VARSELECT=PENALTY strategy works well in this example, there is no guarantee that it will work well with your model. Experimentation with various strategies is necessary to find the one that works well with your model and data, particularly if a model is solved repeatedly with few changes to either the structure or the data.

Chapter Contents
Chapter Contents		 Previous
Previous		 Next
Next		 Top
Top

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