Solver Advanced Tutorial - Handling Sparsity in the Jacobian Directly

Handling Sparsity in the Jacobian Directly

When we wrote the constraint functions in the Product Mix example, we included terms such as "0 times x3" in

1 x1 + 1 x2 + 0 x3 <= 450 (Chassis)

...so that we could treat the constraints uniformly, use the SUMPRODUCT function in Excel (or equivalent FOR loops in Visual Basic or another language), and easily describe the Jacobian matrix.  But we recognized that this constraint does not depend on x3, the number of Speakers produced -- it has a zero partial derivative with respect to x3.

Looking at the entire Jacobian matrix for the Product Mix model, we see that it contains several zero elements.

1 1 0 1 0 0 2 2 1 1 1 0 2 1 1

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 -- more than the memory available on most PCs today -- 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.

But when you call the Solver DLL products from your own program in Visual Basic or another language, you must create arrays that store only the nonzero elements and their indices, and pass these arrays to the Solver DLL.  You do this by creating the matbeg, matcnt and matind arrays (and a much smaller matval array) and passing these four arguments to either loadlp() or loadnlp().  Further details can be found in the Solver DLL Platform Programmer's Guide.

<< Back to Tutorial Start

To Learn More: For instant access to our white papers, example models, full-text User Guides, and to download free 15-day trial versions of our software products whenever you're ready, register now with no obligation.

User type Please Select Commercial User Consultant Corp Developer Govt/Military Professor Student VAR/ISV Firm Email address Name First Last Company University Phone

Trial version passwords are sent to the above email address. Our Privacy Policy protects you.