Using AMPL at CAEN

1. Set up AMPL environment:

Create a symbolic link to AMPL interactive solver by typing the following command line on any UNIX machine:

ln -s /afs/engin.umich.edu/group/engin/priv/ioe/ampl/ampl_interactive ampl

CPLEX is the default solver. In most cases, you won’t need other solvers. However if for some reason you would like to use other solvers, you must create a symbolic link for the solver before you can use it. Currently three additional solvers, osl, minos and alpo, are available.

ln -s /afs/engin.umich.edu/group/engin/priv/ioe/ampl/solvers_SunOS/osl osl

ln -s /afs/engin.umich.edu/group/engin/priv/ioe/ampl/solvers_SunOS/minos minos

ln -s /afs/engin.umich.edu/group/engin/priv/ioe/ampl/solvers_SunOS/alpo alpo

2. Starting and quitting AMPL

To invoke ampl, type ** ampl** in the directory where you created the symbolic link in 1. Then you type AMPL statements in response to the ampl: prompt, until you leave AMPL by typing

3. Example

A steel company must decide how to allocate next week’s time on a rolling mill. The mill takes unfinished slabs of steel as input, and can produce either of two semi-finished products, which we will call bands and coils. The mill’s two products come off the rolling line at different rates:

Tons per hour: Bands 200

Coils 140

and they also have different profitabilities:

Profit per ton: Bands $25

Coils $30

To further complicate matters, the following weekly production amounts are the most that can be justified in light of the currently booked orders:

Maximum tons: Bands 6,000

Coils 4,000

The question facing the company is as follows: if 40 hours of production time are available this week, how many tons of bands and how many tons of coils should be produced to bring in the greatest total profit?

While we are given numeric values for production rates and per-unit profits, the tons of bands and coils to be produced are as yet unknown. These quantities are the decision* variables* whose values we must determine so as to maximize profits. The purpose of the linear program is to specify the profits and production limitations as explicit formulas involving the variables, so that the desired values of the variables can be determined systematically.

In an algebraic statement of a linear program, it is customary to use a mathematical shorthand for the variables. Thus we will write X_{B} for the number of tons of bands to be produced, and X_{C} for tons of coils. The total hours to produce all these tons is then given by

(hours to make a ton of bands)X_{B }+ (hours to make a ton of coils)X_{C}

This number cannot exceed the 40 hours available. Since hours per ton is the reciprocal of the tons per hour given above, we have *constraint *on the variables:

(1/200)X_{B }+ (1/140)X_{C} <= 40

There are also production limits:

0 <= X_{B} <= 6000

0 <= X_{c} <= 4000

In the statement of the problem above, the upper limits were specified, but the lower limits were assumed – it was obvious that a negative production of bands or coils would be meaningless. Dealing with a computer, however, it is necessary to be quite explicit.

By analogy with the formula for total hours, the total profit must be

(profit per ton of bands)X_{B }+ (profit per ton of coils)X_{C}

That is, our objective is to maximize 25X_{B }+ 30X_{C}. Putting this all together, we have the following linear program:

Maximize 25X_{B }+ 30X_{C}

Subject to (1/200)X_{B }+ (1/140)X_{C} <= 40

0 <= X_{B} <= 6000

0 <= X_{c} <= 4000

Solving this linear program with AMPL just requires entering it into the computer and typing ** solve**:

> *ampl*

ampl: *var XB;*

ampl: *var XC;*

ampl: *maximize profit: 25 * XB + 30 * XC;*

ampl: *subject to time: (1/200) * XB + (1/140) * XC <= 40;*

ampl: *subject to B_limit: 0 <= XB <= 6000;*

ampl: *subject to C_limit: 0 <= XC <= 4000;*

ampl: *solve;*

MINOS 5.4: optimal solution found.

2 iterations, objective 192000

ampl: *display XB, XC;*

XB = 6000

XC = 1400

ampl:*quit; *

>

As in the algebraic form, the AMPL version specifies the decision variables, defines the objective, and lists the constraints. It differs mainly in being somewhat more formal and regular, to facilitate computer processing. Each variable is named in a var statement, and each constraint by a statement that begins with subject to and a name (time, B_limit) for the constraint. Multiplication requires an explicit * operator, and the less than or equal to relation is written <=.

After you have typed in the linear program, type solve to have AMPL translate it, send it to a linear program solver, and return the answer. A final command, display, is used to show the optimal values of the variables.

The message MINOS 5.4 directly following the solve command indicates that AMPL used version 5.4 of a solver called MINOS.

4. A linear programming model

The simple approach employed so far is helpful for understanding the fundamentals of linear programming, but you can see that if our problem were only slightly more realistic – a few more products, a few more constraints – it would be a nuisance to write down. And if the problem were subject to frequent change, either in form or merely in the data values, it would be hard to update as well.

If we are to progress beyond the very tinniest linear programs, we must adopt a more general and concise way of expressing them. This is where mathematical notation comes to the rescue. We can write a compact description of the general form of the problem, which we called a *model*, using algebraic notation for the objective function and the constraints. The following is a symbolic linear programming model.

Given: P, a set of products

a_{j} = tons per hour of product j, for each j in P

b = hours available at the mill

c_{j} = profit per ton of product j, for each j in P

u_{j} = maximum tons of product j, for each j in P

Decision variables: X_{j} = tons of product j to be made, for each j in P

Maximize:

Subject to:

Its components are fundamental to all models:

**Sets,**like the products**Parameters**, like to production and profit rates**Variables**, the values of which the solver is to determine- An
**objective function**, to be minimized or maximized **Constraints**that the solution must satisfy.

It might seem that we have made things less rather than more concise, since our model is longer than the original statement of the linear program. Consider what would happen, however, if the set P had 42 products rather than 2. The linear program would have 120 more data values; there would be 40 more variables, with new lower and upper limits for each; and there would be 40 more terms in the objective and the hours constraint. Yet the abstract model, as shown above, would be no different. Without this ability of a short model to describe a long linear program, larger and more complex instances of linear programming would become impossible to deal with.

A mathematical model like this is thus usually the best compromise between brevity and comprehension; and fortunately, it is easy to convert into a language that a computer can process.

5. The linear programming model in AMPL

The AMPL language is intentionally as close to the mathematical form as it can get while still being easy to type on an ordinary keyboard and process by a program. There are AMPL constructions for each of the basic components listed above – sets, parameters, variables, objectives, and constraints – and ways to write arithmetic expressions, sums over sets, and so on.

We will first five an AMPL model that resembles our algebraic model as much as possible, and then present an improved version that takes advantage of the language.

5.1 The Basic Model

For the basic production model, a direct transcription into AMPL would look like the following:

set P;

param a {j in P};

param b;

param c {j in P};

param u {j in P};

var X {j in P};

maximize profit: sum {j in P} c[j] * X[j];

subject to Time: sum {j in P} (1/a[j]) * X[j] <= b;

subject to Limit {j in P}: 0 <= X[j] <= u[j];

The keyword set declares a set name, as in

set P;

The members of set P will be provided in separate data statements, which we’ll show in a moment.

The keyword param declares a parameter, which may be a single scalar value, as in

param b;

or a collection of values indexed by a set. Where algebraic notation says that "there is an *a _{j} *for each

param a {j in P};

which means that a is a collection of parameter values, one for each member of the set P. Subscripts in algebraic notation are written with brackets in AMPL, so an individual value like *a _{j} *is written a[j].

The var declaration

var X {j in P};

names a collection of variables, one for each member of the set P, whose values the solver is to determine.

The objective function is given by the declaration

maximize profit: sum {j in P} c[j] * X[j];

The name profit is arbitrary; a name is required by the syntax, but any name will do. The precedence of the sum operator is lower than that of *, so the expression is indeed a sum of products, as intended.

Finally the constraints are given by

subject to Time: sum {j in P} (1/a[j]) * X[j] <= b;

subject to Limit {j in P}: 0 <= X[j] <= u[j];

The Time constraint says that a certain sum over the set P may not exceed the value of parameter b. The Limit constraint is actually a family of constraints, one for each member j in P: each X[j] is bounded by zero and the corresponding u[j].

The construct {j in P} is called an indexing expression. As you can see from our example, indexing expressions are used not only in declaring parameters and variables, but also in any context where the algebraic model does something "for each j in P" . Thus the Limit constraints are declared

subject to Limit {j in P}

because we want to impose a different restriction 0 <= X[j] <= u[j]for each different product j in the set P. In the same way, the summation in the objective is written

sum {j in P} c[j] * X[j]

to indicate that the different terms c[j] * X[j], for each different product j in the set P, are to be added together to compute the profit.

The layout of an AMPL model is quite free. Sets, parameters, and variables must be declared before they are used but can otherwise appear in any order. Statements end with semicolons. Upper and lower case letter are different, so time, Time, and TIME are three different names.

Our original two-variable linear program is one of the many LPs that are instances of this model. To specify it or any other such instance, we need to supply the membership of P and the values of parameters. In AMPL, there is a specific syntax for data supply. The following is the data for the basic production model.

set P := bands coils;

param: a c u :=

bands 200 25 6000

coils 140 30 4000 ;

param b := 40;

A set statement supplies the members (bands, coils) of set P, and a param table gives the corresponding values for a, c, and u. A simple param statement gives the value of b. AMPL provides a variety of options that let you list or tabulate parameters in conventional ways; but essentially you must provide the name of each set members over which a parameter is indexed, together with the associated value.

5.2. An improved model

We could go on immediately to solve the LP defined in previous section. Once we have written the model in AMPL, however, we need not feel constrained by all the conventions of algebra, and we can instead consider changes that might make the model easier to work with. The following are a possible "improved" version.

Model :

set PROD; # products

param rate {PROD} > 0; # tons produced per hour

param avail >= 0; # hours available in week

param profit {PROD}; # profit per ton

param market {PROD} >= 0; # limit on tons sold in week

var Make {p in PROD} >= 0, <= market[p]; # tons produced

maximize total_profit: sum {p in PROD} profit[p] * Make[p];

# Objective: total profits from all products

subject to Time: sum {p in PROD} (1/rate[p]) * Make[p] <= avail;

# Constraint: total of hours used by all

# products may not exceed hours available

Data:

set PROD := bands coils;

param: rate profit market :=

bands 200 25 6000

coils 140 30 4000 ;

param avail := 40;

The short "mathematical" names for the sets, parameters, and variables have been replaced by longer, more meaningful ones. The indexing expressions have become p in PROD , or just PROD in those declarations that do not use index p. The bounds on individual variables have been placed within their var declaration, rather than in a separate constraint; analogous bounds have been placed in the parameters, to indicate the ones that must be positive or nonnegative in any linear program derived from the model.

Finally, comments have been added to help explain the model to a reader. Comments begin with # and end at the end of the line. As in any programming language, judicious use of meaningful names, comments, and formatting helps to make AMPL models more readable and understandable.

At this point, we could show how the model and data of the improved version would be typed interactively, as before. But clearly such an approach in unworkable for models of any size. Instead the statements of a model and its data are placed in one or more files, which are read as pare of an AMPL session. Here is an example in which all of the model declarations have been put in a file called steel.mod, and the data specification has been put in steel.dat.

ampl: *model steel.mod;*

ampl: *data steel.dat;*

ampl: *solve;*

MINOS 5.4: optimal solution found.

2 iterations, objective 192000

ampl: *display Make;*

Make [*] :=

bands 6000

coils 1400

;

ampl: *display Make.lb, Make.ub, Make.rc;*

: Make.lb Make.ub Make.rc :=

bands 0 6000 4

coils 0 4000 7.10543e-15

;

ampl: *display Time;*

Time = 4200

The model and data commands each specify a file whose contents are to be read immediately, as if all of its lines had been typed at that point. In this example, we first read the model from steel.mod, then read the data from steel.dat. The use of two separate commands encourages a clean separation of model from data.

Once the model has been solved, we can show all of the optimal values of the variables Make[p], by typing ** display Make**. We also display several quantities associated with the variables Make. First there are lower bounds Make.lb and upper bounds Make.ub, then the "reduced costs" Make.rc. At the end of the example above, we have displayed the "dual values" or "shadow prices" associated with the Time constraint.