Knapsack constraint reformulation: A new approach that significantly reduces the number of sub-problems in the branch and bound algorithm

Figures & data

Table 1. Complexity of the problem as n value increases

Value of n in the model	Number of sub-problems created by the standard branch and bound approach to reach the optimum solution
4	11
6	39
8	139
16	25,739
40	Computer was stopped after the sub-problems exceeded 30,000

Table 2. Complexity of the problem as n value increases

Value of n in the model	Number of sub-problems created by the branch and bound approach to reach the optimum
4	$\mathit{\kappa }=3$, Sub-problems =17
6	$\mathit{\kappa }=3,$ Sub-problems =59
	$\mathit{\kappa }=5,$ Sub-problems =59
8	$\mathit{\kappa }=3,$ Sub-problems =209
	$\mathit{\kappa }=5,$ Sub-problems =209
	$\mathit{\kappa }=7,$ Sub-problems =209
16	Computer was stopped after the number of sub-problems exceeded 30,000.

Table 3. Complexity of the problem as n value increases

Value of n in the model	Number of sub-problems created by the branch and bound approach to reach the optimum solution
4	$\mathit{\kappa }=3,$ Sub-problems =23
6	$\mathit{\kappa }=3,$ Sub-problems =129
	$\mathit{\kappa }=5,$ Sub-problems =129
8	$\mathit{\kappa }=3,$ Sub-problems =755
	$\mathit{\kappa }=5,$ Sub-problems =755
	$\mathit{\kappa }=7,$ Sub-problems =755
16	Computer was stopped when the number of sub-problems exceeded 30,000

Table 4. Computational experiments on randomly generated Knapsack problems

KLIP S No.	No. of Variables	No. of sub-problems before	No. of sub problems after	% Reduction in sub-problems
1	5	25	4	84.0
2	10	41	7	82.9
3	20	158	29	81.6
4	30	132	12	90.9
5	40	89	9	80.0
6	50	*	32	–
7	60	289	18	93.7
8	70	6590	47	99.3
9	80	2198	29	98.7
10	90	1789	15	99.2
11	100	691	106	84.7
12	150	11209	89	99.2
13	200	721	19	97.4
14	250	*	51	–
15	300	2187	71	96.8
16	350	6842	29	99.6
17	400	895	67	92.5
18	450	17866	27	99.8
19	500	*	105	–
20	550	96	11	88.5
21	600	14	3	78.6
22	650	871	69	92.1
23	700	956	17	98.2
24	750	4008	189	95.3
25	800	38	2	94.7
26	850	2983	63	97.9
27	900	345	22	93.6
28	950	27689	58	99.8
29	1000	116	26	77.6
30	1500	19	4	78.9
31	2000	4578	23	99.5
32	2500	89	13	85.4
33	3000	8104	269	96.7
34	3500	978	47	95.2
35	4000	67	15	77.6
36	4500	*	44	–
37	5000	24672	56	99.8
38	6000	*	391	–
39	6500	897	35	96.1
40	7000	1946	219	88.7

*Number of sub-problems exceeded 30,000.

Table 5. More computational experiments on randomly generated Knapsack problems

KLIP S No.	No. of variables	No. of sub-problems before	No. of sub problems after	% Reduction in sub-problems
41	7500	*	456	–
42	8000	15008	375	97.5
43	8500	6895	132	98.1
44	9000	*	249	–
45	9500	1193	83	93.1
46	10000	5829	683	88.3
47	10500	*	43	–
48	12000	*	102	–
49	13000	28972	219	99.2
50	15000	*	147	–

*Number of sub-problems exceeded 30,000.