The LP Procedure

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