The LP Procedure

Example 4.11 Alternative Search of the Branch-and-Bound Tree

In this example, the HALDI10 problem from Example 4.10 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 data=haldi10 varselect=penalty;
run;

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

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

Integer Iteration Log
Iter Problem Condition Objective Branched Value Sinfeas Active Proximity
1 0 ACTIVE 18.709524 x4 0.8 1.11905 2 .
2 1 ACTIVE 16.585187 x1 0.447 2.33824 3 .
3 2 ACTIVE 14.86157 x5 0.221 2.09584 4 .
4 3 ACTIVE 14.807195 x2 0.897 1.31729 5 .
5 -4 ACTIVE 14.753205 x8 14.58 0.61538 6 .
6 5 ACTIVE 14.730078 x6 0.043 0.79446 7 .
7 -6 ACTIVE 13.755102 x3 0.051 0.58163 8 .
8 -7 ACTIVE 11.6 x8 11.6 0.4 9 .
9 8 ACTIVE 11.6 x12 0.6 0.4 10 .
10 -9 ACTIVE 11.6 x8 10.6 0.4 11 .
11 10 ACTIVE 11.6 x12 1.6 0.4 12 .
12 -11 ACTIVE 11.6 x8 9.6 0.4 13 .
13 12 ACTIVE 11.6 x12 2.6 0.4 14 .
14 -13 ACTIVE 11.571429 x9 0.143 0.57143 15 .
15 14 ACTIVE 11.5 x8 8.5 0.5 16 .
16 -15 INFEASIBLE 9 . . . 15 .
17 15 ACTIVE 11.375 x12 3.375 0.375 16 .
18 -17 ACTIVE 11.166667 x8 7.167 0.16667 17 .
19 18 ACTIVE 11.125 x12 4.125 0.125 18 .
20 19 SUBOPTIMAL 11 . . . 7 7
21 7 ACTIVE 13.5 x8 13.5 0.5 8 7
22 -21 INFEASIBLE 11 . . . 7 7
23 21 ACTIVE 13.375 x12 0.375 0.375 8 7
24 -23 ACTIVE 13.166667 x8 12.17 0.16667 9 7
25 24 ACTIVE 13.125 x12 1.125 0.125 10 7
26 25 SUBOPTIMAL 13 . . . 4 5
27 6 ACTIVE 14.535714 x3 0.045 0.50893 5 5
28 -27 FATHOMED 12.625 . . . 4 5
29 27 SUBOPTIMAL 14 . . . 1 4
30 -1 ACTIVE 18.309524 x3 0.129 1.31905 2 4
31 30 ACTIVE 17.67723 x6 0.886 0.43662 3 4
32 31 ACTIVE 15.485156 x2 0.777 1.50833 4 4
33 -32 ACTIVE 15.2625 x1 0.121 1.38333 4 4
34 33 ACTIVE 15.085106 x10 3.532 0.91489 4 4
35 34 FATHOMED 14.857143 . . . 3 4
36 32 FATHOMED 11.212121 . . . 2 4
37 -31 ACTIVE 17.56338 x10 7.93 0.43662 3 4
38 37 ACTIVE 17.225962 x8 2.38 0.69231 4 4
39 38 ACTIVE 17.221818 x1 0.016 0.37111 5 4
40 -39 FATHOMED 14.43662 . . . 4 4
41 39 ACTIVE 17.172375 x2 0.133 0.31948 5 4
42 41 ACTIVE 16.890196 x5 0.086 0.19608 6 4
43 42 ACTIVE 16.75 x12 9.75 0.25 7 4
44 -43 SUBOPTIMAL 15 . . . 6 3
45 43 SUBOPTIMAL 16 . . . 3 2
46 -38 FATHOMED 17.138028 . . . 2 2
47 -37 SUBOPTIMAL 17 . . . 1 1
48 -30 FATHOMED 16.566667 . . . 0 .

Solution Summary

Integer Optimal Solution
Objective Value 17
   
Phase 1 Iterations 0
Phase 2 Iterations 13
Phase 3 Iterations 79
Integer Iterations 48
Integer Solutions 6
Initial Basic Feasible Variables 12
Time Used (seconds) 0
Number of Inversions 17
   
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

Variable Summary
Col Variable Name Status Type Price Activity Reduced Cost
1 x1 DEGEN BINARY 0 0 0
2 x2   BINARY 0 0 -4
3 x3   BINARY 0 0 -4
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
9 x9   INTEGER 1 0 -1
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_ DEGEN SLACK 0 0 0
19 _OBS8_ DEGEN SLACK 0 0 0
20 _OBS9_ BASIC SLACK 0 2 0
21 _OBS10_   SLACK 0 0 -2.545455
22 _OBS11_ BASIC SLACK 0 2 0

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
8 _OBS8_ LE 19 0 0 0
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.