Return to Index
Operations Research Models and Methods
Computation Section
Subunit Mathematical Programming Model Builder
 - Column List Format

The column list format shows all the model components as lists. For this format the lists are arranged as columns of worksheet cells. Rather than using a matrix, the column list for the constraint coefficients stores each coefficient with a row of a table. The advantage of this list format is that zero value coefficients need not be included in the list. The much reduced figure below illustrates the arrangements of the components on the worksheet. All components begin at the same row. Green outlined cells hold the primal solution of the model and are filled by add-in programs. Red outlined cells hold the dual solution of the model. Yellow cells hold formulas provided by the program. These should not be changed.

column list format



The variable columns start in column D. Since this arrangement is described earlier it is not repeated here.

column list variables



  The constraint columns start in column N.
constraint columns


Coefficient List


The entries in the coefficient list refer to cells in the coefficient matrix of the tableau representation. For convenience that matrix is repeated below.

coefficient matrix

The coefficients are stored in a table starting in column U and continuing until column AA. The coefficient list for the example is below. Each coefficient occupies a row of the list. Columns V and W refer to the coefficient matrix of the tableau representation. Column V holds the index of a variable (column), and column W holds the index of a constraint (row). Together they define a cell of the coefficient matrix. The first column entry (row 13) indicates that the coefficient for this row is the coefficient for variable 1 (X_01) in constraint 1 (A_1). The names of the variable and constraint are concatenated in column X (X_01-A_1) to help identify the combination. The value (10) of the coefficient is in column Y. This particular model has 50 constraint coefficients, so the list has 50 entries. Reading down the table, you can see that the first column of the coefficient matrix is the first five entries in the table. During the solution process this list is always sorted with column V the primary sorting index and column W the secondary sorting index.

coefficient columns

The last two columns, Z and AA, are computed with formulas. Column Z uses an INDEX function to recover the value of the variable for each row of the table. Since the first five entries are for X_01, column Z reports 0 for the value of that variable. This is obtained from column D of the variable table shown at the top of this page. Column AA holds the product of column Y and column Z. For each row, this is the contribution of the term to the constraint equation.

The constraint value shown as column Q in the constraint display is the sum of all cells with a specified constraint index. For example the value of P13 is the sum of cells AA13, AA18, AA23, and so on through the coefficient list. Column Q uses the SUMIF Excel function to compute the constraint values.

constraint columns

The constraint list display is certainly not the most efficient for a dense coefficient matrix as the one used for this random example. Its benefit is realized for sparse coefficient matrices where the number of nonzero coefficients is much fewer than the number of cells of the matrix.

This list will also be useful for automatically generated models that use computer programs to specify the coefficients of the model. I hope to create an add-in that will automatically generate large linear/integer programs much like the dynamic programming model generator described elsewhere on this site.

Return to Top

tree roots

Operations Research Models and Methods
by Paul A. Jensen
Copyright 2004 - All rights reserved