SAS/OR Software

R & D: Operations Research Software: Mathematical Programming Tools

NEW! SAS/OR 9.1.3 Release 3.2 is now available. This release features production versions of the OPTMODEL, OPTLP, OPTMILP, and OPTQP procedures. PROC OPTMODEL also adds mixed-integer modeling capabilities. To obtain this new SAS/OR release, see

Request Form

Comprehensive Tools for Mathematical Programming

Mathematical programs are a class of problems with an objective that is a function of a set of decision variables and is to be optimized (maximized or minimized) subject to constraints on those decision variables. These problems are categorized by the structure of the objective function and constraints.

Mathematical programming techniques in SAS/OR software help solve mathematical programs that can correspond to a wide range of problems including resource allocation, distribution, product mix and blending, production planning, capital budgeting, asset allocation, portfolio selection and staffing, to name a few.

Specialized algorithms (called solvers) that exploit the structure in the problem have been developed for solving specific categories of mathematical programs. The approach is to exploit characteristics of the problem to find optimal solutions more efficiently. All optimization procedures in SAS/OR employ such specialized algorithms and are defined by the structure of the mathematical program that they solve. The following sections detail these structural categories.

Linear and Mixed-Integer Programming

The LP procedure solves linear, integer, and mixed-integer programs. Linear programs are problems that have an objective function and constraints that are defined using linear functions of the decision variables. The constraints can be a set of linear equalities and/or inequalities. If there is an additional constraint that all or some of the decision variables must be integer-valued, then the program is called an integer or mixed-integer program.

The procedure solves these problems using a primal simplex solver and provides interactive control of the solution process and printing, handles sparse and dense input formats, and enables you to perform ranging, objective and right-hand-side sensitivity analysis, and parametric programming. In addition, the software saves intermediate results for "warm-starts."

New Procedures

The OPTLP procedure (SAS/OR 9.1.3, Release 3.2) provides linear programming solvers and enables you to choose from three linear programming solvers: primal simplex, dual simplex, and interior-point (experimental). The simplex solvers implement a two-phase simplex method, and the interior point solver implements a primal-dual predictor-corrector algorithm. All three solvers are newly rewritten and are designed for excellent performance and scalability. Presolvers, which work aggressively to reduce the effective size of problems before the solvers are invoked, are also provided.

PROC OPTLP accepts linear programming problems that are submitted in an MPS-format SAS data set. The MPS-format SAS data set corresponds closely to the MPS-format text file (commonly used in the optimization community) and was first introduced in SAS/OR 9.1.3, release 2.1.

You can also use the PROC OPTMODEL modeling language (SAS/OR 9.1.3, Release 3.2) to solve linear programs. The OPTMODEL syntax enables you to express the problem indirectly in the SAS language in a form that very closely resembles the symbolic form.

Within both the OPTLP and OPTMODEL procedures, you have access to three LP solvers --- primal simplex, dual simplex, and the interior-point solver (experimental).

The new OPTMILP procedure (SAS/OR 9.1.3, Release 3.2) solves mixed-integer linear programming (MILP) problems with an LP-based branch-and-bound algorithm. The algorithm also implements advanced techniques including presolvers, cutting planes, and primal heuristics. The resulting improvements in efficiency enable you to use PROC OPTMILP to solve larger and more complex optimization problems than you could solve with previous releases of SAS/OR.

PROC OPTMILP accepts mixed-integer linear programming problems that are submitted in an MPS-format SAS data set.

You can also access this experimental MILP solver using PROC OPTMODEL.

Network Flow Programming

The NETFLOW procedure finds the shortest path, the maximum flow, or the minimum cost flow through a network, using a specialized simplex algorithm. In this procedure, the decision variables represent the flow through a network that has sources of flow and demands for flow. The procedure also supports linear side constraints on the flows through the network and on additional nonarc decision variables, and it can solve both network flow problems and pure linear programs using an interior-point optimization method.

New Options in PROC NETFLOW

Two new options, GENNET and EXCESS=, were introduced in the NETFLOW procedure in SAS/OR 9.1.3, Release 2.1. These options enable you to model and solve generalized networks, in which it is possible to have losses or gains in the flow over various arcs. Some real-life problems that lend themselves to be modeled as generalized networks include:

Power generation: As electricity is transmitted over wires, there is some unavoidable loss along the way. This loss is represented by a multiplier less than 1.0.
Financial models: A flow through an arc could represent money in a bank account earning interest over the specified time period. In this case, the gain is represented by a multiplier greater than 1.0.
Changes in the form of flow through the network due to assembly operations: various subassemblies reach a particular node and the resulting commodity exiting that node is a completed part. In this case, the multipliers could be defined through the bill-of-material.

Nonlinear Programming

The NLP procedure solves mathematical programs in which the objective function is a general nonlinear function of the decision variables and the constraints are linear or general nonlinear functions of the decision variables. The procedure includes a variety of algorithms, each specializing in solving different variants of the general nonlinear program.

New Procedure

The OPTMODEL procedure's modeling language (SAS/OR 9.1.3, Release 3.2) enables you to formulate and solve nonlinear programming problems in a very concise manner. You can choose from a variety of optimization techniques provided by four nonlinear programming solvers: the NLPU solver, which is designed to solve unconstrained NLP problems, the NLPC solver, which is designed to solve linearly constrained NLP problems, and the SQP (sequential quadratic programming) and experimental IPNLP (interior-point NLP) solvers, both of which are designed to solve general NLP problems.

Quadratic Programming

The OPTQP procedure (SAS/OR 9.1.3, Release 3.2) solves mathematical programming problems with a quadratic objective function and a set of linear constraints. It replaces the earlier experimental QP procedure and uses an experimental quadratic programming solver which may also be accessed using PROC OPTMODEL.

Statistics and Operations Research Home Page | Operations Research