Artificial Intelligence: Problem Set 1

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 S1 ... SN. 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:
S1 = 42; S2 = 40; S3 = 30; S4 = 31; S5 = 72; S6 = 70; S7 = 60; S8 = 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.)

Problem 1

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 */

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.

Problem 2

A useful general technique in searches for optimal solutions to this kind of problem is called ``branch and bound''. It says that, if you can be sure that your current path in the space cannot possibly lead to a better solution than one you have already found, then you can abandon the current path. In the BIN-PACKING problem, this is interpreted as follows: If you have already found a solution that uses K bins, and your current partial assignment uses K bins, then there is no need to pursue this branch of the state space any further, because it cannot lead to a solution better than the one you already have found.

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?

Problem 3:

The bin-packing problem can be viewed as a constrained AND/OR tree. It is a three-level tree, where the root is an AND node, the second level nodes are OR nodes, and the third level nodes are leaves. The leaves of the tree are assignments of objects to bins; e.g. ``Object 3 goes in bin 2''. The OR nodes correspond to objects: each object can either go in bin 1, or in bin 2 ... or in bin N. The constraint is that no bin contains more than its capacity.

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.

Back to course home page