Tuesday, May 3, 2011

Large (almost) triangular spreadsheet?

A spreadsheet model without circular references can be called “triangular”. Excel can form a dependency graph and ordering such that recalculation can be done in one iteration. If there are circular references the spreadsheet needs to perform more iterations before the results converge.

I was given a very large spreadsheet implementing an agricultural country trade model. The question was how near triangular is this? With the Excel tool to find circular references, we only find a single case:

circular

Luckily I have a tool that takes an Excel spreadsheet and parses Excel formulas and produces a GAMS representation of this. Essentially each cell forms an equation:

image

The whole spreadsheet can be viewed as a fixed point expression:

image

This is of course just a system of nonlinear equations:

image

When we solve this spreadsheet model as an NLP with Conopt we get some statistics:

---   67,618 rows  68,707 columns  232,364 non-zeroes
---   776,017 nl-code  103,528 nl-non-zeroes

   Iter Phase Ninf   Infeasibility   RGmax    NSB   Step InItr MX OK
      0   0        7.3221660778E-07 (Input point)
                                Pre-triangular equations:    22507
                                Post-triangular equations:   13897
      1   0        1.2425686171E-07 (After pre-processing)
      2   0        3.4325009848E-11 (After scaling)

Graphically, after reordering rows and columns, we have:

triangular

This certainly gives an indication we are not close to a triangular model and we need a simultaneous equation solver to handle this type of model.