Introduction to Modeling Languages and AMPL

For the Spreadsheet User

[Dividing Line Image]

When a spreadsheet model becomes unwieldy for expressing your optimization problem, an algebraic modeling language such as AMPL can help. Your model can be written far more compactly; errors can be found more easily; the model can be adjusted easily to accommodate different problem sizes; and you can solve larger problems in far less time in many cases, even when using the same solvers.

WHY USE A MODELING LANGUAGE?

Spreadsheets such as Microsoft Excel have several advantages for building optimization models. Your learning curve is minimized if you are already familiar with Excel spreadsheet modeling. You can use all of the powerful facilities in Excel to create, modify, format and audit your model. It is easy to add charts and graphics to present your results. And since your co-workers are probably familiar with spreadsheets too, it is easier to communicate results to others.

When a model becomes larger, however, the spreadsheet approach runs into problems. When you have hundreds or thousands of formulas copied into different cells on your spreadsheet, it becomes increasingly difficult to track down errors in an ordinary model -- and this difficulty is magnified for optimization models. It is also hard for others to understand your model and extend it, or even for you if you haven't worked with the model for some time. The result is much effort wasted hunting through a large model.

A further difficulty arises when the amount of data to be used in the model (the model dimensions) begins to change. Spreadsheet models are often fixed by their two-dimensional layout and are difficult to modify to accommodate (say) additional products, regions, time periods or other dimensions. Attempts to add these elements very often introduce errors into the spreadsheet model, which are hard to find and correct.

Algebraic modeling languages such as AMPL are designed to overcome these problems with spreadsheets. They allow you to express your model in a higher-level way -- writing one expression which expands into hundreds of constraints, for instance. And models written this way are flexible in their dimensions, so you can accommodate additional products, regions, time periods, etc. with no changes to your model.

HOW HARD IS IT TO LEARN AMPL?

AMPL is a new language which involves some learning effort, but the effort is simplified considerably because the language is so similar to standard algebraic notation of the type you first encountered in high school. In fact, AMPL statements are closer than even Excel formulas to standard algebraic form. AMPL is a higher level language which deals naturally with arrays or sets in single statements. If you have ever tried to use Excel's array formulas, you will find that AMPL is far more flexible and easier to use.

Unlike some other modeling languages, AMPL is powerful and general -- you can write an arbitrary expression in any context which requires a value, and you can use any sort of set or indexing expression where index values are required. You learn a few simple rules for composing expressions and statements which can be used anywhere in your model.

AMPL strongly encourages you to separate your model from the data which is used to create a specific, solvable instance of the model. You will find that in AMPL, it is natural to write models which are more general than the ones you created in spreadsheet form, and that these models can be more easily re-used in other situations. Since AMPL models are written to be general, you will probably find that you can more easily borrow from a prewritten AMPL model (like the ones in Compass's library of models) to create a new model for your own needs.

WHAT DOES AN AMPL MODEL LOOK LIKE?

To get a feeling for AMPL, let's examine a classical diet planning model, similar to the one George Dantzig used when he invented linear programming in the 1940s. In this model, you can choose different amounts of food, of set of available foods, to create a diet or meal. Each food contains certain nutrients, and the diet (combination of amounts of foods) you select must provide a certain amount of each nutrient. Each food also has a different cost, and the objective is to minimize the total cost of the diet. Here is the complete AMPL model for the diet problem:

set NUTR; 
set FOOD; 
param cost {FOOD} > 0; 
param f_min {FOOD} >= 0; 
param f_max {j in FOOD} >= f_min[j]; 
param n_min {NUTR} >= 0; 
param n_max {i in NUTR} >= n_min[i]; 
param amt {NUTR,FOOD} >= 0; 
var Buy {j in FOOD} >= f_min[j], <= f_max[j]; 
minimize total_cost: sum {j in FOOD} cost[j] * Buy[j]; 
subject to diet {i in NUTR}: n_min[i] <= sum {j in FOOD} amt[i,j] * Buy[j] <= n_max[i];

The AMPL model begins by defining a set NUTR of nutrients and a set FOOD of foods. In your model, it is not necessary to specify how many nutrients and foods will be used, the names of the nutrients and foods, the costs and minimum amounts, etc.; all of this is data which will later be combined with the model by the AMPL system and used to generate a specific model instance to be solved.

The AMPL model then defines parameters which are indexed over the sets NUTR and FOOD. This means that there will be a cost figure, a minimum amount and a maximum amount for each food when the model instance is created; the number of parameter values is determined later when the number of foods is known. Similarly, there is a minimum and maximum amount of each nutrient. Notice that the parameter amt (the amount of each nutrient found in each food) is indexed over both NUTR and FOOD.

Next, the decision variables are introduced with the var statement. The variables (the amounts to buy) are indexed over FOOD and are given lower and upper bounds (which will be used by the solver). Then the objective is defined as the sum, indexed over FOOD, of the cost of each food times the amount bought. In the AMPL model, unlike a spreadsheet model, the number of elements multiplied and summed is variable and is determined by the amount of data supplied.

The last two lines define a set of constraints named diet, indexed over NUTR. Each constraint is computed as a sum, indexed over FOOD, of the amount of nutrient in each food times the amount of food bought, which yields the total amount of that nutrient in the diet. Lower and upper bounds are placed on each of these nutrient amounts. The solver will find the values of Buy which satisfy the constraints (and bounds on the variables) and which minimizes the total cost of the diet.

ADVANTAGES OF AMPL

Some of the advantages of AMPL are apparent from the diet model. Compared to an Excel spreadsheet, the AMPL model is general, i.e. useful for diets with varying numbers of foods and nutrients. The model is very compact, and remains the same size no matter how much data is used. Because the model is compact, it is much easier to find any errors in the formulas or equations used. In processing this model, the AMPL modeling system will perform many syntax and consistency checks. When the data is provided, AMPL will also perform "subscript checking" wherever items are indexed over sets.

It should also be apparent from the diet model that AMPL is easy to learn. The syntax of expressions and statements is natural (closely akin to algebraic notation) and general. And as you create more complex models, you will find that AMPL has all the power you need. It allows you to define sets as flexibly as in algebra (with defining expressions, unions and intersections, etc.), expressions of almost arbitrary complexity, and indexing over any number of dimensions.

MORE FEATURES OF AMPL

In addition to its powerful sets and expressions, AMPL has the ability to more naturally express certain types of optimization models. For example, network models may be written in terms of their nodes and arcs. And if you have nonlinear functions which can be approximated by several piecewise-linear terms (allowing the model to be solved by a fast linear programming solver), you can easily write these terms using a special AMPL syntax.

SOLVER PERFORMANCE AND AMPL

AMPL is designed to handle large, complex problems efficiently. Problem setup for optimization is much faster in AMPL than in Excel spreadsheets. And AMPL actually performs some of the work common to most solvers before passing the problem to the solver you choose. It will tighten constraint bounds and eliminate redundant constraints automatically, so the solver has less work to do. For nonlinear models, AMPL can automatically compute partial derivatives for the objective and constraints. Compass's nonlinear solvers take advantage of this derivative information to greatly speed up the solution process. So solution can be much faster in AMPL, even if you're using the same solvers available for Excel!

WHAT AMPL DOESN'T DO

AMPL is not designed to "dress up" and present your data, as you would in your spreadsheet. Although it provides some basic control over display of numbers and text, and it can display multi-dimensional data in tabular form, AMPL doesn't use fonts, colors, borders or similar graphic elements to display data. Nor will it produce charts and graphs. With AMPL Plus, however, you can easily use a spreadsheet as a source of data and/or as a destination for optimization results -- so you can combine the benefits of AMPL with the strengths of Microsoft Excel (or your favorite spreadsheet program).

TO LEARN MORE ABOUT AMPL

The AMPL and AMPL Plus Modeling Systems, and the Frontline Systems Solvers for AMPL and AMPL Plus are sold and supported by Compass Modeling Solutions, Inc. To learn more about AMPL, ask Compass about a demo or evaluation version of the AMPL system. You may want to obtain a copy of the book AMPL: A Modeling Language for Mathematical Programming by Robert Fourer, David Gay and Brian Kernighan, published by International Thompson (available through bookstores or direct from Compass). Compass also offers intensive three-day training seminars where you can learn AMPL from experts in a hands-on environment. Contact Compass today to find out more about how you can take advantage of the power of AMPL.