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 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 (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.