Advanced Methods for XPRESS
A Full Arsenal of Solution Methods For mixed-integer (MIP) problems, XPRESS uses an advanced Branch & Cut method, which combines Branch & Bound with "cut generation" strategies, that you can easily customize. Click here to learn about the options that allow you to choose and further control these solution methods. |
|
Sparse Matrix Storage
Sparse matrix storage methods take advantage of sparsity in large LP models, where subsets of the constraints typically depend on only a small subset of the variables. For example, an LP coefficient matrix for a problem with 10,000 variables and 10,000 constraints would take about 800 megabytes for matrix storage using dense storage methods, but if this problem has the sparsity typical of larger models, it would take about 24 megabytes using the sparse storage methods in the XPRESS Solver. (To learn more, click on Problem Size and Sparsity, covered in our Solver Tutorial.)
Matrix Factorization
Large LP models require hundreds of thousands to millions of floating-point arithmetic calculations to solve. Because of the finite precision inherent in computer arithmetic, small numerical errors occur in these calculations. Using conventional matrix representation and Simplex method iterations, these errors typically have a cumulative effect, leading to a numerically unstable problem and possibly large errors in the "solution."
The XPRESS Solver Engine uses a factorization of the LP matrix, called the LU decomposition, which remains numerically stable. This factorization is updated using advanced numerical methods (including dynamic Markowitz refactorization) that are much faster than a full update on each Simplex iteration. These methods enable the XPRESS Solver to maintain accuracy, find the optimal solution, and do so much faster than conventional methods.
Intelligent Defaults Plus Fine-Grained Control
The XPRESS Solver Engine features more than 60 user-controlled options and tolerances. But relax -- since they all have intelligent default values, you won't even have to look at most of them unless you want fine-grained control of solution strategies. The options are organized into "basic" and "advanced" sets that appear in panes in the Solver Options dialog.
You can easily select the solution method (primal Simplex, dual Simplex or Newton Barrier), a variety of Branch & Bound and Branch & Cut strategies for mixed-integer problems, time and iteration limits, and the like. Click here for a more complete description of XPRESS Solver Engine options and tolerances.