Assigned: Jan. 18

Due: Feb. 8 (NOte: Due date changed because class was cancelled for snow
on Jan. 25)

The BIN-PACKING PROBLEM problem is defined as follows:
You are given and a collection of N objects
with sizes S_{1} ... S_{N}. The problem is to pack these
objects into bins of size B, using as few bins as possible.

For example, suppose that N=8, that B=102, and that the
objects have the following sizes:

S_{1} = 42;
S_{2} = 40;
S_{3} = 30;
S_{4} = 31;
S_{5} = 72;
S_{6} = 70;
S_{7} = 60;
S_{8} = 61.

Then it is possible to pack these into 4 bins by packing objects 1 and 7 into bin 1; objects 2 and 8 into bin 2; objects 3 and 5 into bin 3; and objects 4 and 6 into bin 4. (Note: In this particular problem the optimal solution happens to have two full bins, and all bins containing the same number of objects, but neither of those are necessary conditions.)

Consider the following non-deterministic algorithm:

/* BIN-PACK goes through the objects in order and non-deterministically chooses a bin to put them in; either a partially filled bin or a new bin. It returns, non-deterministically, all possible assignments. */ function BIN-PACK(in N, B : integer; S[1 .. N] : array of integers --- sizes) out A[1 .. N] : array of integers --- assignments) /* Backtraking variables */ var FREE[1 .. N] : the amount of space left in each bin. P : integer --- number of processors used + 1; /* Initialization */ P := 1; FREE[P] := B; /* Main loop */ for I := 1 to N do choose processor Q in {1 .. P} such that FREE[Q] >= S[I]; A[I] := Q; FREE[Q] := FREE[Q] - S[I]; if Q = P then begin P := P+1; FREE[P] := B end; /* starting new bin */ endfor end BIN-PACK

A. Suppose that BIN-PACK is implemented using depth-first search, and that at each choice point it tests the possible values of Q in increasing order. What are the first five solutions found? (Note: this algorithm returns all consistent assignments, not just the optimal ones.)

B. Describe the state space used in this algorithm. What is a state? What is an operator? What is the start state? What is a goal state?

C. What is the maximum branching factor in this space? What is the depth of the space? Give an upper bound on the size of the space.

To express this kind of rule in the language of non-deterministic algorithms requires some new constructs that allow communication between different branches of the search tree; I am not going to go into these.

If the BIN-PACK algorithm is implemented as in problem 1 and this technique is used, what is the first state encountered where pruning takes place?

The figure shows the AND/OR tree for 3 objects being assigned to up to 3 bins:

We may now consider two different heuristics for improving the behavior of the BIN-PACK algorithm:

1. Go through the objects in decreasing order of size.

2. When deciding which bin to place the object in, try bins in
increasing order of FREE. That is, try it in the fullest bin first;
then in the next fullest, and so on.

A. Which of these corresponds to choosing an order of the children of the AND node? Which corresponds to choosing an order of the children of the OR nodes?

B. In our example, what is the effect of applying heuristic 1? Heuristic 2? Both heuristics?

C. (Extra credit) Construct an example in which, when both heuristics 1 and 2 are applied, the first solution found by BIN-PACK is not, in fact, the optimal solution.