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.

---------------------------------------------------------------
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
---------------------------------------------------------------

---------------------------------------------------------------
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:

• Pick initial patterns sufficient to meet demand.
• Repeat
  • Solve the (fractional) cutting optimality problem.
  • Let price[i] equal Fill[i].dual for each pattern i.
  • Solve the pattern generation problem.
  • If the optimal value is < 0
    • then add a new pattern that cuts Use[i] rolls of each width i;
      
    • else find a final integer solution and stop.

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;
	   ...
	}

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;
	   ...
	}

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 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;

	let {i in WIDTHS} price[i] := Fill[i].dual;

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.

---------------------------------------------------------------
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;

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.

---------------------------------------------------------------
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
;
---------------------------------------------------------------

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

Figure 5. Other examples of the use of named problems in AMPL.

Defining named problems

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;

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;

	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];

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:

• A component-name, such as Cut or Fill, which refers to all components having that name.

• A subscripted component-name, such as Reduced_Cost[p], which refers to that component alone.

• An indexing-expression followed by a subscripted component-name, such as {i in ORIG} Supply[i,p], which refers to one component for each member of the indexing set (as in the display command).

	{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]))

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.

---------------------------------------------------------------

  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;

	problem Master: Artificial, Weight, Excess, Multi, Convex;

	drop Artificial; restore Total_Cost;
	fix Excess;

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;

A form of the reset command lets you undo any changes made to the definition of a problem. For example,

	reset problem Cutting_Opt;

Using named problems

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;

	problem Cutting_Opt;
	   option relax_integrality 1;

	problem Pattern_Gen;
	   option relax_integrality 0;

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];

	for {p in PROD} {
	   problem SubII[p];
	   ...
	}

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.

Displaying named problems

	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;

Use the show command to get a list of the named problems that you have defined:

	ampl: show problems;
	problems:   Cutting_Opt   Pattern_Gen

	ampl: display _PROBS;
	set _PROBS := Cutting_Opt Pattern_Gen;

	ampl: show Cutting_Opt, Pattern_Gen;  
	problem Cutting_Opt: Fill, Number, Cut;
	problem Pattern_Gen: Width_Limit, Reduced_Cost, Use;

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;

Defining and using named environments

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;

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]]

Numerical pitfalls in implementing algorithms

Controlling the output of a script