Handling Sparsity in the Jacobian Directly

In many optimization problems, several (and often most) of the coefficients in the constraint matrix are zero.  For example, consider the term  "0 times X3" in the constraint:

        1 X1 + 1 X2 + 0 X3 <= 450.

We often include the zero terms to facilitate the use of the SUMPRODUCT( ) function in Excel (or equivalent FOR loops in Visual Basic or another language).  But we recognize that this constraint does not depend on X3; it has a zero partial derivative with respect to X3.

In large optimization models, the Jacobian matrix often contains a great many zero elements.  In fact, in LP models with tens of thousands of variables and constraints, it is common for only 2% to 3% of the elements to be nonzero.  A matrix with many zero elements is called sparse; a matrix with mostly nonzero elements is called dense.

A matrix of a few hundred, or even a thousand rows and columns doesn't take that much memory, by modern standards.  But a 10,000 by 10,000 matrix of double precision numbers (8 bytes each) would require 800 megabytes of RAM if all of the zero elements were stored explicitly.  A better alternative is to store only the nonzero elements and their indices.

Solver engines designed for large-scale problems, such as the Large-Scale LP Solver, Large-Scale GRG Solver, Large-Scale SQP Solver, KNITRO Solver, MOSEK Solver, Gurobi Solver and XPRESS Solver, are designed to exploit sparsity in the Jacobian matrix.  In the Premium Solver products for Excel, zero elements in the Jacobian are detected automatically, and only nonzero elements are passed to the Solver engines.

The Solver SDK products provide a convenient way to define a sparse matrix, using the DoubleMatrix object.  For example, you can define a DoubleMatrix object MyMatrix with 10,000 rows and columns, and assign values to different elements with syntax such as MyMatrix[i,j] = value just as you would for a two-dimensional array, but MyMatrix will store only the non-zero elements of the matrix.