INDUSTRIAL ENGINEERING APPLICATIONS AND PRACTICE: USERS ENCYCLOPEDIA®

MATHEMATICAL PROGRAMMING

What do the following problems have in common: "integration of strategic and tactical planning in the aluminum industry", "planning the mission and composition of the U.S. Merchant Marine fleet", "design of a naval tender job shop", "a system for bank portfolio planning"? They are all actual applications of mathematical programming to support business and public sector decisions as discussed in a popular book on applied mathematical programming. All these problems are concerned with the efficient use or allocation of limited resources to meet desired objectives.

In order to illustrate the concepts and approaches to be discussed below, consider a very simple example of a mathematical programming problem: product mix problem of production planning. Suppose we can manufacture three different products (1, 2, and 3) using two resources (A and B). Each product requires different amounts from each resource. The profit obtained from the sale of each product is different. What we would like to do is to determine how much of each product we should manufacture with the available resources so that our profit is maximized.

One of the founding fathers of mathematical programming, George B. Dantzig, states in the foreword to his recent book:

"Industrial production, the flow of resources in the economy, the exertion of military effort in a war, the management of finances --all require the coordination of interrelated activities. What these complex undertakings share in common is the task of constructing a statement of actions to be performed, their timing and quantity (called a program or schedule), that, if implemented, would move the system from a given initial status as much as possible towards some defined goal."

To do these, Dantzig goes on, we need the following tools:

• ways to formulate real-world problems in detailed mathematical terms: MODELS,
• techniques for solving these models: ALGORITHMS, and
• engines for executing the steps of algorithms: COMPUTERS & SOFTWARE.

Let us briefly discuss each of these.

Mathematical Programming Models

In order to decide how to design, construct, or operate a physical or an economic system, we need to formulate its analytical model. An analytical model of a system or a process is a mathematical description of the interactions among its variables. There are basically two types of analytical models: predictive and descriptive. A regression model, for example, is a predictive model. Given the new housing starts, we can predict how many garage door openers we can sell during the next few months. On the other hand, laws from physics are examples of descriptive models: e = mc² attempts to explain, or to describe, a physical phenomenon. It says energy contained in a mass is equal to the mass times the square of the speed of light. Most of the descriptive models are neutral; they do not imply any value judgments. But when you are optimizing something, as all mathematical programming models do, you are comparing one design, construct, or operating policy against another. In other words, you are prescribing a particular solution, a course of action, or a decision. Thus mathematical programming models are prescriptive models in which you can control the inputs and can evaluate the outputs.

In constructing a mathematical programming model we need to quantitatively and meticulously identify the variables and describe their interactions. There are two types of variables in these models. The variables whose values can be assigned by the decision-maker are referred to as controllable variables. These are the endogenous variables which are also called decisions, courses of action, or solutions. In our product mix example, the decision variables are how much of each product should be produced. Let us denote symbolically each of these amounts by X₁, X₂, and X₃.

The variables whose values cannot be controlled by the decision-maker are called parameters. The parameters are the givens of the problem. These uncontrollable, or exogenous variables are referred to as scenarios or states of nature, in other problem contexts. In our example problem, how much profit we make from the sale of a product is a given of the problem, i.e. someone else tells us what that number is, we are not free to assign a value to it. Similarly, how much a particular resource is used in the manufacture of a product, how much we have on hand of each resource are the numbers that must be estimated. As Beightler, Phillips, and Wilde mention in their book, Foundations of Optimization, "...[a]s soon as optimization enters the picture, everybody must become quantitative and consequently more meticulous, rigorous, and scientific." In our example problem, suppose the following numbers were given to us: for products 1, 2, and 3, respectively, the unit profit: $6, $2, $4; the amount of resource A needed for each unit of production: 2, 1, 3; the amount of resource B needed: 4, 2, 1; and, finally, suppose we have on hand 4,000 units of resource A, and 6,000 units of resource B.

Once these two types of variables are accurately identified, in order to complete the model, we need to define the interactions among the (decision) variables and the parameters. These interactions are the constraints and the objective function. Constraints are mathematical (as opposed to physical or analog) description of the physics of the system or the process to be modeled. Objective function evaluates the decisions based on a given criterion. It is a mapping from the space of decision variables to the space of measure of effectiveness. The objective function value is the return resulting from taking a specific course of action.

There are many types of constraints. It is impossible to classify and discuss all of them. We will briefly mention few common types, such as resource and requirement constraints and material balance (node conservation) equations. A material balance equation simply state that what comes into a node must go out. For example, in production/inventory processes, "what is carried in inventory from the previous period plus what is produced in this period is equal to the demand for that item in this period plus what will be carried in inventory for the next period." Similar balance equations appear in financial planning problems and other problems in which there is a flow of materials in the system. Requirement constraints state that the solution, to be acceptable, must satisfy certain minimal requirements. For example, in our product mix problem if we had a "marketing" constraint that required a minimal total production of products 2 and 3 to be 1,300 units, in order to keep the company's market share of that line of products, we would need an inequality that states: X₂ + X₃ <= 1,300.

One trivial type of a requirement constraint is nonnegativity constraint, since we cannot manufacture negative quantities, the decision variables can assume only nonnegative quantities, that is, X₁ >= 0, X₂ >= 0, X₃ >= 0. The resource constraints, on the other hand, state that the resource used in the system cannot exceed the amount of available resources. In our product mix example we have two such constraints corresponding to resources A and B. Note that in order to manufacture one product 1 we need 2 units of resource A. Since we are going to manufacture X₁ units of product 1, it will consume 2X₁ units of resource A. Furthermore, each product 2 needs 1 unit of resource A, product 3 needs 3 units. Thus, total amount of resource A used (2X₁ + 1X₂ + 4X₃) cannot exceed (<=) the total amount of resource A available (4,000). So the constraint for resource A is 2X₁ + 1X₂ + 4X₃ <= 4,000. The corresponding constraint for resource B is 4X₁ + 2X₂ + 1X₃ <= 6,000.

Any nonnegative combination of values for (X₁, X₂, X₃) that satisfy the above two resource constraints is a feasible solution to our problem. But some feasible combinations are better than the others. For example the feasible solution (0, 0, 0) results in zero profit, whereas the feasible solution (1, 1, 1) results in a profit of $12. The objective function evaluates feasible solutions based on the chosen measure of effectiveness; in our example the measure of effectiveness is profit maximization. The objective is to maximize the function 6X₁ + 2X₂ + 4X₃. The above discussion of the product mix problem is an example of a linear programming formulation. Continuous linear programming formulation of mathematical programming problems requires four major assumptions. These are proportionality, additivity, divisibility, and certainty.

Proportionality implies that if one unit of product 1 brings $6 profit, a million units will bring $6 million in profits. Similarly, if it takes two units of resource A to make one unit of product 1, then it will require exactly two million units of resource A to make a million product 1's. Proportionality, in effect, prohibit square, cube, or any higher order terms, or any other functional forms other than linearity for the decision variables. Additivity, on the other hand, does not allow any cross terms. This is to say that the contribution of each variable to the objective function, or to the left-hand side of each constraint, is independent of the values assumed by other variables. Thus every function is the sum of the individual contributions of the activities. These two assumptions do not allow for nonlinearity, but the world is highly nonlinear. "Fortunately" as Dantzig states, "systems of linear inequalities (as opposed to equalities) permit us to approximate most of the kinds of nonlinear relations encountered in practical planning."

Divisibility assumption allows for decision variables to have fractional values. In our example, the product mix problem, under this assumption we may end with a production plan that recommends producing, for example, ¾ units of a product. If the total number of units to be produced is in the order of thousands, or even hundreds, then rounding off this fractional value to a neighboring integer may be quite acceptable. On the other hand, if the solution recommends producing 1.75 units of a product, then the error introduced when the solution is rounded off to 1 or 2 can be very significant (furthermore, such a rounded off solution may not even be feasible.). Another situation where divisibility assumption becomes important is when binary variables are used in the formulation of certain mathematical programming problems. These binary variables are logical variables such that when their value is equal to 1, a certain statement is "true" and when it is equal to 0, that statement is "false". For example, X = 1 may stand for leasing a warehouse at a certain location and X = 0 indicates not leasing the warehouse. Then the solution X = 0.5 is meaningless. The mathematical programs in which one or more variables must be integral valued require specialized algorithms of mixed integer programming.

Finally, certainty assumption requires that all parameter values to be known constants; randomness is not allowed. But almost all parameter values are some form of estimates, or forecasts, in real applications. Sensitivity analysis techniques can be used to check the severity of this assumption in a particular problem. Basically, sensitivity analysis checks how sensitive is the optimal solution is to the specific value of a parameter. For example, suppose we cannot be sure of the exact value of the unit profit for product 1 in our product mix example. All we can say is that profit margin will be somewhere in between $5 and $7. Either by special techniques of sensitivity analysis or simply using "What if...?" analysis, if we can establish that the optimal value of the decision variable X₁ is equal to 1,000 for any value of the parameter, unit profit, in the range [5, 7], then there is no need to do anything further. Go ahead and plan for producing 1,000 units of product 1. Of course, your profits will change depending on the exact value of the unit profit realized; but in any case, it is optimal to produce 1,000 units. On the other hand, if the solution is highly sensitive to that parameter value, then we need to do further work. For example, if it turns out that the optimal value of X₁ is equal to 500 when unit profit is $5 and equal to 1,500 when the unit profit is $7, we need to accurately estimate the exact value for the profit. There exist cases, though, no matter how much effort is expanded, it will not be possible to eliminate the effects of randomness, or uncertainty, in the parameter values. In those cases one has to resort to the techniques of stochastic programming.

Mathematical Programming Algorithms

An algorithm is a step-by-step procedure that solves a class of problems. In the context of mathematical programming, we can define a problem class by explicitly specifying its mathematical structure. For example, the class of "linear programming problems" are all problems in which you maximize (or minimize) a linear objective function subject to linear equality and inequality constraints where all variables are restricted to be nonnegative. If, in addition, some (but not all) variables are restricted to be integers, then we have the class of "mixed integer linear programming problems." (If all variables are restricted to be integers, the class of problems is "pure integer linear programming problems", and so on.)

Naturally, an algorithm designed to solve a broader class of problems is less efficient on a specific problem class than a special purpose algorithm which is designed specifically for that class of problems. For example, the assignment problem is a special type of a transportation problem which, in turn, is a linear programming problem. Solving an assignment problem using a general purpose linear programming algorithm is less efficient than using a transportation algorithm for solving the same problem. But the most efficient way to solve an assignment problem is to use an algorithm that is designed especially for assignment problems. How this efficiency achieved is by exploiting the special structure of that specific class of problems.

Although used rather loosely in the above paragraph, the term efficiency is a technical term. It is the subject matter of computational complexity, or the theory of NP-completeness. This area of study investigates the level of complexity inherent in problem classes.

Now let us look at the typical steps in a mathematical programming algorithm for (convex) optimization problems with continuous variables.

• Initialization Step: Find a feasible starting solution.
• General Step: Check if there is an improving feasible direction to move. If there is none, stop; the current solution is optimal. Else, determine the step size to be taken along the improving direction. Replace the current solution with the new solution thus obtained. Repeat until optimality is reached.

Each of these steps are implemented slightly differently in various algorithms. Dantzig's Simplex Method is an elegant algorithm, which is probably the most widely used solution procedure in mathematical programming. The Simplex Method is a general-purpose algorithm that solves any linear programming problem. Let us very briefly review how the Simplex Method accomplishes the above steps.

To find a feasible starting solution, the Simplex Method basically solves another linear programming problem whose initial feasible solution is trivially available (in the literature this is referred to as the solution of Phase-I problem.) So we can safely assume that we have a starting solution.

Every linear inequality constraint can be converted into a linear equation by adding a nonnegative (slack) variable to the left-hand-side of a less-than-or-equal-to constraint, or by subtracting a nonnegative (surplus) variable from the left-hand-side of a greater-than-or-equal-to constraint. So every linear program can be expressed in its standard form as maximizing or minimizing a linear function such that a set of linear equations are satisfied and all the variable values are nonnegative. Suppose we have m equations in n variables. Assuming that we do not have any redundant equations, to find a solution, we have to set n - m of the variables (referred to as the non-basic variables) equal to zero and solve the system of m linear equations in m remaining variables (referred to basic variables). If in the resulting solution all variables have nonnegative values, then we have a basic feasible solution. The starting solution that is found in the initialization step is such a basic feasible solution.

Note that at the current solution all nonbasic variables at level zero. To have any different solution than the current one, the level of at least one of the nonbasic variables must be increased from its current value of zero. The Simplex Method checks to see if increasing the current value of any nonbasic variable will have an improving effect on the objective function value. If it cannot find any, then the current solution must be the optimal one; and the algorithm stops.

On the other hand if there is at least one nonbasic variable when its value is increased from its current level of zero, the objective function improves, then the Simplex Method chooses that nonbasic variable as the "direction" to move along. The next question is how much to move along that direction, i.e. how much can we increase the value of that nonbasic variable? The answer is as much as possible as long as all the linear equations are satisfied and until the first basic variable whose value reaches zero from above is detected. (If no such basic variable is detected, then we can increase the value of the "entering" nonbasic variable indefinitely, thus improving the value of the objective function indefinitely, resulting in a so called unbounded problem.)

A little reflection on the linearity assumption should convince the reader why the above optimality check and the "step size" calculation make sense. We have, now, a new solution with, again, at most m positive valued variables. (We have started with m basic variables, then begin to increase the value of one nonbasic variable. When we stop it is because one of the basic variable's value is driven to zero, further increase would make its value negative. The previous basic variable whose value becomes zero, now is a nonbasic variable; and the nonbasic variable whose value has increased is the new basic variable. Thus ending up again with m basic variables.) This main step is repeated again, looking for another nonbasic variable whose "introduction" to the solution will cause an improvement in the objective function value.

Will these iterations ever stop? Yes, after finite number of iteration the Simplex Method will either find the optimal solution, or declare that the solution is unbounded, or state that there is not even a single solution possible with the stated constraints. For this last statement to occur (that is, for the problem to be infeasible) we would not have been able to solve the Phase-I problem in the Initialization Step. Because if there is even a one nonnegative solution of the linear equations exists, regardless of its objective function value, the Phase-I problem should have found it. When we introduce a nonbasic variable to the solution that improves the objective function value and no currently basic variable is "leaving" the solution, then the problem is unbounded. If the problem is not infeasible, and not unbounded, then what we do in each iteration is that we choose m variables out of n variables and set the remaining n - m variables equal to zero; and solve the resulting system of m equations in m unknowns. Since there is a finite number of ways n things can be chosen m-at-a-time, and that that choice of m things cannot be repeated (objective function value is not becoming worse in each consecutive choice), the algorithm should stop after finite number of steps.

The above discussion of the Simplex Method overlooked a number of fine details and mathematical rigor. The purpose was to give the essence of the Simplex Method as an example of an algorithm in mathematical programming.

Mathematical Programming Software

Practically all mathematical programming models in practice are large scale and practically all mathematical programming algorithms are tedious enough to make the solution of these models by hand impossible. Thus we need computers and mathematical programming software. It is not a mere coincidence that the mathematical programming showed a remarkable advance during the second part of this century. It is the advent of computers that made mathematical programming an indispensable tool to support business and public sector decisions.

Even to attempt to survey the currently available mathematical software is beyond the scope of this introductory discussion. Moreover, software development is a very dynamic field in which developments do occur almost on a daily basis. Fortunately there exists a comprehensive and excellent resource on the Internet: NEOS Guide from the Optimization Technology Center. Interested reader is encouraged to visit these pages for a thorough and up-to-date information on mathematical programming software.

Two relatively recent developments in mathematical programming software from end user perspective, though, require special mention: modeling languages and use of spreadsheets. Modeling languages, such as AMPL, GAMS, and LINGO, allow the user to express a model of the mathematical programming problem algebraically and would admit the data of the problem in convenient formats. Then, using a number of solvers, which are the special purpose algorithms for a variety of problem classes, they solve the problem and generate the reports on the solution and its analysis. The user can choose to guide the actual solution process or it can be entirely transparent to the user.

One reason for the lack of wider use of mathematical programming in business and public sector decision making is probably the need for the nonspecialist to learn a different "language" comprised of mathematics of optimization and certain amount of computer expertise. But spreadsheets are used by practically every decision-maker in business and in public sector. As more and more optimization capabilities are being added on to the commercially available spreadsheet programs, we shall start to see more widespread applications of tools and techniques of mathematical programming in practice. A place to start to "perform management science in spreadsheets" is Tom Grossman's "Resources for Management Science in Spreadsheets".

Mathematical Programming Applications

Probably the best source to learn about the real world applications of mathematical programming and how practical problems are formulated as mathematical programs is the applications journal Interfaces. An excellent overview of mathematical programming applications can be found in the five case prepared by the Optimization Technology Center: "The Diet Problem" (Linear Programming), "The Portfolio Optimization Problem" (Quadratic Programming), "The Natural Gas Planning Case Study" (Stochastic Linear Programming), "The Minimal Surface Area Problem" (Unconstrained Optimization), and "The Cutting-Stock Problem" (Integer Programming).

Finally, for a comprehensive discussion of the terminology in this area one should refer to H. Greenberg's Mathematical Programming Glossary.

© Copyright 1999   INTERNATIONAL JOURNAL OF INDUSTRIAL ENGINEERING

Ömer S. Benli
Bilkent University