This section introduces a variety of AMPL features that help make algorithmic scripts easier to write, and that make more sophisticated scripts possible. [summary to come]
To use two models in this manner, a script must have some way of switching between one model and the other. After first indicating how switching can be accomplished using only previously defined AMPL features, we show how the same results can be accomplished more clearly and efficiently by use of new AMPL features for defining separately named problems and environments.
We illustrate these possibilities through a script for an elementary form of the "roll trim" or "cutting stock" problem, using a well-known procedure due to Gilmore and Gomory. In the interest of brevity, we give only a sketchy description of the procedure here; a detailed derivation and discussion can be found in Chapter 13 of Chvatal's text. (Vasek Chvatal, Linear Programming. New York: W.H. Freeman and Company, 1983.)
In a simple roll trim problem, we wish to cut up long raw widths of some commodity -- such as rolls of paper -- into a combination of smaller widths that meet given orders with as little waste as possible. This problem can be viewed as deciding, for each raw-width roll, where the cuts should be made so as to produce one or more of the ordered smaller widths. Expressing such a problem in terms of decision variables is awkward, however, and leads to an integer program very difficult to solve except for very small instances.
To derive a more manageable model, the Gilmore-Gomory procedure defines a cutting pattern to be any one feasible way in which a raw roll can be cut up. A pattern thus consists of a certain number of rolls of each ordered width, such that their total width does not exceed the raw width. If (as in Exercise 2-6) the raw width is 110", and there are demands for widths of 20", 45", 50", 55" and 75", then two rolls of 45" and one of 20" make an acceptable pattern, as do one of 50" and one of 55" (with 5" of waste). Given a list of these patterns, we can recast the roll-trim problem so that the decision variables are indexed over patterns. For each particular pattern, the associated variable represents the numbers of raw rolls to be cut using that pattern. The objective, naturally, is to cut as few raw rolls as possible while meeting all demands.
Figure 1 gives two simple linear programs that can work together to find an efficient roll-cutting plan. The cutting optimization problem (Figure 1a) finds the minimum number of raw rolls that need be cut, given a collection of cutting patterns that may be used. If we relax the integrality requirement on this problem -- so that the solution may involve fractions of a roll -- then the solver will return "dual values" or "prices" on the constraints Fill[i]. The concept of a price on a constraint is introduced briefly by Section 10.7 of the AMPL book, and at much greater length in any LP textbook. For present purposes, however, it is enough to know that, given these prices, there exists a pattern generation problem (Figure 1b) that does one of two things: either it finds a new pattern that can be used (in the cutting optimization) to reduce the number of raw rolls needed, or it determines that no such new pattern exists. The pattern generation problem is a particularly simple one-constraint integer linear program, known as a knapsack problem.
Figure 1a. A pattern-based model for the cutting optimization problem (cut.mod). Given a collection of patterns, it determines how many raw rolls to cut using each patterns, so as to minimize total raw rolls used.
--------------------------------------------------------------- param roll_width > 0; # width of raw rolls set WIDTHS; # set of widths to be cut param orders {WIDTHS} > 0; # number of each width to be cut param nPAT integer >= 0; # number of patterns set PATTERNS := 1..nPAT; # set of patterns param nbr {WIDTHS,PATTERNS} integer >= 0; check {j in PATTERNS}: sum {i in WIDTHS} i * nbr[i,j] <= roll_width; # defn of patterns: nbr[i,j] = number # of rolls of width i in pattern j var Cut {PATTERNS} integer >= 0; # rolls cut using each pattern minimize Number: # minimize total raw rolls cut sum {j in PATTERNS} Cut[j]; subj to Fill {i in WIDTHS}: sum {j in PATTERNS} nbr[i,j] * Cut[j] >= orders[i]; # for each width, total # rolls cut meets total orders ---------------------------------------------------------------
Figure 1b. A knapsack model for the pattern generation problem (cut.mod, continued). Given values price[i] generated by the cutting optimization problem (with integrality relaxed), it looks for a pattern that may be added to reduce the number of raw rolls required.
--------------------------------------------------------------- param price {WIDTHS} default 0.0; # prices from cutting opt var Use {WIDTHS} integer >= 0; # numbers of each width in pattern minimize Reduced_Cost: 1 - sum {i in WIDTHS} price[i] * Use[i]; subj to Width_Limit: sum {i in WIDTHS} i * Use[i] <= roll_width; ---------------------------------------------------------------
We can search for a good cutting plan by solving these two
problems repeatedly in alternation. First the cutting optimization
problem generates some prices, then the pattern generation problem
uses the prices to generate a new pattern, and then the procedure
repeats with the collection of patterns extended by one. We stop
repeating when the pattern generation problem indicates that no new
pattern can lead to an improvement. We then have the best possible
solution in terms of (possibly) fractional numbers of raw rolls cut.
We may make one last run with the integrality restriction restored, to
get the best integral solution using the patterns generated, or we may
simply round the fractional numbers of rolls to the nearest integers
if that gives an acceptable result.
This is the Gilmore-Gomory procedure. In outline, its steps may be described as follows:
An implementation as an AMPL script is shown in Figure 2. The statement model cut.mod at the very beginning reads a file that contains both the cutting optimization and pattern generation models from in Figure 1. Since these models have no variables or constraints in common, it would be possible to write the script with simple solve statements using alternating objective functions; in outline,
repeat { objective Number; solve; ... objective Reduced_Cost; solve; ... }If we took this approach, however, every solve would send the solver all of the variables and constraints generated by both models. Especially for larger and more complex iterative procedures, such as arrangement is inefficient and prone to error.
We could instead insure that only the immediately relevant variables and constraints are sent to the solver, by using AMPL's fix and drop commands to suppress the others. Then the outline of our loop would look like this:
repeat { unfix Cut; restore Fill; objective Number; fix Use; drop Width_Limit; solve; ... unfix Use; restore Width_Limit; objective Reduced_Cost; fix Cut; drop Fill; solve; ... }Before each solve, the previously fixed variables and dropped constraints must also be brought back, by use of unfix and restore. This approach is efficient, but it remains highly error-prone, and makes scripts difficult to read.
As an alternative, therefore, AMPL allows alternative models to be distinguished by use of the new problem statement seen in Figure 2:
problem Cutting_Opt: Cut, Fill, Number; option relax_integrality 1; problem Pattern_Gen: Use, Width_Limit, Reduced_Cost; option relax_integrality 0;The first statement defines a problem named Cutting_Opt that consists of the Cut variables, the Fill constraints, and the objective Number. This statement also makes Cutting_Opt the current problem; uses of the AMPL var, minimize, maximize, subject to, and option statements now apply to this problem only. Thus by setting option relax_integrality to 1 above, for example, we assure that the integrality condition on the Cut variables will be relaxed whenever Cutting_Opt is current. In a similar way, we define a problem Pattern_Gen that consists of the Use variables, the Width_Limit constraint, and the objective Reduced_Cost; this in turn becomes the current problem, and this time we set relax_integrality to 0 because only integer solutions to this problem are meaningful. (The next subsection gives more detailed rules for how a problem and its environment can be defined and made current.)
The for loop in Figure 2 creates the initial cutting patterns, after which the main repeat loop carries out the Gilmore-Gomory procedure as described previously. The statement
solve Cutting_Opt;acts both to restore Cutting_Opt as the current problem, along with its environment, and to solve the associated linear program. Then we say
let {i in WIDTHS} price[i] := Fill[i].dual;to assign the optimal dual prices from Cutting_Opt to the parameters price[i] will be used by Pattern_Gen. All set and parameter data is global in AMPL, so that it can be referenced or changed whatever the current problem.
The second half of the main loop makes problem Pattern_Gen and its environment current, and sends the associated integer program to the solver. If the resulting objective is sufficiently negative, the pattern returned by the Use[i] variables is added to the data that will be used by Cutting_Opt in the next pass through the loop. Otherwise no further progress can be made, and the loop is terminated.
Figure 2. A script to implement to Gilmore-Gomory procedure for the cutting-stock problem, using the problem statement and other new AMPL features (cut.run).
--------------------------------------------------------------- model cut.mod; data cut.dat; option solver cplex; option solution_round 6; problem Cutting_Opt: Cut, Number, Fill; option relax_integrality 1; problem Pattern_Gen: Use, Reduced_Cost, Width_Limit; option relax_integrality 0; let nPAT := 0; for {i in WIDTHS} { let nPAT := nPAT + 1; let nbr[i,nPAT] := floor (roll_width/i); let {i2 in WIDTHS: i2 <> i} nbr[i2,nPAT] := 0; }; repeat { solve Cutting_Opt; let {i in WIDTHS} price[i] := Fill[i].dual; solve Pattern_Gen; if Reduced_Cost < -0.00001 then { let nPAT := nPAT + 1; let {i in WIDTHS} nbr[i,nPAT] := Use[i]; } else break; }; option Cutting_Opt.relax_integrality 0; solve Cutting_Opt; display nbr; display Cut; ---------------------------------------------------------------
The script concludes with the following statements, to solve
for the best integer solution using all patterns generated:
option Cutting_Opt.relax_integrality 0; solve Cutting_Opt;The expression Cutting_Opt.relax_integrality stands for the value of the relax_integrality environment in the Cutting_Opt environment. We discuss these kinds of names and their uses at greater length in the next section.
As an example of how this works, Figure 3 shows data for cutting 100" raw rolls, to meet demands of 48, 35, 24, 10 and 8 for finished rolls of widths 20, 45, 50, 55 and 75, respectively. Figure 4 shows the output that occurs when Figure 2's script is run with the model and data as shown in Figures 1 and 3. The best fractional solution cuts 46.25 raw rolls in five different patterns, using actually 48 rolls if the fractional values are rounded up to the next integer. The final solve shows that six of the patterns can be combined to meet demand using only 47 raw rolls.
Figure 3. Data for the cutting-stock model (cut.dat).
--------------------------------------------------------------- param roll_width := 110 ; param: WIDTHS: orders := 20 48 45 35 50 24 55 10 75 8 ; ---------------------------------------------------------------
--------------------------------------------------------------- ampl: include cut.run CPLEX 2.1: All rows and columns eliminated. CPLEX 2.1: optimal solution; objective 52.1 0 iterations CPLEX 2.1: optimal integer solution; objective -0.2 17 simplex iterations 18 branch-and-bound nodes CPLEX 2.1: optimal solution; objective 48.6 3 iterations (2 in phase I) CPLEX 2.1: optimal integer solution; objective -0.2 20 simplex iterations 19 branch-and-bound nodes CPLEX 2.1: optimal solution; objective 47 5 iterations (3 in phase I) CPLEX 2.1: optimal integer solution; objective -0.1 23 simplex iterations 19 branch-and-bound nodes CPLEX 2.1: optimal solution; objective 46.25 7 iterations (4 in phase I) CPLEX 2.1: optimal integer solution; objective -1e-06 28 simplex iterations 44 branch-and-bound nodes nbr [*,*] (tr) : 20 45 50 55 75 := 1 5 0 0 0 0 2 0 2 0 0 0 3 0 0 2 0 0 4 0 0 0 2 0 5 0 0 0 0 1 6 1 2 0 0 0 7 1 0 0 0 1 8 3 0 1 0 0 ; Cut [*] := 1 0 2 0 3 8.25 4 5 5 0 6 17.5 7 8 8 7.5 ; CPLEX 2.1: optimal integer solution; objective 47 11 simplex iterations 4 branch-and-bound nodes Cut [*] := 1 2 2 0 3 10 4 5 5 0 6 18 7 8 8 4 ; ---------------------------------------------------------------Figure 4. Output generated from execution of Figure 2's cutting-stock script.
We have developed other examples, listed in Figure 5, that
show how AMPL can iterate between models to implement well-known
iterative schemes including Dantzig-Wolfe decomposition, Benders
decomposition, and Lagrangian relaxation. The Dantzig-Wolfe examples
in particular show how more than two named problems can be involved.
Script | Uses | Implements |
---|---|---|
cut1.run | cut1.mod cut.dat | Gilmore-Gomory column generation procedure for the cutting-stock (roll trim) problem |
cut2.run | cut2.mod cut.dat | Same as cut1.run, but using an alternative arrangement wherein problems are defined immediately before before their members are declared |
cut3.run | cut1.mod cut.dat | Same as cut1.run, but with better formatting of output |
multi1.run | multi1.mod multi1.dat | Dantzig-Wolfe decomposition for a multi-commodity transportation problem, using a single subproblem |
multi2.run | multi2.mod multi2.dat | Same as multi1.run, but using a separate subproblem for each product; subproblems represented in AMPL by an indexed collection of named problems |
multi3.run | multi3.mod multi3.dat | Same as multi2.run, except that the separate subproblems are realized by changing the data to a single AMPL named problem |
stoch1.run | stoch1.mod stoch.dat | Benders decomposition for a stochastic programming variant of a multi-period production problem (see Exercise 4-5) |
stoch2.run | stoch2.mod stoch.dat | Same as stoch1.run, but using a separate subproblem for each scenario; subproblems are represented in AMPL by an indexed collection of named problems |
stoch3.run | stoch3.mod stoch.dat | Same as stoch2.run, except that the separate subproblems are realized by changing the data to a single AMPL named problem |
trnloc1d.run | trnloc1d.mod trnloc1.dat | Benders decomposition for a location-transportation problem |
trnloc1p.run | trnloc1p.mod trnloc1.dat | Same as trnloc1d.run, but using a primal rather than dual formulation of the subproblem |
trnloc2a.run | trnloc2a.mod trnloc2.dat | Lagrangian relaxation for a location-transportation problem |
trnloc2b.run | trnloc2b.mod trnloc2.dat | Same as trnloc2a.run, but model has upper limits on the Ship variables to give better lower bounds on the objective |
trnloc2c.run | trnloc2c.mod trnloc2.dat | Same as trnloc2b.run, but model has 0-1 constraints disaggregated to give better LP relaxation |
AMPL offers a variety of commands for working with named problems, based in many cases on the forms and commands already used for other purposes. We consider first the several ways to define named problems, and then survey the commands for using and displaying them.
You can define a problem most straightforwardly through a problem command that gives the problem's name and its list of components. Thus in Figure 2 we have:
problem Cutting_Opt: Cut, Number, Fill;A new problem named Cutting_Opt is defined, and is specified to contain all of the Cut variables, the objective Number, and all of the Fill constraints from the model in Figure 1. At the same time, Cutting_Opt becomes the current problem. Any fixed Cut variables are unfixed, while all other declared variables are fixed (at their current values). The objective Number is restored if it had been previously dropped, while all other declared objectives are dropped; and similarly any dropped Fill constraints are restored, while all other declared constraints are dropped.
For more complex models, the list of a problem's components typically includes several collections of variables and constraints, as in this example from stoch.run:
problem Sub: Make, Inv, Sell, Stage2_Profit, Time, Balance2, Balance;By specifying an indexing-expression after the problem name, you can define an indexed collection of problems, such as these in multi2.run:
problem SubII {p in PROD}: Reduced_Cost[p], {i in ORIG, j in DEST} Trans[i,j,p], {i in ORIG} Supply[i,p], {j in DEST} Demand[j,p];For each p in the set PROD, a problem SubII[p] is defined. Its components include the objective Reduced_Cost[p], the variables Trans[i,j,p] for each combination of i in ORIG and j in DEST, and the constraints Supply[i,p] and Demand[j,p] for each i in ORIG and each j in DEST, respectively.
In general, a problem declaration's form and interpretation somewhat resemble those of the display command (Section 10.3). The declaration begins with the keyword problem, a problem-name not previously used for any other model component, an optional indexing-expression (to define an indexed collection of problems), and a colon. Following the colon is the comma-separated list of variables, objectives and constraints to be included in the problem. This list may contain items of any of the following forms, where "component" refers to any variable, objective or constraint:
{i in ORIG} Supply1[i,p], {i in ORIG} Supply2[i,p], {i in ORIG, j in DEST} Trans[i,j,p], {i in ORIG, j in DEST} Use[i,j,p] {i in ORIG} (Supply1[i,p], Supply2[i,p]), {i in ORIG, j in DEST} (Trans[i,j,p], Use[i,j,p]) {i in ORIG} (Supply1[i,p], Supply2[i,p], {j in DEST} Trans[i,j,p], {j in DEST} Use[i,j,p]) {i in ORIG} (Supply1[i,p], Supply2[i,p], {j in DEST} (Trans[i,j,p],Use[i,j,p]))As these examples show, the list inside the parentheses may contain any item that is valid in a component-list, even an indexing-expression followed by another parenthesized list. This sort of recursion is also found in AMPL's function and print commands, but is more general than the list format allowed in display commands.
Any variables, objectives or constraints that you declare are automatically added to the current problem. Thus in our earlier example, all of Figure 1's model components are first placed by default into the problem Initial; then, when Figure 2's script is run, the components are divided into the problems Cutting_Opt and Pattern_Gen by use of problem statements. As an alternative, you can declare empty problems and then fill in their members through AMPL declarations. Figure 6 (cut2.mod) shows how this would be done for the Figure 1 models. The associated script (cut2.run) is similar to the previous one. This approach is sometimes clearer or easier for the simpler applications.
Figure 6. An alternative way of specifying the two named problems for Figure 1's the cutting-stock problem (cut2.mod). The associated script (cut2.run) is similar to the one previously shown.
--------------------------------------------------------------- problem Cutting_Opt; # ====================== param nPAT integer >= 0, default 0; param roll_width; set PATTERNS := 1..nPAT; set WIDTHS; param orders {WIDTHS} > 0; param nbr {WIDTHS,PATTERNS} integer >= 0; check {j in PATTERNS}: sum {i in WIDTHS} i * nbr[i,j] <= roll_width; var Cut {PATTERNS} >= 0; minimize Number: sum {j in PATTERNS} Cut[j]; subj to Fill {i in WIDTHS}: sum {j in PATTERNS} nbr[i,j] * Cut[j] >= orders[i]; problem Pattern_Gen; # ====================== param price {WIDTHS}; var Use {WIDTHS} integer >= 0; minimize Reduced_Cost: 1 - sum {i in WIDTHS} price[i] * Use[i]; subj to Width_Limit: sum {i in WIDTHS} i * Use[i] <= roll_width; ---------------------------------------------------------------
Any use of drop/restore or
fix/unfix (Section 10.8) also modifies the current
problem. The drop command has the effect of removing
constraints or objectives from the current problem, while the
restore command has the effect of adding constraints or
objectives. Similarly, the fix command removes variables
from the current problem and the unfix command adds
variables. As an example, multi1.run uses the following
problem statements,
problem MasterI: Artificial, Weight, Excess, Multi, Convex; problem MasterII: Total_Cost, Weight, Multi, Convex;to define master problems for phases I and II of its decomposition procedure. Instead it could specify
problem Master: Artificial, Weight, Excess, Multi, Convex;to define the master problem initially, and then
drop Artificial; restore Total_Cost; fix Excess;when the time comes to convert the master problem to a form appropriate for the second phase. With a similar change to the definition of the subproblem, one loop suffices to implement both phases as seen in multi1a.run.
Alternatively, the redeclare problem command can be employed to specify a new definition for a problem. The drop, restore, and fix commands above could be replaced, for instance, by
redeclare problem Master: Total_Cost, Weight, Multi, Convex;Like other declarations, however, this cannot be used within a compound statment (if, for or repeat) and so cannot be used in the multi1a.run example. (Other uses of the new redeclare keyword are discussed further in . . . ).
A form of the reset command lets you undo any changes made to the definition of a problem. For example,
reset problem Cutting_Opt;resets the definition of Cutting_Opt to the list of components in the problem statement that most recently defined it.
Any problem statement that refers to just one problem will make that problem current. As an example, at the beginning of the cutting-stock script we want to make first one and then the other named problem current, so that we can adjust certain options in the problems' environments. The problem statements in cut1.run (Figure 2),
problem Cutting_Opt: Cut, Number, Fill; option relax_integrality 1; problem Pattern_Gen: Use, Reduced_Cost, Width_Limit; option relax_integrality 0;serve both to define the new problems and to make those problems current. The analogous statements in cut2.run are simpler:
problem Cutting_Opt; option relax_integrality 1; problem Pattern_Gen; option relax_integrality 0;These statements serve only to make the named problems current, because the problems have already been defined by problem statements in cut2.mod (Figure 6).
A problem statement may also refer to an indexed collection of problems, as in the stoch.run example cited previously:
problem SubII {p in PROD}: Reduced_Cost[p], {i in ORIG, j in DEST} Trans[i,j,p], {i in ORIG} Supply[i,p], {j in DEST} Demand[j,p];This form defines potentially many problems. Subsequent declarations go into all of these problems, as long as the unsubscripted problem name is current. Subsequent problem statements can make members of a collection current one at a time, as in a loop having the form
for {p in PROD} { problem SubII[p]; ... }or in a statement such as problem SubII["coils"] that refers to a particular member.
As seen in previous examples, the solve statement can also include a problem-name, in which case the named problem is made current and then sent to the solver. The effect of a statement such as solve Pattern_Gen is thus exactly the same as the effect of problem Pattern_Gen followed by solve.
ampl: model cut1.mod; ampl: data cut.dat; ampl: problem; problem Initial; ampl: problem Cutting_Opt: Cut, Number, Fill; ampl: problem Pattern_Gen: Use, Reduced_Cost, Width_Limit; ampl: problem; problem Pattern_Gen;The current problem is always Initial until other named problems have been defined.
Use the show command to get a list of the named problems that you have defined:
ampl: show problems; problems: Cutting_Opt Pattern_GenThe predefined set _PROBS also contains these names:
ampl: display _PROBS; set _PROBS := Cutting_Opt Pattern_Gen;Also use show to see the variables, objectives and constraints that make up a particular problem,
ampl: show Cutting_Opt, Pattern_Gen; problem Cutting_Opt: Fill, Number, Cut; problem Pattern_Gen: Width_Limit, Reduced_Cost, Use;or indexed collection of problems.
Use expand to see the explicit objectives and constraints of the current problem, after all data values have been substituted:
ampl: expand Pattern_Gen; minimize Reduced_Cost: -0.166667*Use[20] - 0.416667*Use[45] - 0.5*Use[50] - 0.5*Use[55] - 0.833333*Use[75] + 1; s.t. Width_Limit: 20*Use[20] + 45*Use[45] + 50*Use[50] + 55*Use[55] + 75*Use[75] <= 110;See the Examining Models and Data section of this supplement for further discussion of expand. [[At present, expand can be applied only to the current problem.]]
Named environments are automatically defined and changed when you define and change named problems. We begin by describing this mode of operation, which is sufficient for many purposes. We then describe several alternatives that afford a greater degree of control over environments, by permitting them to be managed independently of problems.
When you use the problem statement as shown above, the current environment always has the same name as the current problem. Sprcifically, at the start of an AMPL session the current environment is named Initial, and each subsequent problem statement that defines a new named problem also defines a new environment having the same name. An environment initially inherits all the option settings that existed when it was created, but it may be changed to new option settings. Any subsequent problem or solve statement that changes the current problem also switches to the correspondingly named environment.
As an example, our script for the cutting stock problem (Figure 2) sets up the model and data and then proceeds as follows:
option solver cplex; option solution_round 6; problem Cutting_Opt: Cut, Number, Fill; option relax_integrality 1; problem Pattern_Gen: Use, Reduced_Cost, Width_Limit; option relax_integrality 0;Options solver and solution_round are reset (by the first two option statements) before any of the problem statements; hence their new settings are inherited by subsequently defined environments and are the same throughout the rest of the script. Next a problem statement defines a new problem and a new environment named Cutting_Opt, and makes them current. The ensuing option statement changes relax_integrality to 1. Thereafter, when Cutting_Opt is the current problem (and environment) in the script, relax_integrality will have the value 1. Finally, another problem and option statement do much the same for problem (and environment) Pattern_Gen, except that relax_integrality is set back to 0 in that environment.
The result of these initial statements is to guarantee a proper setup for each of the subsequent solve statements in the repeat loop. The result of solve Cutting_Opt is to set the current environment to Cutting_Opt, thereby setting relax_integrality to 1 and causing the linear relaxation of the cutting optimization problem to be solved. Similarly the result of solve Pattern_Gen is to cause the pattern generation problem to be solved as an integer program. We could instead have used option statements within the loop to switch the setting of relax_integrality, but with this approach we have kept the loop -- the key part of the script -- as simple as possible. The advantages of this approach can be much more pronounced in scripts for more complex algorithms.
To come:
[[qualified option name ... ]] [[optional "environ envname" in problem statement]] [[environ command -- define with optional assign]] [[show environments]]
Return to the AMPL update page.