# SAS/OR® Software

## Mathematical Programming Tools

Mathematical programs are a class of optimization problems with a goal of maximizing or minimizing an objective function with respect to a set of decision variables, subject to constraints on those decision variables. These optimization problems are categorized by the structure of the objective function and the 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, and 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 software 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 Programming

Linear programs (LPs) are problems that have an objective function and constraints that are defined by using linear functions of the decision variables. The constraints can be a set of linear equalities or inequalities or both.

• The OPTMODEL procedure solves linear programs. The syntax of the procedure's modeling language enables you to express the problem in a form that very closely resembles the symbolic form. PROC OPTMODEL provides three LP solvers: primal simplex, dual simplex, and interior-point. 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 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.
• The OPTLP procedure also solves linear programs by using the same LP solvers that are available in PROC OPTMODEL. PROC OPTLP accepts linear programming problems that are submitted in a SAS data set that has a mathematical programming system (MPS) format. The MPS-format SAS data set corresponds closely to the MPS-format text file that is commonly used in the optimization community.
• The legacy LP procedure solves linear programs using a primal simplex solver. PROC LP 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 procedure saves intermediate results for "warm-starts."
• The legacy INTPOINT procedure solves general linear programming problems by using the interior point algorithm. To solve LP problems using PROC INTPOINT, you save a representation of the LP variables and the constraints in one or two SAS data sets. These data sets are then passed to PROC INTPOINT for solution. The data is specified in the same format that is used by PROC LP. Therefore, any model-building techniques that apply to models for PROC LP also apply to PROC INTPOINT.

## Mixed Integer Linear Programming

Mixed integer linear programs (MILPs) are problems that have an objective function, a set of linear equality or inequality constraints (or both) that are defined using linear functions of the decision variables, and an additional constraint that requires some or all of the decision variables to be integer-valued.

• The OPTMODEL procedure solves mixed integer linear programming problems using the MILP solver. The MILP solver implements 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 OPTMODEL to solve larger and more complex optimization problems.
• The OPTMILP procedure solves mixed integer linear programming problems using the same MILP solver that is provided with PROC OPTMODEL. PROC OPTMILP accepts mixed integer linear programming problems that are submitted in an MPS-format SAS data set.
• The legacy LP procedure solves integer and mixed integer programs using an LP-based branch-and-bound algorithm. PROC LP provides interactive control of the solution process and printing and also handles sparse and dense input formats.

## Network Flow Programming

A network consists of a collection of nodes joined by a collection of arcs. The arcs connect nodes and convey flow of one or more commodities that are supplied at supply nodes and demanded at demand nodes in the network. Each arc has a cost per unit of flow, a flow capacity, and a lower flow bound associated with it. Constrained network models can be used to describe a wide variety of real-world applications ranging from production, inventory, and distribution problems to financial applications.

• To solve a network flow programming problem using the OPTMODEL procedure, you can formulate the corresponding linear programming problem and call the LP solver.
• The legacy NETFLOW procedure also solves network flow programming problems by finding 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. PROC NETFLOW solves both network flow problems and pure linear programs by using an interior-point optimization method. PROC NETFLOW also provides options that enable you to model and solve generalized networks, in which it is possible to have losses or gains in the flow over various arcs.
• The legacy INTPOINT procedure solves the network program with side constraints problem by using the interior point algorithm.

## Nonlinear Programming

Nonlinear programming (NLP) problems involve minimizing or maximizing a continuous nonlinear function subject to linear and nonlinear, equality and inequality, and lower and upper bound constraints. Problems of this type are found in many settings ranging from optimal control to maximum likelihood estimation.

• The OPTMODEL procedure's modeling language 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 IPNLP (interior-point NLP) solvers, both of which are designed to solve general NLP problems.
• The legacy 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.

A quadratic programming (QP) problem is identified by a quadratic term (in addition to or without a linear component) in the objective function, and a collection of linear constraints including general linear constraints along with lower or upper bounds (or both) on the decision variables.

• The OPTMODEL procedure solves quadratic programming problems by using the QP solver. This solver implements an infeasible primal-dual predictor-corrector interior point algorithm.
• The OPTQP procedure solves quadratic programs by using the same QP solver that is provided with PROC OPTMODEL. You specify the problem input data in a SAS data set that has a quadratic programming system (QPS) format.