Introduction to Optimization

Overview

This chapter describes how to use SAS/OR software to solve a wide variety of optimization problems. The basic optimization problem is that of minimizing or maximizing an objective function subject to constraints imposed on the variables of that function. The objective function and constraints can be linear or nonlinear; the constraints can be bound constraints, equality or inequality constraints, or integer constraints.

Traditionally, optimization problems are divided into Linear Programming (LP; all functions are linear) and Nonlinear Programming (NLP). Variations of LP problems are assignment problems, network flow problems, and transportation problems. Nonlinear Regression (fitting a nonlinear model to a set of data and the subsequent statistical analysis of the results) is a special NLP problem. Since these applications are so common, SAS/OR software has separate procedures or facilities within procedures for solving each type of these problems. Model data are supplied in a form suited for the particular type of problem. Another benefit is that an optimization algorithm can be specialized for the particular type of problem, reducing solution times. Optimizers can exploit some structure in problems such as imbedded networks, special ordered sets, least squares, and quadratic objective functions.

SAS/OR software has five procedures used for optimization:

PROC ASSIGN for solving assignment problems
PROC LP for solving linear and mixed integer programming problems
PROC NETFLOW for network programming problems with side constraints, and linear programming problems solved by an Interior Point algorithm
PROC NLP for non-linear programming problems
PROC TRANS for solving transportation problems

SAS/OR procedures use syntax that is similar to other SAS procedures. In particular, all SAS retrieval, data management, reporting and analysis can be used with SAS/OR software. Each optimizer is designed to integrate with the SAS System to simplify model building, maintenance, solution, and report writing. Data for models are supplied to SAS/OR procedures in SAS data sets. These data sets can be saved and easily changed and the problem can be re-solved. Because the models are in SAS data sets, problem data that can represent pieces of a larger model can be concatenated and merged. The SAS/OR procedures output SAS data sets containing the solutions. These can then be used to produce customized reports. This structure allows decision support systems to be constructed using SAS/OR procedures and other tools in the SAS System as building blocks.

The following list suggests application areas where decision support systems have been used. In practice, models often contain elements of several applications listed here.

Product-Mix problems find the mix of products that generates the largest return when there are several products that compete for limited resources.
Blending problems find the mix of ingredients to be used in a product so that it meets minimum standards at minumum cost.
Time-Staged problems are models whose structure repeats as a function of time. Production and inventory models are classic examples of time-staged problems. In each period, production plus inventory minus current demand equals inventory carried to the next period.
Scheduling problems assigns people to times, places, or tasks so as to optimize peoples' preferences while satisfying the demands of the schedule.
Multiple objective problems have multiple conflicting objectives. Typically, the objectives are prioritized and the problems are solved sequentially in a priority order.
Capital budgeting and project selection problems ask for the project or set of projects that will yield the greatest return.
Location problems seek the set of locations that meets the distribution needs at minimum cost.
Cutting stock problems find the partition of raw material that minimizes waste.

Chapter Contents
Previous
Next
Top