Intentional Circular References

Over a lunchtime pastie, I was recently browsing my copy of Walkenbach’s Formulas. I found myself looking at the chapter on Intentional Circular References.

Here, JW gives an example of choosing a set of unique random numbers – that is, having chosen a number once, it can not be chosen again. Each random number has an associated COUNTIF formula, which counts occurrences of the associated number; if this is 1 for each number, then we have a solution. In a random-number cell (e.g. A1), we have a formula of the form:

=IF(<no solution>, <new number using RAND>, A1)

These formulas generate candidate solutions at random, until one is found. In >Tools >Options >Calculation (v2003), you need to allow Iteration, and set a sufficient number of Maximum Iterations.

I thought I’d try my own example: allocating resources to a set of tasks (with pre-determined start and finish dates). Here’s the worksheet:

  • The task durations are set out with 1 values, in C6:J9 – each column represents a day, with time increasing from left to right
  • The allocated resources are identified in A6:A9 (range Alloc)
  • The pool of  available resources is in A12:A14 (range Resource)
  • The resource utilization per-day is calculated in C12:J14, using an array formula (see below), plus some conditional formatting
  • The maximum utilization for a resource is calculated in B12:B14 (range Max)
  • The maximum of the maxima is calculated in B16 (range Supermax). If this is 1 – that is, no resource is multi-booked for any day – then we have a solution.

The resource utilization in C12, etc, is calculated using the array formula:

{=SUM(($A12=Alloc)*C$6:C$9)}

That is, the ones in C6:C9 are summed only if the resource in the corresponding row of Alloc matches the one in A12. You can see how the allocations of res2 (in rows 6 and 8 ) are unioned in row 13.

The random-allocation formula in A6 is:

=IF(SuperMax<>1, NewResource, A6)

The reference to Supermax is what creates the circularity.

NewResource is a named formula:

=INDEX(Resource, INT(RAND()*Rescount) + 1)

This generates a random index into the Resource list, whose size is Rescount.

Having found a solution, recalculation just keeps preserving the existing values. To force a new solution, you first have to ‘break’ the existing solution. This is done using the named value Started, in A2. Each of the green cells in C6:J9 has the formula ‘=Started’. Setting Started to zero makes the allocation fail to find a solution (since Supermax can never = 1), leaving Alloc with an arbitrary set of resource ids. Then setting Started = 1 allows a new solution to be found.

I’m not sure how useful this technique would be for realistically sized problems, since it’s basically trying solutions at random. Anyway, here’s the workbook, if you fancy a play.

About these ads

2 Responses to “Intentional Circular References”


  1. 1 Alan August 30, 2010 at 4:07 pm

    Thanks for the post. Cool technique.

    Just curious, on C12, why did you choose an array formula rather than:
    SUMIF(Alloc,$A12,C$6:C$9)

    It may just be personal preference.

  2. 2 Roy MacLean August 30, 2010 at 4:24 pm

    Alan,
    Yes, SUMIF would do it. I guess I was thinking in array terms, and that just seemed natural. Although irrelevant in this case, the array formula is a more general technique in that you can use functions other than SUM.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




August 2010
M T W T F S S
« Jul   Sep »
 1
2345678
9101112131415
16171819202122
23242526272829
3031  

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: