Mathematical Programming
New Procedures for Linear and Nonlinear Programming
OPTMODEL Procedure
The OPTMODEL procedure comprises the powerful OPTMODEL modeling language and state-of-the-art solvers for several classes of mathematical programming problems.
The OPTMODEL modeling language provides a modeling environment tailored to building, solving, and maintaining optimization models. This makes the process of translating the symbolic formulation of an optimization model into OPTMODEL virtually transparent since the modeling language mimics the symbolic algebra of the formulation as closely as possible. OPTMODEL also streamlines and simplifies the critical process of populating optimization models with data from SAS data sets.
You can use OPTMODEL to build and solve optimization models or you can use it purely as a modeling tool, saving optimization models built with OPTMODEL in SAS data sets that may be submitted to other optimization procedures in SAS/OR.
Example Problem
Consider the following nonlinear programming problem:
The OPTMODEL formulation is as follows:
proc optmodel;
number ub{1..3} = [20 11 42];
/* variable upper bounds */
var x{i in 1..3} >= 0 <= ub[i] init 10;
/* initial values */
min f = -1*x[1]*x[2]*x[3];
/* objective function */
con c1: x[1] + 2*x[2] + 2*x[3]
>= 0; /* constraint 1 */
con c2: 72 - x[1] - 2*x[2]
-2*x[3] >= 0; /* constraint 2 */
solve; /* invoke solver */
print x;
quit;
You can view details about the optimization progress and status in the iteration log. The summary results window, in its default setting, displays information about the input problem, solution technique used, status of the current solution, number of iterations taken, and the current objective value. In addition, it also displays any information requested using the PRINT statement within the modeling language. The output of the code above is as follows:
OPTMODEL Language Features
-
Optimization-oriented syntax (parameters, variables, arrays, constraints, objective function)
-
Symbolic, algebraic modeling language
-
Model-data separation and transparent access to SAS data sets
-
The ability to use in defining models.
-
Automatic differentiation, modern flow control, dynamic model generation, and more.
Unconstrained Nonlinear Programming
The NLPU solver in OPTMODEL procedure enables you to solve unconstrained nonlinear programming problems. An unconstrained NLP can be written as:
, where 
is the nonlinear objective function and x is the decision variable.
Solution Techniques
-
Fletcher-Reeves nonlinear conjugate gradient algorithm
-
Polak-Ribiere nonlinear conjugate gradient algorithm
-
Limited-memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) algorithm
Nonlinear Programming with Linear Constraints
The NLPC solver in the OPTMODEL procedure enables you to solve nonlinear programming problems that are linearly constrained. Mathematically, the problem can be stated as:
where 
is the nonlinear objective function, 
is the matrix of linear constraints, and 
is the right-hand-side. The lower and upper bounds on the decision variable are denoted by l and
u, respectively.
Solution Techniques
-
Trust Region Method
-
Newton-Raphson Method with Line Search
-
Conjugate Gradient Method
-
Quasi-Newton Method (experimental)
General Nonlinear Programming
The SQP solver and the experimental IPNLP solver in the OPTMODEL procedure enable you to solve general nonlinear programming problems. Mathematically, a general nonlinear programming problem can be stated as:
where is the nonlinear objective function and 
is the set of general nonlinear equality and inequality constraints. The lower and upper
bounds on the decision variable are denoted by l and u, respectively.
Solution Techniques
-
The SQP solver solves quadratic programming (QP) subproblems to find a search direction. This subproblem involves some linear equality and inequality constraints, and an active set method is used to solve the subproblem. An augmented Lagrangian function is employed as a merit function for the line search. Global convergence is ensured when the Wolfe-Powell conditions are satisfied.
-
The IPNLP solver implements a primal-dual interior point algorithm that includes several powerful features from recent state-of-the-art algorithms. It uses a line-search procedure and a merit function to ensure convergence of the iterates to a local minimum.
Key Features
-
The SQP solver has a built-in procedure to find a good estimate of the Lagrange multipliers, given the starting points for the decision variables.
-
The SQP solver also provides an option, HESCHECK, to verify the second-order necessary condition for a local optimal solution. This feature ensures that the solver does not terminate at a saddle point, which is not optimal.
-
The IPNLP solver iteratively generates better approximations of the primal variables as well as the dual variables. The solver also ensures that the primal iterates always remain strictly within their bounds for every iteration.
-
The IPNLP solver is particularly suited for problems that contain many dense nonlinear inequality constraints, and it is expected to outperform solvers that use other NLP solution techniques.
Linear Programming
The OPTLP procedure can be used to solve linear programming (LP) problems,which can be formulated mathematically as follows:
The OPTLP procedure provides you with a choice of three solvers --- primal simplex, dual simplex, and iterative interior point.
Input Data
PROC OPTLP requires that you specify the input data as an MPS-format SAS data set. The MPS format is a widely accepted format in the optimization community for specifying linear programs.
Output Data
The OPTLP procedure stores the primal and dual output in separate data sets. These data sets contain problem- and solution-related information. Information related to the problem include objective function identification, names of constraints and variables and their types, lower and/or upper bounds, etc.
Solution-related information in the primal data set includes the current value of each decision variable, its current status, and its reduced cost. In the dual output data set, solution-related information includes the current value of the dual variable associated with each constraint, status of the slack variable for the constraint, and the current value of the constraint.
Using OPTMODEL to solve LP's
You can also solve LP problems using PROC OPTMODEL. You can express the problem in a manner that resembles its symbolic algebraic formulation, invoke a solver of choice, and view the solution and related information about the optimization process. OPTMODEL offers all three solvers available in PROC OPTLP.
Quadratic Programming
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. Mathematically the problem may be expressed as follows:
The OPTQP procedure finds the values of variables that minimize the total cost of the solution. The value of each variable is at or between the variable's lower and upper bounds, and the constraints are satisfied.
Input Data
PROC OPTQP requires that you specify the input data as a QPS-format SAS data set. The QPS format is an extension of the widely used MPS format used for specifying linear programming problems. It includes an additional section named QSECTION that enables you to specify the Hessian matrix of the quadratic term in the objective function.
Output Data
The OPTQP procedure stores the primal and dual output in separate data sets. These data sets contain problem- and solution-related information. Information related to the problem include objective function identification, variable names and types, lower and/or upper bounds, etc. Solution-related information include current value of each decision variable and its status in the current solution.
Using OPTMODEL to solve QP's (experimental)
You can also solve QP problems using PROC OPTMODEL. You can express the problem in a manner that resembles its symbolic algebraic formulation, invoke the QP solver, and view the solution and related information about the optimization process. Note that use of the QP solver from OPTMODEL is experimental. For production results you can build a QP problem in OPTMODEL, use the SAVE QPS statement to save the problem in a SAS data set, and then supply that data set to PROC OPTQP.
Mixed-Integer Linear Programming
The OPTMILP procedure can be used to solve mixed-integer linear programming (MILP) problems. Such problems can be expressed mathematically as follows:
The OPTMILP procedure implements an LP-based branch-and-bound algorithm as well as several advanced techniques such as presolving, cutting planes, and primal heuristics to improve the efficiency of the overall algorithm.
Input Data
PROC OPTMILP requires that you specify the input data as an MPS-format SAS data set. The MPS format is a widely accepted format in the optimization community for specifying mixed-integer linear programs. It is also possible to input an incumbent solution in the MPS format.
Output Data
The OPTMILP procedure outputs an optimal solution or the best integer feasible solution found, if any, in SAS data sets. These data sets contain problem- and solution-related information. Information related to the problem include objective function identification, names of constraints and variables and their types, lower and/or upper bounds, etc.
Solution-related information in the primal data set includes the current value of each decision variable. In the dual output data set, solution-related information includes the current value of each constraint.
Using OPTMODEL to solve MILP's
You can also solve MILP problems using PROC OPTMODEL. You can express the problem in a manner that resembles its symbolic algebraic formulation, invoke the experimental MILP solver, and view the solution and related information about the optimization process.
Statistics and Operations Research Home Page | Mathematical Programming