The LP Procedure

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

In this example, the HALDI10 problem from Example 6.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 6.10. In this example, the difference is profound; in general, solution times can vary significantly with the search technique. See Output 6.11.1.

Output 6.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.5	x9	0.5	0.5	13	.
13	-12	ACTIVE	11.4	x8	9.4	0.4	14	.
14	13	ACTIVE	11.333333	x9	1.333	0.33333	15	.
15	-14	ACTIVE	11.2	x8	8.2	0.2	16	.
16	15	ACTIVE	11.166667	x9	2.167	0.16667	17	.
17	-16	SUBOPTIMAL	11	.	.	.	7	7
18	7	ACTIVE	13.5	x8	13.5	0.5	8	7
19	-18	INFEASIBLE	11	.	.	.	7	7
20	18	ACTIVE	13.375	x12	0.375	0.375	8	7
21	-20	ACTIVE	13.166667	x8	12.17	0.16667	9	7
22	21	ACTIVE	13.125	x12	1.125	0.125	10	7
23	22	SUBOPTIMAL	13	.	.	.	4	5
24	6	ACTIVE	14.535714	x3	0.045	0.50893	5	5
25	-24	FATHOMED	12.625	.	.	.	4	5
26	24	SUBOPTIMAL	14	.	.	.	1	4
27	-1	ACTIVE	18.309524	x3	0.129	1.31905	2	4
28	27	ACTIVE	17.67723	x6	0.886	0.43662	3	4
29	28	ACTIVE	15.485156	x2	0.777	1.50833	4	4
30	-29	ACTIVE	15.2625	x1	0.121	1.38333	4	4
31	30	ACTIVE	15.085106	x10	3.532	0.91489	4	4
32	31	FATHOMED	14.857143	.	.	.	3	4
33	29	FATHOMED	11.212121	.	.	.	2	4
34	-28	ACTIVE	17.56338	x10	7.93	0.43662	3	4
35	34	ACTIVE	17.225962	x8	2.38	0.69231	4	4
36	35	ACTIVE	17.221818	x1	0.016	0.37111	5	4
37	-36	FATHOMED	14.43662	.	.	.	4	4
38	36	ACTIVE	17.172375	x2	0.133	0.31948	5	4
39	38	ACTIVE	16.890196	x5	0.086	0.19608	6	4
40	39	ACTIVE	16.75	x12	9.75	0.25	7	4
41	-40	SUBOPTIMAL	15	.	.	.	6	3
42	40	SUBOPTIMAL	16	.	.	.	3	2
43	-35	FATHOMED	17.138028	.	.	.	2	2
44	-34	SUBOPTIMAL	17	.	.	.	1	1
45	-27	FATHOMED	16.566667	.	.	.	0	.

Solution Summary
Integer Optimal Solution
Objective Value	17

Phase 1 Iterations	0
Phase 2 Iterations	13
Phase 3 Iterations	74
Integer Iterations	45
Integer Solutions	6
Initial Basic Feasible Variables	12
Time Used (seconds)	0
Number of Inversions	16

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.