On 3/1/00 at 10:09 PM, GlenNaekel@cs.com wrote:

> Hello Professor Spingarn,
>

> I noted the "pseudo-code" which you generated for the good-basis heuristic.
> Do you have anything similar, or a good algorithm for solving the knapsack
> problems? I find that it's easy to sometimes skip possibile solutions when
> using the enumeration trees. It can be rather tedious.
>
> Thank you.
>
> Glen Naekel.

When you are solving a cutting stock problem, the tree you draw for each knapsack problem is exactly the same. For example, for the problem in exercise #20, the possibilities at each iteration are:
(3 0 0 0)
(2 1 0 1)
(2 0 2 0)
(2 0 1 1)
(2 0 0 2)
(1 2 1 0)
(1 2 0 1)
(1 1 2 0)
(1 1 1 1)
(1 1 0 2)
(1 0 3 0)
(1 0 2 1)
(1 0 1 3)
(1 0 0 4)
(0 4 0 0)
(0 3 1 0)
(0 3 0 1)
(0 2 2 0)
(0 2 1 1)
(0 2 0 3)
(0 1 3 0)
(0 1 2 1)
(0 1 1 3)
(0 1 0 4)
(0 0 4 0)
(0 0 3 2)
(0 0 2 3)
(0 0 1 4)
(0 0 0 6)
The only thing that changes is the objective function, eg 7/24 a1 + 1/4 a2 + 5/24 a3 + 1/6 a4, which should be evaluated at each of the possibilities (unless you are using the branch and bound proceedure to cut off branches -- hardly worth the trouble). You can easily write a small computer program that inputs the objective (say, 7/24,1/4,5/24,1/6) and outputs its value at each possibility. Really, you don't even need to write a program. If you have a spreadsheet, it could easily handle such a calculation: enter all the possible patterns and the objective. Then change the objective at each iteration.



actually, I take that back about it not being worth the trouble to
do the branch and bound cut off. There can be a very large number
of possibilities if you look at all of them. Here they are for the
three cutting stock problems of exercise 22. They are tab delimited
so you can paste them into a spreadsheet. The third one has only a
few possibilities. :

? (knapsack 90 #(60 30 51/2 20 69/4 15 51/4 10))

1 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0
1 0 0 1 0 0 0 1
1 0 0 0 1 0 1 0
1 0 0 0 1 0 0 1
1 0 0 0 0 2 0 0
1 0 0 0 0 1 1 0
1 0 0 0 0 1 0 1
1 0 0 0 0 0 2 0
1 0 0 0 0 0 1 1
1 0 0 0 0 0 0 3
0 3 0 0 0 0 0 0
0 2 1 0 0 0 0 0
0 2 0 1 0 0 0 1
0 2 0 0 1 0 1 0
0 2 0 0 1 0 0 1
0 2 0 0 0 2 0 0
0 2 0 0 0 1 1 0
0 2 0 0 0 1 0 1
0 2 0 0 0 0 2 0
0 2 0 0 0 0 1 1
0 2 0 0 0 0 0 3
0 1 2 0 0 0 0 0
0 1 1 1 0 0 1 0
0 1 1 1 0 0 0 1
0 1 1 0 2 0 0 0
0 1 1 0 1 1 0 0
0 1 1 0 1 0 1 0
0 1 1 0 1 0 0 1
0 1 1 0 0 2 0 0
0 1 1 0 0 1 1 0
0 1 1 0 0 1 0 1
0 1 1 0 0 0 2 0
0 1 1 0 0 0 1 2
0 1 1 0 0 0 0 3
0 1 0 3 0 0 0 0
0 1 0 2 1 0 0 0
0 1 0 2 0 1 0 0
0 1 0 2 0 0 1 0
0 1 0 2 0 0 0 2
0 1 0 1 2 0 0 0
0 1 0 1 1 1 0 0
0 1 0 1 1 0 1 1
0 1 0 1 1 0 0 2
0 1 0 1 0 2 0 1
0 1 0 1 0 1 1 1
0 1 0 1 0 1 0 2
0 1 0 1 0 0 3 0
0 1 0 1 0 0 2 1
0 1 0 1 0 0 1 2
0 1 0 1 0 0 0 4
0 1 0 0 3 0 0 0
0 1 0 0 2 1 0 1
0 1 0 0 2 0 2 0
0 1 0 0 2 0 1 1
0 1 0 0 2 0 0 2
0 1 0 0 1 2 1 0
0 1 0 0 1 2 0 1
0 1 0 0 1 1 2 0
0 1 0 0 1 1 1 1
0 1 0 0 1 1 0 2
0 1 0 0 1 0 3 0
0 1 0 0 1 0 2 1
0 1 0 0 1 0 1 3
0 1 0 0 1 0 0 4
0 1 0 0 0 4 0 0
0 1 0 0 0 3 1 0
0 1 0 0 0 3 0 1
0 1 0 0 0 2 2 0
0 1 0 0 0 2 1 1
0 1 0 0 0 2 0 3
0 1 0 0 0 1 3 0
0 1 0 0 0 1 2 1
0 1 0 0 0 1 1 3
0 1 0 0 0 1 0 4
0 1 0 0 0 0 4 0
0 1 0 0 0 0 3 2
0 1 0 0 0 0 2 3
0 1 0 0 0 0 1 4
0 1 0 0 0 0 0 6
0 0 3 0 0 0 1 0
0 0 3 0 0 0 0 1
0 0 2 1 1 0 0 0
0 0 2 1 0 1 0 0
0 0 2 1 0 0 1 0
0 0 2 1 0 0 0 1
0 0 2 0 2 0 0 0
0 0 2 0 1 1 0 0
0 0 2 0 1 0 1 0
0 0 2 0 1 0 0 2
0 0 2 0 0 2 0 0
0 0 2 0 0 1 1 1
0 0 2 0 0 1 0 2
0 0 2 0 0 0 3 0
0 0 2 0 0 0 2 1
0 0 2 0 0 0 1 2
0 0 2 0 0 0 0 3
0 0 1 3 0 0 0 0
0 0 1 2 1 0 0 0
0 0 1 2 0 1 0 0
0 0 1 2 0 0 1 1
0 0 1 2 0 0 0 2
0 0 1 1 2 0 0 1
0 0 1 1 1 1 0 1
0 0 1 1 1 0 2 0
0 0 1 1 1 0 1 1
0 0 1 1 1 0 0 2
0 0 1 1 0 2 1 0
0 0 1 1 0 2 0 1
0 0 1 1 0 1 2 0
0 0 1 1 0 1 1 1
0 0 1 1 0 1 0 2
0 0 1 1 0 0 3 0
0 0 1 1 0 0 2 1
0 0 1 1 0 0 1 3
0 0 1 1 0 0 0 4
0 0 1 0 3 0 1 0
0 0 1 0 3 0 0 1
0 0 1 0 2 2 0 0
0 0 1 0 2 1 1 0
0 0 1 0 2 1 0 1
0 0 1 0 2 0 2 0
0 0 1 0 2 0 1 1
0 0 1 0 2 0 0 3
0 0 1 0 1 3 0 0
0 0 1 0 1 2 1 0
0 0 1 0 1 2 0 1
0 0 1 0 1 1 2 0
0 0 1 0 1 1 1 1
0 0 1 0 1 1 0 3
0 0 1 0 1 0 3 0
0 0 1 0 1 0 2 2
0 0 1 0 1 0 1 3
0 0 1 0 1 0 0 4
0 0 1 0 0 4 0 0
0 0 1 0 0 3 1 0
0 0 1 0 0 3 0 1
0 0 1 0 0 2 2 0
0 0 1 0 0 2 1 2
0 0 1 0 0 2 0 3
0 0 1 0 0 1 3 1
0 0 1 0 0 1 2 2
0 0 1 0 0 1 1 3
0 0 1 0 0 1 0 4
0 0 1 0 0 0 5 0
0 0 1 0 0 0 4 1
0 0 1 0 0 0 3 2
0 0 1 0 0 0 2 3
0 0 1 0 0 0 1 5
0 0 1 0 0 0 0 6
0 0 0 4 0 0 0 1
0 0 0 3 1 0 1 0
0 0 0 3 1 0 0 1
0 0 0 3 0 2 0 0
0 0 0 3 0 1 1 0
0 0 0 3 0 1 0 1
0 0 0 3 0 0 2 0
0 0 0 3 0 0 1 1
0 0 0 3 0 0 0 3
0 0 0 2 2 1 0 0
0 0 0 2 2 0 1 0
0 0 0 2 2 0 0 1
0 0 0 2 1 2 0 0
0 0 0 2 1 1 1 0
0 0 0 2 1 1 0 1
0 0 0 2 1 0 2 0
0 0 0 2 1 0 1 2
0 0 0 2 1 0 0 3
0 0 0 2 0 3 0 0
0 0 0 2 0 2 1 0
0 0 0 2 0 2 0 2
0 0 0 2 0 1 2 0
0 0 0 2 0 1 1 2
0 0 0 2 0 1 0 3
0 0 0 2 0 0 3 1
0 0 0 2 0 0 2 2
0 0 0 2 0 0 1 3
0 0 0 2 0 0 0 5
0 0 0 1 4 0 0 0
0 0 0 1 3 1 0 0
0 0 0 1 3 0 1 0
0 0 0 1 3 0 0 1
0 0 0 1 2 2 0 0
0 0 0 1 2 1 1 0
0 0 0 1 2 1 0 2
0 0 0 1 2 0 2 1
0 0 0 1 2 0 1 2
0 0 0 1 2 0 0 3
0 0 0 1 1 3 0 0
0 0 0 1 1 2 1 1
0 0 0 1 1 2 0 2
0 0 0 1 1 1 2 1
0 0 0 1 1 1 1 2
0 0 0 1 1 1 0 3
0 0 0 1 1 0 4 0
0 0 0 1 1 0 3 1
0 0 0 1 1 0 2 2
0 0 0 1 1 0 1 4
0 0 0 1 1 0 0 5
0 0 0 1 0 4 0 1
0 0 0 1 0 3 1 1
0 0 0 1 0 3 0 2
0 0 0 1 0 2 3 0
0 0 0 1 0 2 2 1
0 0 0 1 0 2 1 2
0 0 0 1 0 2 0 4
0 0 0 1 0 1 4 0
0 0 0 1 0 1 3 1
0 0 0 1 0 1 2 2
0 0 0 1 0 1 1 4
0 0 0 1 0 1 0 5
0 0 0 1 0 0 5 0
0 0 0 1 0 0 4 1
0 0 0 1 0 0 3 3
0 0 0 1 0 0 2 4
0 0 0 1 0 0 1 5
0 0 0 1 0 0 0 7
0 0 0 0 5 0 0 0
0 0 0 0 4 1 0 0
0 0 0 0 4 0 1 0
0 0 0 0 4 0 0 2
0 0 0 0 3 2 0 0
0 0 0 0 3 1 1 1
0 0 0 0 3 1 0 2
0 0 0 0 3 0 3 0
0 0 0 0 3 0 2 1
0 0 0 0 3 0 1 2
0 0 0 0 3 0 0 3
0 0 0 0 2 3 0 1
0 0 0 0 2 2 2 0
0 0 0 0 2 2 1 1
0 0 0 0 2 2 0 2
0 0 0 0 2 1 3 0
0 0 0 0 2 1 2 1
0 0 0 0 2 1 1 2
0 0 0 0 2 1 0 4
0 0 0 0 2 0 4 0
0 0 0 0 2 0 3 1
0 0 0 0 2 0 2 3
0 0 0 0 2 0 1 4
0 0 0 0 2 0 0 5
0 0 0 0 1 4 1 0
0 0 0 0 1 4 0 1
0 0 0 0 1 3 2 0
0 0 0 0 1 3 1 1
0 0 0 0 1 3 0 2
0 0 0 0 1 2 3 0
0 0 0 0 1 2 2 1
0 0 0 0 1 2 1 3
0 0 0 0 1 2 0 4
0 0 0 0 1 1 4 0
0 0 0 0 1 1 3 1
0 0 0 0 1 1 2 3
0 0 0 0 1 1 1 4
0 0 0 0 1 1 0 5
0 0 0 0 1 0 5 0
0 0 0 0 1 0 4 2
0 0 0 0 1 0 3 3
0 0 0 0 1 0 2 4
0 0 0 0 1 0 1 6
0 0 0 0 1 0 0 7
0 0 0 0 0 6 0 0
0 0 0 0 0 5 1 0
0 0 0 0 0 5 0 1
0 0 0 0 0 4 2 0
0 0 0 0 0 4 1 1
0 0 0 0 0 4 0 3
0 0 0 0 0 3 3 0
0 0 0 0 0 3 2 1
0 0 0 0 0 3 1 3
0 0 0 0 0 3 0 4
0 0 0 0 0 2 4 0
0 0 0 0 0 2 3 2
0 0 0 0 0 2 2 3
0 0 0 0 0 2 1 4
0 0 0 0 0 2 0 6
0 0 0 0 0 1 5 1
0 0 0 0 0 1 4 2
0 0 0 0 0 1 3 3
0 0 0 0 0 1 2 4
0 0 0 0 0 1 1 6
0 0 0 0 0 1 0 7
0 0 0 0 0 0 7 0
0 0 0 0 0 0 6 1
0 0 0 0 0 0 5 2
0 0 0 0 0 0 4 3
0 0 0 0 0 0 3 5
0 0 0 0 0 0 2 6
0 0 0 0 0 0 1 7
0 0 0 0 0 0 0 9

? (knapsack 181 #(21.625 20.5 20.0 17.25))

8 0 0 0
7 1 0 0
7 0 1 0
7 0 0 1
6 2 0 0
6 1 1 0
6 1 0 1
6 0 2 0
6 0 1 1
6 0 0 2
5 3 0 0
5 2 1 0
5 2 0 1
5 1 2 0
5 1 1 1
5 1 0 3
5 0 3 0
5 0 2 1
5 0 1 3
5 0 0 4
4 4 0 0
4 3 1 0
4 3 0 1
4 2 2 0
4 2 1 1
4 2 0 3
4 1 3 0
4 1 2 1
4 1 1 3
4 1 0 4
4 0 4 0
4 0 3 2
4 0 2 3
4 0 1 4
4 0 0 5
3 5 0 0
3 4 1 0
3 4 0 1
3 3 2 0
3 3 1 2
3 3 0 3
3 2 3 0
3 2 2 2
3 2 1 3
3 2 0 4
3 1 4 0
3 1 3 2
3 1 2 3
3 1 1 4
3 1 0 5
3 0 5 0
3 0 4 2
3 0 3 3
3 0 2 4
3 0 1 5
3 0 0 6
2 6 0 0
2 5 1 0
2 5 0 2
2 4 2 0
2 4 1 2
2 4 0 3
2 3 3 0
2 3 2 2
2 3 1 3
2 3 0 4
2 2 4 0
2 2 3 2
2 2 2 3
2 2 1 4
2 2 0 5
2 1 5 1
2 1 4 2
2 1 3 3
2 1 2 4
2 1 1 5
2 1 0 6
2 0 6 1
2 0 5 2
2 0 4 3
2 0 3 4
2 0 2 5
2 0 1 6
2 0 0 7
1 7 0 0
1 6 1 0
1 6 0 2
1 5 2 0
1 5 1 2
1 5 0 3
1 4 3 1
1 4 2 2
1 4 1 3
1 4 0 4
1 3 4 1
1 3 3 2
1 3 2 3
1 3 1 4
1 3 0 5
1 2 5 1
1 2 4 2
1 2 3 3
1 2 2 4
1 2 1 5
1 2 0 6
1 1 6 1
1 1 5 2
1 1 4 3
1 1 3 4
1 1 2 5
1 1 1 6
1 1 0 8
1 0 7 1
1 0 6 2
1 0 5 3
1 0 4 4
1 0 3 5
1 0 2 6
1 0 1 8
1 0 0 9
0 8 0 0
0 7 1 1
0 7 0 2
0 6 2 1
0 6 1 2
0 6 0 3
0 5 3 1
0 5 2 2
0 5 1 3
0 5 0 4
0 4 4 1
0 4 3 2
0 4 2 3
0 4 1 4
0 4 0 5
0 3 5 1
0 3 4 2
0 3 3 3
0 3 2 4
0 3 1 5
0 3 0 6
0 2 7 0
0 2 6 1
0 2 5 2
0 2 4 3
0 2 3 4
0 2 2 5
0 2 1 6
0 2 0 8
0 1 8 0
0 1 7 1
0 1 6 2
0 1 5 3
0 1 4 4
0 1 3 5
0 1 2 6
0 1 1 8
0 1 0 9
0 0 9 0
0 0 8 1
0 0 7 2
0 0 6 3
0 0 5 4
0 0 4 5
0 0 3 7
0 0 2 8
0 0 1 9
0 0 0 10


? knapsack 100 #(52 29 27 21)

1 1 0 0
1 0 1 1
1 0 0 2
0 3 0 0
0 2 1 0
0 2 0 2
0 1 2 0
0 1 1 2
0 1 0 3
0 0 3 0
0 0 2 2
0 0 1 3
0 0 0 4