A paper company produces raw rolls of paper of a very large width. It then cuts these rolls into narrower ones to meet customer orders. Thus it faces the problem of deciding how to make the cuts so as to fill orders as economically as possible.

The company addresses this problem by first generating a list of possible cutting patterns. Each pattern consists of a collection of narrow rolls that can all be cut from one raw roll. For example, if raw rolls are 200 cm wide and there are orders for rolls 45 cm, 80 cm, and 110 cm wide, then a possible pattern would consist of one 80 cm and one 110 cm (with 10 cm wasted); another could have two 45 cm and one 110 cm (with nothing wasted).

From this vantage, the problem is to decide how many rolls to cut according to each pattern, so that orders are met using as few raw rolls as possible. Data and variables for an optimization model to solve this problem can be written in AMPL as

set WID; # widths ordered

set PAT; # cutting patterns available

param ord {WID} >= 0; # orders for each width

param num {WID,PAT} >= 0; # times each width occurs in each pattern

var Cut {PAT} >= 0; # raw rolls to be cut using each pattern

The following parameters are also declared in the model:

param cst {PAT} >= 0; # a cost associated with cutting each pattern

param max_cst > 0; # the maximum total cutting cost allowed

param ovr {WID} >= 0; # an overrun factor for each ordered width

Write an AMPL minimize or subject to statement that implements each of the following parts of the problem: a: The objective that the total number of raw rolls cut is to be minimized.

b: The constraints that, for each i in WID, the total rolls of width i actually cut must be at least the number of that width ordered.

c: The constraints that, for each i in WID, the total rolls of width i actually cut may be at most the number of that width ordered times the specified overrun factor.

d: The constraint that the total of all costs associated with cutting all patterns must not exceed the maximum total cutting cost allowed.

Now imagine that the paper company is concerned not to change the cutting pattern too often. To adapt the previous model to handling changeovers, the model is extended by defining:

var Use {PAT} binary; # 1 for each pattern used

# 0 for each pattern not used

The following additional parameters are declared:

param maxdif > 0;	# maximum different patterns allowed
param minpat >= 0;	# minimum times any one pattern can be used, # if it is used at all

param maxpat {PAT} >= 0; # maximum times each pattern can be used

Write an AMPL subjectto statement that would implement each of the following constraints:

e: The total number of different patterns used, in filling all orders, must not exceed the maximum different patterns allowed.

f: For each pattern, if that pattern is not used, then the number of raw rolls cut using that pattern is zero.

g: For each pattern that does get used, it must be used at least the specified minimum number of times.