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

The general linear programming model has a linear objective function, linear constraints and lower and upper bounds for the variables. The model has n variables and m constraints. Since the expressions for the objective function and constraints are linear, the model is completely described by the coefficients of the objective, the coefficients of the constraints, bounds for constraints, and lower and upper bounds for the variables. The formats available with the MP model builder differ on how this information is stored.


This page shows the model formats available with this add-in. The add-in only creates math Programming models for LP and IP. The tableau format is similar to the LP model created by the Math Programming add-in. The others are new. The following pages expand on the different formats.


Building a Model

New model dialog

To create a new model choose the Linear/Integer command from the ORMM menu.

The menu has three additional commands. The worksheet holds buttons to call various add-in procedures. These buttons are linked to the computer that creates a model, and a link error is generated when the worksheet is opened on a different computer. Choose the Add Buttons command to erase the buttons and create new ones. When you expect the worksheet to be used on someone else computer, choose the Remove Buttons command before saving. The About Add-in gives the release date of the version of the add-in that you are using. Make sure you are using the latest release. The latest release date is on the Excel page for this add-in.

format dialog

The Choose Format dialog lists the formats are available and provides a field for specifying the problem name. The name entry is used to provide Excel names to many ranges on the worksheet. The name must satisfy Excel's restrictions for naming ranges, that is: the names must not contain spaces, they must start with a letter and they may not include punctuation marks. If an error occurs when this dialog closes, try a different name for the problem. The program automatically suggests names like LP_1, LP_2 and so on. The user may prefer a more descriptive name. Once it is specified the name cannot be changed.

We choose the Tableau option with the name LP_1.

model dialog

The LP/IP Model dialog appears after the Choose Format dialog is dismissed. The dialog accepts the dimensions of the model as well as data regarding the direction and measure for the objective, the integer variables, the Solver selection, and the choice for the Sensitivity Analysis when the problem is solved.

The Random Data button fills the model with random values. The Random Number Seed determines the values assigned, so the same problem can be assigned to different formats. The Mac and Windows versions of Excel give different models for the same seed.

The entry in the Coefficients section indicates the number of coefficients to be entered. For the tableau format, coefficients are specified for all rows and columns, so the number of coefficients is automatically specified as the product of the number of variables and the number of constraints.

The checkboxes for upper and lower limits specify whether vectors are provided to hold these limits. If unspecified, lower limits are zero and upper limits are large numbers. Checking the Variable Type box includes an array that specifies whether each variable is Real or Integer. If integer variables are included in the model definition, this array is included automatically. When checked the Dual Solution checkbox creates arrays for the dual solution in both the variables and constraints regions of the worksheet.

All of these entries except the name and the feature choices can be changed with the Change button after the worksheet is constructed.

In the examples of this section the figures show the dual variables associated with the solutions. These results are interesting from a theoretical viewpoint and often have relevance in practical problems. For those interested in only the solution of the linear or integer model, it is not necessary to view or understand the dual variables.


Parameters and Buttons


Dismiss the dialog with an OK indication and the program builds a worksheet holding one of the formats described on this page. The formats all place buttons and parameters at the top of the worksheet. None of the values in this section are under direct control of the user and they should not be changed. The upper left corner holds the model name prefixed with the label "List Model". The yellow range in column A shows data used by the Jensen LP/IP Solver when that solver is active. It can be changed by selecting the LP/IP Solver item on the ORMM menu. When the Excel Solver add-in is active, the Excel Solver model is stored in this range. The range in column F describes model parameters. Column I holds information controlling the solver. Column L has solver output results. Column O is constructed when the the dual solution is displayed on the worksheet.

Cell F4 is important because it holds the objective function for the model while F3 holds the direction of optimization (Max or Min). Some of these entries in columns F and I can be changed by clicking the Change button.

  The Change button opens the model dialog to change the size and other features of the model. The Solve button calls the selected solver. The Equation button rewrites the equations of the model. This is generally unnecessary but can be used to fix errors. The Change Relation button changes constraint relations (<=, >=, =). It is only effective if the selected range is on one or more relation cells.


The Tableau Format


The formats differ on how the components of the model are arranged on the worksheet. For the tableau format the variable information is arranged in rows at the top of the worksheet. The constraint information is arranged by columns at the left side of the worksheet. The constraint coefficients are stored in a matrix lying below the variables and to the right of the constraints.

small tableau

The variable data is arranged by row. Row 10 holds variable names and rows 12 through 15 hold the type, lower bound, upper bound and objective coefficient terms. Row 11 holds the primal solution to the problem and is filled by the Jensen LP/IP Solver add-in or the Excel Solver add-in. We indicate with the green outlines the cells that are filled in by the solver. The numbers in rows 16 and 17 are the dual variables for the lower and upper bounds. In LP theory discussions they are called the Reduced Costs for the variables. For maximization problem the reduced costs are negative for variables at their lower bounds and positive for variables at their upper bounds. The dual values are computed by the add-in and surrounded by red outlines.

The constraint information: name, dual values, value, relation and bound are described in columns E, F, G, H and I respectively. The dual variables for constraints are usually called the shadow prices. It is filled by the Jensen LP/IP Solver add-in. The constraint data is arranged by columns.

The constraint coefficients are stored in a matrix with rows representing constraints and columns representing variables. This is an efficient representation when the constraint matrix is dense (most coefficients are not equal to zero). In many practical instances, constraint matrices are sparse where most coefficients are zero. The sample problem is small, but practical problems may have many hundreds (or thousands) of variables and many hundreds of constraints. Although the solution of very large problems is beyond our add-ins, it is not unlikely that problems may have a few hundreds of variables and several dozens of constraints. Then the matrix format is very inconvenient. The matrix is a vast expanse on the worksheet and the user may have a tough time entering and checking the data for even moderately sized problems.

Older versions of Excel are limited to 256 columns. Since the variables are arranged by columns, this automatically limits the model size to about 250 variables. This limitation is not so great for Excel 2007 and later versions because these allow many more columns.


The Dual Tableau Format

  The dual tableau format is the transpose of the tableau format. Here constraints have the row orientation while variables have the column orientation. The constraint coefficient matrix as also transposed. For most problems, the number of variables is much greater than the number of constraints. When models are limited to 256 columns, the dual tableau representation is preferred for problems with more than 250 variables.
dual format tableau

It is important to observe that this format represents the primal LP model and not the dual LP model. It is simply a reorganization of the primal data.


The Column List Format


The list format replaces the constraint coefficient matrix with a list. This format has the variables and constraints in arranged in columns. The constraint coefficients are stored in columns U through AA. Each coefficient has: index, column number, row number, name, coefficient value, the value of the variable associated with the column index, and the product of the coefficient variable and the coefficient value.

Several columns are yellow indicating that they contain formulas. The coefficient name, column X, is computed using a formula that combines column and row names. The coefficient variable, column Z, is computed by referencing the appropriate cell in the solution, column J. The coefficient value, column AA, is the product of the values in column Y and column Z. The numbers in the constraint value, column Q, are computed by summing the appropriate entries in column AA. The Excel function SUMIF is used for this calculation.

The advantage of this format is that it uses a fixed number of columns, independent of the problem size. The problem size is reflected in the number of rows used. The number of rows is very large for the current versions of Excel (more than 1,000,000).

column list format

The list format is much more efficient than the matrix for storing sparse constraint sets. It is unnecessary to store 0's in the list. This example doesn't illustrate this efficiency since the number of coefficients is the product of the numbers of variables and constraints. I expect that programs that automatically generate the data for the model will take advantage of the list structure. I plan to create an add-in that will automatically generate LP data in a manner to the DP Data add-in.

The current version of the LP/IP solver requires that the coefficient list be sorted by column order. The sorting is automatically accomplished when the Solve button is pressed.


The Row List Format

  The row list format is the transpose of the column list format. All data is described by rows. The figure below shows part of the coefficient list since the full list of 50 columns would be difficult to display. For some problems the row list format may be convenient. The number of columns allowed by Excel may limit the use of this format since the number of nonzero coefficients will always exceed the number of constraints.
row list format
Return to Top

tree roots

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