AMPL Optimization Problem: To manage its excess cash over the next 12 months, a
ID: 3773439 • Letter: A
Question
AMPL Optimization Problem:
To manage its excess cash over the next 12 months, a company may purchase 1-month, 2-month or 3-month certificates of deposit from any of several different banks. The current cash on hand and amounts invested are known, while the company must estimate the cash receipts and expenditures for each month, and the returns on the different certificates.The company’s problem is to determine the best investment strategy, subject to cash requirements. (As a practical matter, the company would use the first month of the optimal solution as a guide to its current purchases, and then re-solve with updated estimates at the beginning of the next month.)
A. Form an AMPL Model for the above problem
B. Construct a Data file for the following:
Suppose that the company’s estimated receipts and expenses (in thousands of dollars) over the next 12 months are as follows:
month
receipt
expense
1
3200
200
2
3600
200
3
3100
400
4
1000
800
5
1000
2100
6
1000
4500
7
1200
3300
8
1200
1800
9
1200
600
10
1500
200
11
1800
200
12
1900
200
The two banks competing for the business are estimating the following rates of return for the next
12 months
CIT:
1
2
3
NBD:
1
2
3
1
0.00433
0.01067
0.01988
1
0.00425
0.01067
0.02013
2
0.00437
0.01075
0.02
2
0.00429
0.01075
0.02025
3
0.00442
0.01083
0.02013
3
0.00433
0.01083
0.02063
4
0.00446
0.01092
0.02038
4
0.00437
0.01092
0.02088
5
0.0045
0.011
0.0205
5
0.00442
0.011
0.021
6
0.00458
0.01125
0.02088
6
0.0045
0.01125
0.02138
7
0.00467
0.01142
0.02113
7
0.00458
0.01142
0.02162
8
0.00487
0.01183
0.02187
8
0.00479
0.01183
0.02212
9
0.005
0.01217
0.02237
9
0.00492
0.01217
0.02262
10
0.005
0.01217
0.0225
10
0.00492
0.01217
0.02275
11
0.00492
0.01217
0.0225
11
0.00483
0.01233
0.02275
12
0.00483
0.01217
0.02275
12
0.00475
0.0125
0.02312
C. Solve the resulting linear program. Use display to produce a summary of the indicated purchases.
month
receipt
expense
1
3200
200
2
3600
200
3
3100
400
4
1000
800
5
1000
2100
6
1000
4500
7
1200
3300
8
1200
1800
9
1200
600
10
1500
200
11
1800
200
12
1900
200
Explanation / Answer
Science is all about models and data — theories (models) that explain observed data and make predictions about data that may be observed later. Science makes engineering possible and has led to many developments that heavily influence modern human life. Many kinds of models are useful. Some involve mathematical structures, such as distributions or differential equations, to which one can devote lifetimes of study. Simpler models, involving only finite numbers of variables, equations, inequalities, and objectives and described by finitely many parameters and sets, have a surprisingly wide range of uses. When one studies a new area, choices for suitable models may be far from obvious, and it may be necessary to try many models. Statistics is largely about comparing candidate models and, particularly with exploratory data analysis, finding suitable ones. Algebraic modeling languages, such as the AMPL language considered in this paper, facilitate formulating, comparing, changing, and deriving results from a subset of the class of ‘‘simpler’’ models outlined above in which equations, inequalities, objectives and derived sets and parameters are expressed algebraically. In short, AMPL is focused on mathematical programming problems, such as constrained optimization problems of the form minimize f (x) (1a) s. t. c(x) u, (1b) with x I Rn and c: I R n I Rm, possibly with some components of x restricted to integer values.
AMPL Design Principles
AMPL is meant to make it easy to transcribe models from mathematical notation, such as one might write by hand on paper or white board, to the AMPL language. We sought to make the language both close to elementary algebraic notation and easy to enter on an ordinary computer keyboard. As explained below, AMPL was created at Bell Labs, in the then Computing Science Research Center, where such languages as C [26, 27], C++ [30], and awk [1, 2] had been created, so AMPL uses some of the same notational conventions as these languages, such as square brackets for subscripts. Models often have sets of variables and constraints, and AMPL allows one to have various kinds of subscripted entities. In model entities, such as constraints and objectives, all subscripting is explicit, in part to make meaning of these entities clear. AMPL is a declare-before-use language, so one can read a model from top to bottom without worrying about the meaning of something whose properties are given later. An AMPL model can represent a whole class of problems. For example, a linear objective might be specified by the declarations set S; var x{S} >= 0; param p{S}; minimize Cost: sum{i in S} p[i]*x[i]; in which the objective is named ‘‘Cost’’ and is a transcription of i S pi x i . Thus a model can involve sets (such as S) over which entities, such as parameters and variables, e.g., p and x, are indexed, and can be stated without regard to the values that its sets and parameters will have in a particular problem to be solved, i.e., an instance. The AMPL language consists of three sub-languages: one for declarations, such as the set, var, param, and objective (minimize) declarations above, a simplified language in ‘‘data sections’’ for giving values to sets and parameters, and a command language for modifying values, solving problems, and writing results in various ways. While AMPL permits commingling declarations and instance data, AMPL also makes it easy to separate pure models from instance data. AMPL does not solve problems by itself (except when AMPL’s problem simplifications — its presolve — result in a solved problem), but instead writes files with full details of the problem instances to be solved and invokes separate solvers. The AMPL/solver interface library [19], whose source is freely available, provides problem details to solver interfaces, which interact with particular solvers to find solutions and return them to AMPL. Often one needs to solve sequences of problems, with the solution of one problem providing data used in the next problem. Sometimes this involves updating set and parameter values. AMPL only instantiates or recomputes problem entities as needed, effectively using lazy evaluation to help speed up processing. While parts of the AMPL language are general purpose, other parts, such as the presolve phase and computation of reduced costs, are tailored to mathematical programming. AMPL is meant for use with both linear and nonlinear problems; its internal use of sparse data structures allows AMPL to be useful with some very large problem instances.
AMPL History
AMPL arose in part because of Karmarkar’s linear-programming algorithm [24]. At the time, there was much interest at the Computing Science Research Center in ‘‘little languages’’, e.g., for graphing data, solving least-squares problems, drawing figures, etc. While Karmarkar’s algorithm seemed to promise faster solutions of some linear programming problems, we thought a ‘‘little language’’ to express such problems would help make the algorithm useful in practice. I had known Bob Fourer since the mid 1970s, when we both worked at the NBER Computer Research Center in Cambridge, Massachusetts, where Bob had done his undergraduate work at MIT. He had subsequently obtained a Ph.D. at Stanford University under George Dantzig and had published a nice paper [10] arguing for modeling languages. Bob was now a professor at Northwestern University and, as I learned when I saw him at a meeting, was coming up for a sabbatical. My management arranged for Bob to spend his sabbatical at Bell Labs in the 1985-86 academic year, during which he, Brian Kernighan, and I worked on the first version of AMPL. (We were aware of GAMS [5], but GAMS was not yet generally available and, anyway, we thought we could do a better language design. Such other modeling languages as AIMMS [4] and MPL [28] came along later.) Brian wrote the first implementation of AMPL; I wrote a preprocessor to transform data sections to a simpler, now defunct, format for the original AMPL processor. Our first technical report on AMPL [13] appeared in 1987. In revised form, it eventually appeared in Management Science [14]. By then, I had written a new implementation to facilitate various extensions we had in mind, such as handling nonlinearities.
Since the late 1970s I had been aware of Kedem’s work [25] on forward automatic differentiation (AD), which provides a mechanical way to compute analytically correct derivatives, and I was thinking of adding such facilities to AMPL. I mentioned this to Andreas Griewank when I saw him in 1988 at the International Symposium on Mathematical Programming (ISMP) in Tokyo, and he told me about the more efficient ‘‘reverse’’ automatic differentiation. (He has subsequently written much more about AD; see [22] for pointers to AD history and [23] for more on AD in general.) Reverse AD computes a function and its gradient with work proportional to that of computing the function alone, whereas forward AD, like straightforward symbolic differentiation, can turn a function evaluation involving n arithmetic operations into a computation involving O(n 2 ) operations. Both avoid the truncation errors inherent in finite differences. Ever since the Tokyo ISMP, I have been a fan of reverse AD. AMPL itself uses reverse AD to compute nonlinear reduced costs, but most AD happens in the solver interface library. See [17] for more on first derivative computations in this regard and [18] for some details of finding and exploiting partially separable structure when doing Hessian (second derivative) computations. By the early 1990s we had enough material to write a book on AMPL [15]. We continued adding facilities to AMPL and added much new material to the second edition [16] of the book. The ‘‘dot-com bubble burst’’ of 2001 threw a monkey wrench into AMPL development, but did cause creation of the AMPL Optimization company. Eventually I went to work at Sandia National Labs in Albuquerque, New Mexico, where I worked on AMPL support after hours (and without pay). Brian became a professor at Princeton. The three co-authors continued to interact via E-mail. When we got an NSF SBIR grant for some new work on AMPL, I left Sandia to work for the AMPL company (and get some pay). Bob Fourer retired somewhat later from Northwestern University and now also works full time for the AMPL company.
Some Simple Declarations and Commands Here is a simple example of some declarations, commands, and a little data section: param p; param q = p + 10; data; param p := 2.5; display p, q; The third line is the data section, which gives a value to p that is used in the ‘‘display’’ command, which produces output p = 2.5 q = 12.5 Data sections are good for conveying single values as well as tables of data, but data sections have relaxed quoting rules and other simplifications that preclude the appearance of expressions. The ‘‘let’’ command, by contrast, can involve general expressions. For example, let p := 17; display p, q; gives p = 17 q = 27 Notice that q was automatically recomputed.
AMPL can be used in batch interactive mode (reading from a file) or interactive mode (reading from the standard input). Prompts are given in interactive mode. Doing the above exercise in interactive mode, one would see
ampl: param p;
ampl: param q = p + 10;
ampl: data;
param p := 2.5;
ampl: display p, q;
p = 2.5
q = 12.5
ampl: let p := 17;
display p, q;
p = 17 q = 27
Simple Sets
To illustrate some simple sets and an error, here is a continuation of the above interactive-mode session. ampl: set A; set B; ampl: set C = p .. q; ampl: display A; Error executing "display" command: no data for set A ampl: data; set A := a b c; set B := c d; ampl data: display A, B, C; set A := a b c; set B := c d; set C := 17 18 19 20 21 22 23 24 25 26 27; The prompt ‘‘ampl data:’’ indicates data-section mode; the ‘‘display’’ command causes AMPL to revert to model/command reading mode. Here are examples of some set operations:
ampl: display A intersect B, A union B;
set A inter B := c;
set A union B := a b c d;
display A diff B, A symdiff B;
set A diff B := a b;
set A symdiff B := a b d;
Iterated and Recursive Expressions
Often it is useful to use iterated expressions, such as iterated sums. Here are some iterated expressions and a recursive definition, illustrated with the help of ‘‘print’’ commands.
ampl: print sum {i in 1..4} i;
10
ampl: print prod {i in 1..4} i;
24
ampl: param fac{ i in 1..9 }
ampl? = if i == 1 then 1 else i*fac[i-1];
ampl: print max{i in 1..9}
ampl? abs(fac[i] - prod{j in 2..i} j);
0
ampl: display fac, {i in 1..9} prod{j in 2..i} j;
: fac prod{j in 2 .. i} j :=
1 1 1
2 2 2
3 6 6
4 24 24
5 120 120
6 720 720
7 5040 5040
8 40320 40320
9 362880 362880
;
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.