Reference

cations

AlllDM 3m3?b7

NBSIR 78-1539

Mathematical Models for

Selecting Catalogs of

Standard-Sized Items

Douglas R. Shier

Operations Research Division

Center for Applied Mathematics

National Engineering Laboratory

September 1978

ir

f

i

Report Prepared for: Building Economics and Regulatory

r Technology Division - QQ

rpntpr for Building Technology

100

.U56

#73-1539

/^78

fcfcMlir-iH «*•***

liAY 1 1 WS

NBSIR 78-1539

J MATHEMATICAL MODELS FOR

SELECTING CATALOGS OF

STANDARD-SIZED ITEMS

Douglas R. Shier

Operations Research Division

Center for Applied Mathematics

National Engineering Laboratory

September 1978

Report Prepared for; Building Economics and Regulatory

Technology Division

Center for Building Technology

1

0

. (X'

‘

I / U.S. DEPARTMENT OF COMMERCE, Juanita M. Kreps, Secretary

Dr. Sidnay Harman, Und%r Sacftary

Jordan J. Baruch, Assistant Sacratary for Scianca and Tachnoiogy

NATIONAL BUREAU OF STANDARDS, Emast Amblar, Diractor
j

.
ABSTRACT

This report identifies and discusses various mathematical models for

selecting a "best" catalog of standard sizes. A survey of existing models

for continuous and discrete versions of the catalog selection problem

is presented. The advantages and disadvantages of such models are as- sessed with regard to both range of applicability and computational feasibility. This evaluation shows that a frequently-advocated iterative procedure may produce erroneous results and identifies another approach as the most promising. Various refinements and extensions are then proposed for this latter (discrete) model and its associated solution technique (dynamic prograjmning ) . In particular, a multidimensional version of

the catalog selection problem is formulated and analyzed. Areas for

further investigation, and Tinresolved issues, are also discussed.

Key Words : Catalog; dynamic programming; iterative procedure; models;

optimization; stability; standards.
ACKNOWLEDGMENTS

This work has greatly benefited from valuable discussions with Ward

Buzz ell, James Harris and Hans Milton (Building Economics and Regulatory

Technology Division, National Bureau of Standards). The author also

wishes to thank Dr. A. J. Goldman (Center for Applied Mathematics, NBS)

for providing encouragement and support. In addition, the technical

assistance of Christopher Jones and David Reid, summer workers with the

Center for Applied Mathematics, is gratefully acknowledged.
TABLE OF CONTENTS

Page

1. Introduction 1

2. Survey of Catalog Selection Problems 3

2.1 Models for the Continuous Problem 5

2.2 Models for the Discrete Problem ih

2.2.1 Fixed Number of Sizes ik

2.2.2 Optimal Number of Sizes l8

3. Assessment of Models 23

3.1 Solution Methods for the Continuous Problem 23

3.2 Solution Methods for the Discrete Problem 38

4. Refinements of Models for the Discrete Problem 45

4.1 Computational Observations 45

4.2 Extension to a Two-Dimensional Model 48

4.3 Estimation of Demands 5 6

5. Areas for Further Investigation 59

6. References 62

Appendix A; Stability Aspects of Iterative Procedures 64

Appendix B: Computational Refinement for the Wagner-Whitin Model.. TO
LIST OF FIGURES

Page

1. Demand Function for the Continuous Model 6

2. Demand Function for the Discrete Model 15

3. A Catalog Cost Function vith Several Local Minima 27

k. Demand Function for Example 1 30

5. Application of Lind’s Algorithm to Example 1, vith Starting

Value x^ = 1.5 31

6. Demand Function for Example 2 33

7. The Sets S, T and S x T for the Two-Dimensional Problem 50

0 8. The Index Set E 53

9. Approximating Demand Curve for Existing Sizes e^ 58
1. INTRODUCTION

This report concentrates on the formiilation and analysis of mathematical

models for selecting a "hest" catalog (or ensemble) of standard-sized

items. This situation can arise when a relatively small subset of

standard sizes for some design element or component must be used to meet

demands for a much larger number of potential sizes. The restriction to

this smaller subset of sizes might reasonably be dictated by limitations

of storage and economies of scale in manufacturing. The problem, then,

is to find which standard- si zed items should be produced (or stocked) in

order to meet forecasted demand at minimum cost.

One instance of this catalog selection problem arises in the stocking of

structural steel beams. On the basis of design calculations, the professional engineer may find that a beam possessing a certain section

modulus is required. Of course, it is unlikely that this precise section modulus will be available from an existing catalog of beam section

moduli, and so a steel beam from the catalog with a somewhat larger

section modulus than that required will be used. This larger section

modulus is assumed more costly (without conferring needed benefit)

than the smaller required section modulus. The problem in this context

is thus to select a catalog of beams with specified section moduli that

will adequately meet demand, while minimizing the relevant costs of

stocking such a catalog.

More generally, this framework appears appropriate whenever only some

of the possible sizes for an industrial product are to be stocked, and

demands for unstocked sizes are met by using a larger stocked size. Often,
existing catalogs for such products (e.g., windows, lumber, glass) reflect the historical evolution of standard industrial products and not a

deliberately rationalized selection of standard sizes. In such cases,

it would be useful to have an analytical method for selecting a catalog

of standard sizes that is in some sense "best". Quite likely, such a

method would suggest a streamlining in existing, and sometimes imnecessarily large, collections of standard- si zed products.

A precise statement of the catalog selection problem is provided in

Section 2, where a survey of existing models and alternative approaches

to the problem is presented. In Section 3, the advantages and disadvantages of the various approaches are assessed with regard both to range of

applicability and to computational feasibility. As a result of such assessments, one particular approach is shown to be treacherous and inadvisable for use, while another approach is recommended for actual implementation. Section H details the basic model associated with this recommended approach and shows how the basic model can be modified to allow

for a more flexible and realistic formiilation. In particular, a multidimensional version of the catalog selection problem is formulated and

analyzed. Computational aspects and input requirements to the model are

also discussed in this section. Areas for further investigation, and

unresolved issues, are addressed in Section 5*

2
2. SURVEY OF CATALOG SELECTION PROBLEMS

This section discusses a variety of different approaches taken in the

formulation and solution of catalog selection problems. As will soon

become apparent, this type of problem has in fact been studied in a

number of different guises by a number of different authors. The catalog

selection problem has been studied at times as an "assortment problem"

[ll], at other times as a "dynamic economic lot size problem" [l^], and

also as a "vehicle dispatching problem" [8]. Thus, it is not surprising

that authors studying one manifestation of the catalog selection problem

were often quite unaware of what authors studying a completely equivalent

manifestation had already discovered.

We shall first describe in some generality the important defining characteristics of a catalog selection problem. While a number of somewhat

different versions of the catalog selection problem have been examined

in the literature, virtually all such versions share certain basic

features

:

1. A catalog of "supply sizes" x^, x^, ..., x^ is to be chosen from

some set S of allowable sizes.

2. The underlying demand for each existing (or potential) size x from

the set S is known.

3. The demand for any size x can be met by any supply size x^ which

is at least as large as x. All demands must be met.

h. There is no limit to the demand that can be met by using a given

supply size.

3
5. Various costs are associated -with the selection of a catalog:

o the cost of failing to meet demand exactly,

o the cost of stocking the specified catalog of sizes.

Once a model incorporating the above featiares has heen formulated, two

distinct questions arise. First, what is the overall cost of a specified catalog and, second, what should he the composition of a catalog in

order to minimize the sum of all relevant costs? It is therefore important

for a model to permit the evaluation of a given catalog as well as the

construction of an optimal one.

Previous investigations considered two rather distinct versions of the

catalog selection problem, differing in whether the set S postulated

above represents a continuous interval (e.g., all sizes between some

lower and upper limits) or a discrete (finite) set of sizes. The first

case presents a continuous problem. Here, the sizes selected for the

catalog as well as the sizes which could conceivably be demanded come

from an Infinite set, and the demand function (defined over the set S) is

assumed to be a continuous function over this set. In the second case,

we have a discrete problem, where selected sizes and demanded sizes

arise from a finite set. The demand function here is accordingly a discrete function defined over this finite set.

Because the continuous and discrete versions of the catalog selection

problem are formulated in somewhat different terms (and also because

different analytical techniques are used to analyze the associated models).

4
ve shall discuss them separately here. Accordingly, Section 2.1 is

devoted to a survey of models for the continuous problem, while Section

2.2 focuses on models for the discrete problem.

2.1 Models for the Continuous Problem

Several models have been considered for the continuous version of the

catalog selection problem. The earliest such model was proposed by

Hanssmann [U] and it served as the basis for continuous models subsequently proposed.

The problem is to select a fixed number n (specified in advance)

of sizes , x_, ..., X which are to be chosen from the continuous

interval [a,b]. Sizes x which could potentially be demanded are also

located within this interval, and the known demand function, denoted by

f(x), is assumed to be a continuous function throughout the interval

[a,b]. A typical such function is depicted in Figure 1, where an arbitrary catalog {x^, x^, •••5 has also been indicated. The interpretation of the demand function f(x) is that the number of items demanded

with sizes between x and x + Ax is approximately f(x)Ax , for Ax small.

For simplicity, it is assumed that the catalog sizes are arranged so

that

a<x^<x_<...<x — <b.

1 — 2 — — n —

5
UJ

M

(/)

6

Figure

1.

Demand

Function

for

the

Continuous

Model
Since demand for any size x in the interval [a,h] must be met (using

a larger size if necessary), it follows that the largest size in a

catalog needs to be located at the right-hand endpoint of the interval,

whence x = b. n

In the model proposed by Hanssmann, the costs of stocking a given catalog are not explicitly considered. This omission is not invariably

serious. Indeed, if the cost K of stocking a particular size x^ does

not depend on the size x^ itself, then the total stocking cost for a

catalog with precisely n supply sizes is just nK. Since this stocking

cost will be the same for any catalog of n sizes, such a term can be

ignored when comparing different catalogs with n sizes. In this instance, then, the Hanssmann model is not unreasonable; extensions of

the model to deal with the situation of more general stocking costs are

discussed later.

The present model thus concentrates on the costs of failing to meet demand exactly. For example, if a size x is demanded but the next largest

size available from the catalog is x^, then an amount of excess material x^-x could be considered as "wasted". The objective of the Hanssmann model is to minimize the total "wastage" resulting from the use of

a catalog. More precisely, the total cost of a catalog {x^, x^ ..., x^}

is given by

X. n 1

C(x^, x^, ..., x^) = S [ / (x^-x) f(x)dx], (2.1)

7
where for convenience we define = a and set x = h. In the above

0 n expression, each bracketed term of the sum represents the total amount

of excess material that results from using catalog size x^ to satisfy

the demands for sizes x, where x. ^ < x < x.

.

By using (2.1), we can therefore evaluate the'icost of any specific

catalog {x^, x^, •••5

^

optimal catalog (i.e., one that minimizes

this overall cost) can also be found within the framework of this model.

In fact, since it is assumed that there is no limit to the demand that

can be satisfied by a size in the catalog, the techniques of differential calculus can be employed to find (at least in theory) an optimal

catalog having certain sizes x*, x*, . .

.

,

x*. Particular solution

techniques for this type of model are discussed and analyzed in Section

3.1.

It should be emphasized that the above model addresses the problem of

finding a catalog with exactly n sizes. As mentioned by Hanssmann, one

can repeatedly solve the continuous problem for various values of n. Using

information on the cost of stocking catalogs with different nimibers of

items, one could then detennine a best mmiber n* of sizes to be stocked,

as well as the particular sizes to be stocked.

An alternative approach found in the literature takes such stocking costs

into explicit account. Sadowski [ll] formulates a model identical to

Hanssmann' s, except that a stocking cost c(x^) is associated with

8
using size in the catalog. Equation (2.1) then "becomes

X. n 1 C(x^, x^, ..., x^) = Z [/ (x^-x) f(x)dx + c(x^)]. (2.2)

i=l X. ^ 1-1

By using this expression, the costs for a num"ber of proposed alternative catalogs can be evaluated. As before, differential calculus techniques can be employed to characterize an optimal catalog with n sizes.

Sadowski also proposed solving for an optimal catalog by using a technique known as (continuous) dynamic programming [2]. The relative

merits of these solution methods are discussed in Section 3.1. By

finding an optimal catalog for each fixed value of n, an overall optimal value n* can then be identified. That is, a value of n and a

catalog {x^, x^, ..., x^} can be found that minimizes the cost (2.2)

over all possible catalogs with any number of sizes.

A further generalization of the Sadowski model has recently been advanced by Lind [T]. Instead of considering the "wastage" to be simply

x^-x, a more general expression for wastage g(x^) - g(x) is used. Here,

g(x) refers to the specific per unit cost of producing an item of size x.

Since g(x) would realistically be an increasing function of the size x,

then g(x^) - g(x) represents the additional cost incirrred by using a

(possibly larger) stock size x^ instead of the demanded size x. In

this context, equation (2.2) becomes

X. n 1

C(x^, x^, ..., x^) = Z [/ (g(x^)-g(x)} f(x)dx + c(x^)]. (2.3)

i=l X. ^ 1-1

9
This expression can be used either for evaluating or for optimizing

catalogs with n sizes. Again, differential calculus has been proposed

as the basis of a solution technique. In order to find a best value

n* for n, Lind gives an approximate expression for the optimum number

of items in the catalog when all the stocking costs c(x^) = K, a constant independent of x^. Then the search for the overall optimum can

be confined to the vicinity of this approximate value.

The three models discussed so far were formulated with the example of

selecting an optimal catalog of (industrial) items in mind. For this

reason, the problem has often been referred to as the assortment problem

[ll]: that is, find a best assortment of sizes to meet demand at minimum cost. Quite independently of investigations into the assortment

problem, authors in the area of transportation were studying a seemingly

different problem known as the vehicle dispatching problem [8]. In

this latter problem, a given number n of vehicles are to be dispatched

from a central terminal over a given period of time. Moreover, the

vehicles are to be dispatched in order to minimize the total waiting

time of passengers (arriving at the terminal according to some predictable pattern).

As a matter of fact, these two problems are in all essential respects

the same. The basic identification that illustrates this equivalence

is the identification of sizes, chosen from some interval [a,b], with

10
departure times, also chosen from an interval [a,b]. The demand

function f(x) for sizes x could equally represent the arrival rate of

passengers at time x. Furthermore, just as a demanded size x can he

met hy a (possibly) larger size x^ , the arrival time x of a customer

cannot exceed the departure time x^ of the vehicle he will board.

Finally, the cost of failing to meet demand for a size exactly ("wastage") corresponds to the waiting time of a customer, and the stocking

cost of an item corresponds to the cost of operating a vehicle at a

particular time of day.

Historically, these two related lines of investigation remained virtually separate from one another. Accordingly, it is not surprising

to find that certain results obtained by authors working on one version

of the problem had actually been obtained earlier by investigators of

a different version. We shall therefore briefly indicate the contributions of transportation analysts to an understanding of the catalog

selection problem.

In particular, vom Saal [13] studied the case when there are a fixed

number of departures (sizes) and operating (stocking) costs are not

explicitly considered. The total cost for the departure schedule

{x^, x^, •••, x^} is therefore given by equation (2.l). A further

generalization of the cost structure of this model was also considered.

Namely, the cost associated with a delay (wastage) x^-x is allowed

to be a nonlinear function g(x^-x) of delay. Accordingly, the total

cost for a schedule {x^, x^, ..., x^} is given by

11
(2.U)

X. n 1

C(x^, x^, x^) = S [/ g(x^-x) f(x)dx].

i=l X. ^ 1-1

As in the other models of this section, calculus was proposed for use

in characterizing an optimal schedule with n departures. Generalizations

were considered when capacity constraints are imposed on the number of

passengers that can he transported by a vehicle, and when maximum/

minimum "headways" are imposed between vehicle departures. Such generalizations correspond in the assortment problem to relaxing Assumption U

(p. 3), and to insisting upon certain "spacing" requirements on the sizes

selected for a catalog.

Newell [8] also proposed models for scheduling a fixed number of vehicle

departures. In his basic model, the total cost of scheduling n departures

is given by an expression which is mathematically identical to equation

(2.1). In addition, Newell considered a model that took explicit account

of the vehicle costs c(x^), assumed to be independent of x^. For the

latter model, an approximation to the optimal niimber of dispatches

n* is derived. This approximation represents a somewhat more refined

estimate of n* than that given later (and independently) by Lind [7].

Newell also considered an extension of these models to the case where

capacity restrictions are imposed on the vehicles.

In all the models discussed here (whether for the assortment problem or

the vehicle dispatching problem), the quantities x^ are continuous

variables, freely ranging over some fixed interval of the real line.

Accordingly, the techniques of calculus can in theory be used to find

12
those sizes defining an optimal catalog. To calculate such sizes in

practice is, however, another matter. We postpone a discussion of

numerical solution methods until Section 3.1, and proceed to a description

of discrete models.

13
2.2 Models for the Discrete Prohlem

In this section, various models for versions of the discrete catalog

selection prohlem are surveyed. It is useful to consider first those

models predicated on a fixed mmiher n of sizes in the catalog. Subsequently, those models are considered which allow for the simultaneous

determination of both the optimal number of sizes and the optimal sizes

themselves

.

2.2.1. Fixed Number of Sizes

The model proposed by Wolfson [l6], and later reformulated by Cohen

[ 3 ], deals with selecting a fixed number (n) of sizes which are to be

chosen from a finite set S. Sizes that could potentially be demanded

also arise from this finite set. For simplicity, these potentially

demanded sizes (m in number) are denoted by S = s^, •••,

where s^ < s_ < ... < s . The demand for such sizes is specified by

the quantities d^, d^, •••, d^; namely, the demand (over the period of

interest) for items of the i-th size s. is equal to d. , as illustrated

1 1 in Figure 2.

Since the demand for any size has to be met, it again follows that the

largest size must be part of any optimal catalog. More generally,

the demand for size s. can be met by a (possibly) larger size s., with

^ J s. >_ s^. The problem of interest is that of selecting a subset of n

ik
LUQ

15

Figure

2.

Demand

Function

for

the

Discrete

Model
items (a catalog) from the set S of m items (vhere m > n). There is

assiimed to he no limit to the demand that can he fulfilled hy using a

size stocked in the catalog.

Under these assumptions, the cost of instituting a catalog -with sizes

s. , s. , s. can he expressed as 12 n

n

S [ j=lZ i. <k < J-1

(2.5)

where for convenience we define i^ = 0 and note that i^ = m. Each of the

above terms (s. - s ) can he interpreted as the (per unit) "excess

1 , IC J material" resulting from using the j-th catalog size s. instead of the

demanded size s . Thus, the quantity within brackets in equation (2.5)

iC represents the total excess material resulting from using the j-th catalog

size to satisfy all demands met by that size. The total cost for the

entire catalog is then simply the Siam of such costs for all sizes

in the catalog, as indicated by equation (2.5). Note that for this

case (fixed n) only the costs of failing to meet demand exactly are

considered. Stocking costs for the catalog are not explicitly

included in this model.

By using equation (2.5) one can directly evaluate the cost of any

specified catalog. An optimal catalog of n sizes (i.e., one that minimizes the cost expression given above) can be determined by a technique known as (discrete) dynamic programming [2]. The essential idea

16
of this technique is to solve a given prohlem by solving instead a

series of smaller subproblems. Details of performing such recursive

calculations are deferred to Section 3*2. Wolfson [l6] presented such a

procedure for finding an optimal catalog -with n sizes, and Cohen [3]

subsequently simplified the mechanics of Wolfson’ s method.

In order to find the best number of items in a catalog, Wolfson suggests

using a dynamic programming technique to solve the problem for various

values of n. As a matter of fact, dynamic programming is quite amenable

to these calculations. Indeed, the technique does not need to solve

from scratch each catalog problem with a different value of n, but can

effectively use the information obtained when solving for n sizes in

order to solve for n+1 sizes. Once the catalog problems have been

solved for various values of n, the cost (2.5) can be balanced against

the production and stocking costs to define a best n* and a best catalog

of sizes.

The work by Wolfson and Cohen was subsequently extended by Jackson and

Zerbe [6] in two notable respects. First, the excess material cost

s. - s in equation (2.5) "was replaced by the more general cost difference

1 . K

J g(s. ) - g(s ), where g(s) can be viewed as the manufactTiring cost for

1 , iC J size s. Second, the possibility was allowed for certain sizes to be

"custom-made"; these represent catalog sizes that meet demand for only

IT
one particular size. The appropriate modification of equation (2.5)

to reflect these changes is straightforward, hut notationally cumbersome, and therefore is not shown here. Again, the solution technique

chosen for determining optimal catalogs was dynamic programming.

2.2.2 Optimal Number of Sizes

In all the models previously discussed, the method for finding the

overall best catalog of sizes to stock has (explicitly or implicitly)

been a two-step process. First, find an optimal catalog for a fixed

number of sizes n, and then vary the value of n parametrically to find

the best value n*. As a result, one obtains the optimal number of sizes

to stock and the optimal catalog having this mnnber of sizes. The

catalog thus obtained will minimize the relevant costs over all possible

choices of catalogs with any number of sizes.

In the models presented in this section, the optimal value n* as well

as the (overall) optimal catalog can be found directly , without solving

for each value of n separately. Moreover, the work involved in solving

this seemingly more difficult problem turns out to be less than that

needed to solve any particular "fixed n" problem.

The first model of this type was proposed by Wagner and Whitin [l4].

As in the case for a fixed number of sizes (Section 2.2.1), demands

d^12m , d_, ..., d are given for sizes in some finite set S = {s^12, s_, ...,

s }, with s^ < s^ < . . . < s . The problem here is to select a best

m 12 m

18
subset of sizes to form an optimal catalog. This optimal catalog is

one which minimizes the sum of all costs associated with the catalog:

namely, the costs of failing to meet demand exactly as well as the

costs of stocking the catalog.

More specifically, the total cost of a catalog {s. , s. , ..., s. }

^1 ^2 ^n

under the Wagner-Whitin model is given by

n C(i^, ig, i^) = Z [k^ + E c^

^ d^], (2.6)

j=l 0 l._^ < r < i. ’ j

where it is assumed i^On= 0 and i = m. In the above formulation, k.t

represents the cost of stocking size s^, and c^^ represents the per unit

substitution cost in using size s to meet demand for size s ( r <_ t )

.

The classification into these two types of costs is made so as to reflect the fact that certain costs (substitution) depend on the number

of units demanded, while other costs (stocking) are fixed costs, independent of demand. Accordingly, a (possibly nonzero) term c d is

O Xi L» included in (2.6) to allow for certain quantity-sensitive costs in producing or inventorying size s_^.

Equation (2.6) thus allows evaluation of the costs of alternative catalogs that may be proposed. In addition, an optimal catalog (one that

minimizes this cost expression over all possible catalogs) can be found,

again by using the technique of (discrete) dynamic programming. The

details of such calculations are deferred to Section 3.2.

19
Equation { 2 . 6 ) reveals that an optimal catalog will he one that manages

to balance the stocking costs against the substitution costs. The former

costs increase with increasing n, while the latter costs decrease with

increasing n. It is reasonable, then, that for some intermediate value

of n (not too large and not too small) the total contribution of such

costs will be minimized.

It should be noted that the problem actually considered by Wagner and

Whitin was not one of finding a best collection of sizes (the assortment

problem). Rather, these authors were concerned with another problem,

the dynamic economic lot size problem , which is in all important respects equivalent to the assortment problem. In brief, this problem

refers to the selection of ordering points in time for a particular item.

There are m discrete time periods at which orders could be placed;

\

* during each time period there is a known demand for the item and this

demand draws down the existing inventory. In order that demands can

always be filled from existing inventory, the inventory will have to

be replenished at certain points in time. The problem is thus to determine such ordering points (as well as the amounts ordered) in order

to balance the inventory costs of holding quantities of the item in

storage against the (fixed) cost of placing an order. Furthermore, both

the inventory and ordering costs can vary from period to period.

The equivalence of this problem to the assortment problem can be

seen by identifying catalog sizes with the ordering times. Also, the

20
stocking and substitution costs correspond, respectively, to the

ordering and inventory costs of the economic lot size problem. Fixrthermore, the assumption that demand for a given size can be met by a larger

size corresponds to the notion that inventory ordered in one period

can be used to meet demand in subsequent periods.

Several generalizations of the Wagner-Whitin model have been subsequently proposed. Most notably, Zangvill [17] considered the possibility of allowing the stocking and substitution costs to be more

general nonlinear functions. In addition, the possibility of "backlogging"

was considered - that of allowing the current inventory to drop

below zero. This corresponds in the assortment problem to allowing a

smaller size to be used to fulfill demand for a given size, but at an

additional cost.

In parallel with such developments of the economic lot size problem,

similar models were being proposed for discrete versions of the assortment problem, where n is not required to be fixed. Independently of

Wagner and Whit in, and at just about the same time, Sadowski [ll]

considered a model similar to that described by (2.6). Sadowski 's

model was proposed in order to allow for capacity restrictions on the

demand that could be met by a given item in the catalog. (As will be

discussed in Section 3.1, such capacity restrictions cannot be easily

incorporated into solution techniques for continuous models.) The

work of Sadowski was subsequently generalized by Pentico [9, 10 ], who

considered more general structures for the stocking and substitution costs.

21
Pentico also considered a variant of the assortment problem where the

demands are not known in advance, hut vary according to known (and

independent) probability distributions.

In addition, the same basic models have been studied (again, independently) by authors in connection with vehicle dispatching problems. In

particular. Ward [15 ] considered a series of models for this problem,

including models with constant stocking costs, and (a) linear substitution costs, (b) nonlinear substitution costs, (c) differing capacities, and (d) probabilistic demand. In these, as well as the other

models considered in this section, the indicated method of solution

was by dynamic programming.

To summarize, the models of Section 2 have been classified into those

dealing with continuous catalog selection problems and those dealing

with discrete catalog selection problems. For models in the first

class, the techniques of differential calculus are appropriate in determining optimal catalogs. By contrast, for models of the second typ

dynamic programming emerges as the appropriate computational tool.

Accordingly, the following section will address the relative merits of

alternative models by studying the properties of their associated solution methods.
3. ASSESSMENT OF MODELS

In this section we will study the properties of solution methods for

hoth the continuous and discrete versions of the catalog selection problem. This study will provide valuable information about the range of

applicability and computational feasibility of the associated models.

First, solution methods for the continuous catalog selection problem

will be investigated, followed by a discussion of solution methods for

the discrete problem.

3.1 Solution Methods for the Continuous Problem

We choose the model described by equation (2.2) to illustrate how the

techniques of differential calculus have been used to study optimal catalogs for the continuous problem. Thus, it is required to find a catalog

(with a fixed number of sizes n) that minimizes (2.2):

X. n 1 C(x^, Xg, . . . , x^) = T. [ f (x^-x) f(x)dx + c(x^)].

i=l X. ^ 1-1

Because the catalog sizes x^, x^, are subject to no essential

constraints, the minimizing values x*, x*, ..., x* can be found by differentiating the above cost expression with respect to each x^ and

setting the result equal to zero. This procedure yields the following

set of equations that must be satisfied at x*, x*, ..., x* for i =

1, 2, ..., n-1:

X .1 c'(x^) + / f(x)dx - f(x^) = 0, ( 3 . 1 )

23
where On= a and x = h. In the above expression, c'(x.) denotes the

1 derivative of c(x), evaluated at x = x^.

Equation (3.1) can also he rewritten, assuming f(x^) 7^ 0, in the

following form:

, X. ^ '

) f(x)dx}. ( 3 . 2 ) " ^i-1

In the case that f(x) > 0 and c'(x) ^ 0, the above relation can be used

to show that > x^ , as desired. These two stipulations mean that

demand is always positive and the stocking cost is a nondecreasing

function of size stocked.

Several authors [U, 7,8, 11, 13] have used (3.2) as the basis of an

iterative scheme to solve the nonlinear equations (3.1) for x*, x*,

..., X*. Namely, one guesses a trial value for x^ and then uses (3.2)

with i = 1 and x^ = a in order to obtain a value for x^. This value

of x^, together with the assumed value for x^, is then used in (3.2)

with i = 2 to produce a value for x^. The process is repeated until

X, , x^, ..., X , X have been successively calculated. Of course,

4’ 5

’ ’ n-1 n an optimal catalog must have x^ = b; however, the value obtained for

x^ by repeatedly applying (3.2) can certainly differ from b. It has

therefore been suggested [4,7] that if x^ exceeds b, the trial value

x^ should be reduced and the process should be started again with this

new trial value. On the other hand, if x is less than b, the process

n

is begun with an increased value of x^. Through successive iterations

24
of this procedure, the discrepancy between and b is expected to be

reduced. Accordingly, the iterative process will be terminated once

lx - b 1 is small enough

.

' n

'

For example, Lind [T] suggested the following procedure for obtaining

an optimal catalog.

LIND'S ALGORITHM

LI. Select x^.

L2. Use ( 3 . 2 ) to calculate successively x^, x^, ..., x^.

L3. If 1 x^-b I < e, where e is a small pre-specified "tolerance",

STOP. Otherwise, calciilate z=x,Inn - —(x -b) and using x^=z

1

return to Step L2.

In addition to being s\ii table for computer calculation, an iterative

algorithm such as the above can be implemented [T»8] in the form of a

graphical algorithm, suitable for hand calculation.

Let us now summarize and evaluate the efficacy of the above solution

procedures. First, it must be emphasized that equation (3.1) is only

a first-order condition defining the optimal x*, x*, ..., x*. Namely,

this equation will indeed be satisfied by any x^, x^, •••, x^ that

minimize C(x^, x^, will also be satisfied by any

values that maximi ze or define some other "critical point" of this

25
fiinction^. In other words, even should we he able to solve equation

( 3 . 1

)

, it is not at all clear that the x^, x^, •••, so determined

will actually minimize the catalog cost. However, if all solutions of

( 3 . 1 ) could be found, then one could search through these to find one

that minimizes C(x^12, x_, ..., x ). n

The difficulty, of course, is solving eqmtion ( 3 .I). Because it represents a highly nonlinear system of equations, it can be quite arduous

to determine a single solution, let alone the set of all solutions.

For this reason, several authors have reformulated ( 3 .I) as (3.2) and

then employed an iterative solution method (e.g., Lind’s algorithm) on

the latter system of equations.

However, as noted by Sadowski [ll], vom Saal [13] and Lind [T], there

still remain difficulties in identifying an optimal catalog. Indeed,

the solution produced by using such an iterative solution procedure

may in fact represent a local minimiom, but not a global minim\im of

the cost function. That is, it may be better than other catalogs

similar to it in composition, but it may still fail to be the best

catalog available. This possibility is illustrated in Figure 3,

which shows a hypothetical cost function C(x^, x^, x^) having

^Recall that when a function of a single variable has its first derivative set equal to zero, the sign of the second derivative must be

checked to see whether a (relative) minimum or maximum has been found.

The situation is even more complicated when n variables x ,

. .

.

,

x are Involved [l, p. 152]. ^ ^

26
LdN

if)

O I I

if) Oo

27

Figure

3.A

Catalog

Cost

Function

with

Several

Local

liinima
several local minima (at P, Q and R) , tut only a single global minimum

(at Q). In [ 13 ], vom Saal suggested that this difficulty could be

overcome by repeatedly using the iterative procedure to find all such

local minima, and then choosing the best from among these. Lind [T]

attempted to avoid such issues by investigating conditions under which

the iterative procedure generates a unique solution. In practice,

however, such conditions are not only extremely difficult to check,

but are also \inlikely to be satisfied.

Apart from the question of nonuniqueness, the possibility has also

been raised [ll] that the Iterative procediire might not even converge.

That is to say, is it assured that the sequence of values generated

by the procedure get closer and closer to b (see Step L3 of the Lind

algorithm)? Is such a procedure always guaranteed to terminate?

We now show, by means of simple examples, that the iterative procedure may not in fact converge. Moreover, it will also be demonstrated that even when the procedure does converge, it may fail to

reach the true (global) solution. These examples are constructed for

the simplest case when n = 2 and when there are no stocking costs:

c(x^) = 0 for i = 1,2. Clearly, the situation can only get worse

when n 2 and when more general cost structures are assumed.

Example 1 . Consider the problem of determining an optimal catalog

with n = 2 sizes, where the demand function is given by f(x) = e over

28
2

the interval [O, 1+ e ] = [ 0 , 8 . 389 ]. The demand function shown in

Figure U reflects the (not unrealistic) situation when larger sizes

are less in demand than smaller sizes of the same product. Because

the largest size in the catalog must be at the right-hand end of the

interval, x* = b = 8 . 389 . The problem then is to determine what value

of x^ will minimize (2.l) with x^ = b. It is straightforward to

verify that

"^1

C = C(x^) = + (b-x^)e + K,

where K is a constant independent of x^. Thus,

C’ (x^) = 1 - e (1 + b -x^)

and C'(2) = 0. It can easily be shown that the only solution of C'(x^)

0 is x^ = 2. Since C"(2) > 0, it follows that x^ = 2 is the unique

minimiam of C(x^) and so x* = 2, x* = b represents the optimal catalog

for n = 2.

When the Lind algorithm is applied to this problem, using a starting

value of x^ = 1.5, the results shown in Figure 5 are obtained. In

this figure, the dotted line represents the true value x* = 2; the

successive values of x^ obtained by Lind's algorithm are plotted for

each iteration (up to 25 iterations). It is clear that, even though

the starting value was close to x* = 2, the procedure yields wildly

oscillating values of x^, which do not seem to be settling down to the

true value x* = 2.

29
30

Figure

4.

Demand

Function

for

Example
X

31

Figure

5-

Application

of

Lind's

Algorithm

to

Example

1,

with

Starting

Value
It is shown in Appendix A that for this example the Lind procedure will

never converge. The difficulty here is that, while x* = 2 represents

the unique solution of (3.1), the iterative procedure cannot reach it.

More generally, if the procedure is started using any trial value in

[0,h] other than x^ = 2, the same type of divergent behavior will occur.

The reason is that the value x* = 2, the solution to (3-l), is unstable

with respect to the iterative scheme based on (3-2). That is, whenever

a given iteration value gets sufficiently close to x* = 2, the next

iteration value produced will be further from (rather than closer to)

~ The only instance for which the Lind procedure will converge is

when the trial value chosen happens to be precisely the true solution

x^ = 2, an extremely unlikely occurrence.

lo summarize, we have illustrated by way of a concrete example that

the Lind procedure will not always achieve convergence. Indeed, any

iterative procedure based on (3.2) will also suffer from this rather

serious defect. Even when convergence is assured, such iterative procedures can fail to converge to the correct solution, as the following

example illustrates.

Example 2 . Again we consider the problem of finding an optimal catalog

with n = 2 sizes, where the demand function is now given by f(x) =

3x -2.0Ux + O.U15 over the interval [0,l]. Figure 6 illustrates this

demand function. Since the right-hand end of the interval must be

the largest size in the catalog (x* = l), it is required then to find

a value of x^ that minimizes (2.1) with x^ = 1. It is readily verified

that

32
>

3

CM

0)

X

VD

0)

33

Demand

Function

for

Exampl
C(x^) = -x^(l-x^) (x^-1 . 02x^+0. 415 ) + K,

where K is a constant independent of x^. Upon differentiation one obtains

C’(x^) = Ux^ - 6.06x^ + 2.8Tx^ - 0.U15,

from which it can he determined that u = 0.2769, v = O.5265 and w =

0.7116 are the three solutions of C'(x^) = 0. Thus, equation (3.1)

possesses multiple solutions in this case. By examining second-order

conditions on the sign of C"(x^), it can he inferred that u and w are

local minima of C(x^), while v is a local maximum; the global minimum

is located at x^ = u. Accordingly, the optimal catalog for this

problem consists of x* = u, x* = 1.

However, when Lind’s algorithm is applied to this problem using a

starting value x^ = 0.6, the sequence of x^- values generated converges

to x^ = w. While this resultant value for x^ corresponds to a solution

of (3.1), it represents a local but not the global solution — a relative cost minim'um but not the absolute minimiim. If one attempts to

vary the starting value x^ (beginning, say, with any value x^ > v)

,

then the Lind procediire will always converge to x^ = w. If, on the other

hand, the procedure is begun with a starting value x^ (not equal to u)

with x^ < V, then the resulting sequence of x^-values does not converge.

Thus, no matter how hard one tries (by varying the starting value),

the Lind procedure will invariably fail to converge to the true solution

= u

.

X*

] 3h
Again, the reason for the failure of the Lind algorithm is related to

stability properties of the solutions to (3-1), as discussed in Appendix

A. It is shown there that x^ = u is in fact an unstable minimum,

while x^ = w is a stable minimum; x^ = v corresponds to an unstable

maximum. Thus, it is not surprising that when the Lind algorithm is

started with an x^-value near x^ = w, the process converges to x^ = w.

However, when the procedure is begun with an x^-value near x^ = u, the

process will not even converge.

To summarize, this second example illustrates the fact that the Lind

iterative procedure may not converge for certain starting values. Even

when it does converge, the convergence need not be to the true cost

minimum. This treacherous behavior is a serious drawback to the use

of the Lind procedure, and it applies as well to other proposed iterative

procedures based on (3.2).

With the above analysis in hand, it is now possible to assess the advantages and disadvantages of models for the continuous problem. First,

equations (3.1) represent only first-order conditions on the required

solution, and do not in general uniquely characterize the optimal catalog.

These equations can be highly nonlinear in nature and difficult to

solve. To find all solutions of (3.1) and then choose the best represents an extremely burdensome (as well as uncertain) computational task.

Second, if one instead devises an iterative procedure based on (3.2)

to determine an optimal catalog, convergence is not necessarily guaranteed, nor can one be confident (when convergence does occur) that the

answer obtained is a correct one.

35
Even if such technical difficulties could somehov he resolved, there

are other distinct disadvantages to using models formulated for the continuous problem:

1. Realistically, the given demands are discrete and not continuous. In order to obtain an analytic representation (an algebraically defined continuous function) for f(x), some additional

work is necessary to do curve-fitting with known analytic forms.

Not only will error be introduced by such a procedure, but any

irregularities in the underlying discrete demand will require the

use of a rather complex analytic representation.

2. While the use of a we3-l-established and easily understood technique (calculus) is a real advantage of the approach, this technique is no longer applicable when additional constraints (e.g.,

on capacity) are allowed.

3. In order to find the optimum n*, a n-umber of problems with n

fixed have to be successively solved. There is no effective way

to solve for the optimum n* directly.

In summary, the disadvantages of existing models for the continuous

problem seem to outweigh decidedly their advantages. While certain

difficulties in convergence and correctness can be overcome by a continuous dynamic programming approach [2], the use of a discrete dynamic

36
prograinining approach is not only computationally simpler but also

avoids the three disadvantages listed above. It is therefore to a

discussion of dynamic programming approaches, in the context of discrete

models, that the discussion now turns.

37
3. 2 Solution Methods for the Discrete Pro'blem

All the solution methods proposed for solving the discrete catalog selection pro'blem are "based, in one way or another, on the technique of

dynamic programming [2]. In order to illustrate "both the philosophy

and computational aspects of this technique, the Wagner-Whitin model

will first 'be studied. For this model it is required to find a catalog

of n sizes (n is to he determined) to minimize (2.6):

C

(

5 ^2

i ) n

n

E [k.

j=l

E c . d ]

. . . r,i. r h-i t

'

The philosophy of dynamic programming is to attack the solution of

the original problem - selecting an optimal catalog from S={s^, s^, ...,

s } - through solution of a sequence of simpler suhprohlems. Specifically,

m

consider the suhprohlem defined hy the subset S^ of S, where S^ =

{s^, •••5 this subproblem there are demands d^,

..., d for the potentially occurring sizes in S., and one is required

m 1 to find an optimal catalog of sizes chosen from S^. Let G(i) denote the

cost of an optimal catalog for S^; thus,

G(1) = the minimijm cost achievable using sizes chosen from S^

to meet demands over S .

.

1

In this context, the dynamic programming approach produces the following

recursive relation satisfied by the G(i)’s, where i = 1, . .

. , m:

38
j

G(i) = min {k. + E c d + G(j+l)}. (3-3)

i < j < m t=i ^

The interpretation of (3-3) is that, assuming we have an optimal catalog

for and the smallest catalog size in is s^ (i £ j £ m)

,

then

the remainder of the catalog should he optimal for The bracketed

expression in (3*3) thus represents the cost for a catalog having smallest

size s^: the first two terms represent the stocking cost of instituting

size s. in the catalog and the substitution costs associated with that

catalog size, while the last term G(j+l) represents the minimum cost for

a catalog to meet demands from Finally, the minimum cost over all

possible values of j (corresponding to the smallest catalog size in )

should be selected in foming G(i).

Having obtained the recursive relation (3.3) it is now direct to obtain

an optimal catalog for S. First, it is convenient to define

G(m+1) = 0.

Thus, using (3-3) with i = m produces

G(m) = k + c d , m mm m

indicating that in order to meet demands in S = {s }, the optimal m m

catalog has the single size s^. Next, using (3.3) with i = m-1, one

39
can calculate G(m-l), also noting which index j* in ( 3 . 3 ) yields the

minirriTim value of the expression in "brackets. The interpretation of this

j* is as the smallest catalog size in an optimal catalog for {s^ .

Continuing in this manner, one can successively calculate G(m-2),

G(2), G(1). However G(1), the minimiim cost achievable for a catalog

over = S, is precisely what is required.

Moreover, by keeping track of the minimizing j* at each step of the process, it is straightforward to construct an optimal catalog corresponding

to the minimum cost G(l). In fact, by keeping track of all minimizing

j* at each step, it is also possible to reconstruct all optimal catalogs.

While the above discussion has focused on the Wagner-Whitin model for

determining a best catalog (and optimal n* ) , it is not difficult to

modify the basic recursion (3.3) to find the best catalog with a fixed

value for n. In this case, define the quantity G^(i) by

G^(i) = the minimum cost achievable using r sizes

chosen from S. to meet demands over S..

1 1

Then the appropriate recursion governing these quantities is

j

G (i) = min {k. + Z ^ d + G (j+l)}. (3.^)

^ i 1 j 1 m-r+1 t=i

^

Again, this relation has a direct interpretation. The first two terms

1+0
within brackets represent the costs associated with the smallest size

s. in the catalog, while G ^(j+l) represents the minimum cost achievable

using r-1 remaining catalog sizes to meet demands arising from S .

To calculate an optimal catalog of n sizes for S, it is first convenient

to define

G^(i)=k +c d,fori=l, ...,m.

1 m mm m

Then, by using (3-^), one can determine in succession

G^{i)

,

i = m-1, . .

. , 1;

G^(i) , i = m-2, . .

. , 1;

G ( i )

,

i = m-n+1 ,

. .

.

,

1

.

n The value finally obtained thus represents the minimum cost

achievable for a catalog of n sizes chosen from S. By keeping track of

the various minimizing indices j*, all optimal catalogs with n sizes

can be found.

It should be pointed out that in determining an optimal catalog for a

fixed number of sizes n, it has been necessary to solve subproblems with

one fixed size, two fixed sizes, ..., and n-1 fixed sizes. In particular, when solving the catalog selection problem for a fixed number

of sizes we use information previously generated for one fewer number

of fixed sizes. Recall that when determining (for the continuous catalog
selection problem) the optimal number of sizes n*, it is necessary to

solve a series of unrelated subproblems. In the present case of discrete catalog problems -vith n fixed, it is also necessary to solve a

series of subproblems. But here the information generated in one subproblem is extremely useful in solving the next subproblem. Suppose,

for example, that an optimal catalog of n=10 sizes has been calculated

using the dynamic programming approach (3.^). If an optimal catalog

of n=ll sizes is subsequently required, the calculation procedure does

not have to begin again from scratch. Indeed, all the required "carryover"

information is already captured in the calculated quantities G^Q(i) currently available.

To summarize, the technique of dynamic programming has been illustrated

in relation to the "optimal n*" and "fixed n" versions of the discrete

catalog selection problem. In contrast to the case for continuous problems (where the former version requires more computation than the latter

one), the "optimal n*" version is easier to solve here than the "fixed

n" version.

Certain advantages of a discrete formulation of the catalog selection

problem can be noted:

1. Demand, which occurs naturally in discrete form, is handled

in discrete form. Analytic (closed form) representation of demand

is not required.

h2
2. The technique of dynamic programming always terminates and is

guaranteed to produce globally optimal solutions.

3. All optimal catalogs can be found through appropriate implementation of the dynamic programming calculations.

U. It is not difficult to incorporate additional constraints on

the problem variables. In fact, since imposition of further constraints narrows the region to be searched for the minimizations

in ( 3 . 3 ) or (3-^), it makes solution of the problem easier, not

harder.

On the other hand, it has been noted that solution of the "fixed n"

version of the discrete problem requires solution of a number of subproblems. (Yet, these subproblems do share common information and need

not be restarted from scratch. ) A more substantive drawback in using

models for the discrete problem is that demand estimates may be available only for certain "historically determined" sizes and not for certain "new" sizes. A procedime for estimating demands over the entire

set S, given certain historical demands, can however be devised to

remedy this situation (see Section U.3).

On balance, therefore, models for the discrete problem appear rather

attractive , especially when compared to analogous models for the continuous problem. These discrete models are guaranteed to produce re1+3
liable answers with a minimmn of computation. Moreover, such models

can be easily modified and extended to incorporate more realistic constraints. The following section discusses a number of such modifications and extensions.
U. REFINEMENTS OF MODELS FOR THE DISCRETE PROBLEM

In light of the assessments of alternative models given in Sections 3.1

and 3.2, attention is subsequently confined to models for the discrete

version of the catalog selection problem. In particular, the basic model

chosen here for fiirther study is the Wagner-Whitin model, which is

described in Section 2.2 and whose associated solution technique is

outlined in Section 3.2. The present section develops various modifications and extensions of this basic model.

h . 1 Computational Observations

The basic Wagner-Whitin model involves evaluating and selecting catalogs

from a finite set S, where the cost of a given catalog {s. , s. , ..., s.

T-1 I2 ^

is provided by the expression (2.6). There is certainly no computational

difficulty in evaluating (2.6) for different proposed catalogs. In

order to find an optimal catalog, the dynamic programming approach of

Section 3.2 is recommended. The basic recursion governing the dynamic

progranuning approach is given by (3.3) for the optimal n* case. The

amount of computation required to calculate optimal catalogs using (3.3)

can be estimated directly. Assuming that S contains m potential sizes,

the calculation of G(l), the minimum cost of a catalog, necessitates

approximately m /6 additions and m /2 comparisons. Finding an optimal

catalog is therefore computationally feasible for catalogs of certainly

several hundred sizes. In addition, only the m values G(i), G(2), ...,

G(m) need to be stored, together with appropriate minimizing values of
j in (3.3)- Thus, the storage requirements are rather minimal for

this solution method.

We now show how this computational effort, already modest, can he further

reduced hy modifying the recursion (3*3). Namely, let j(i) he any minimizing value of j for G(i) in (3.3). That is,

j (i)

= h(i) " +1 °t,o(i)h

"C 1

Similarly, define j(i+l) to he any minimizing value of j for G(i+l).

Then it is certainly true that

i £ j ( i) £ m.

In fact, under an extremely mild restriction, one can demonstrate (see

Appendix B) that

i £ j (i) £ j(i+l) £ m. ih.l)

Relation (U.l) holds as long as d. >0 and the substitution costs c..

^ 1

J

satisfy

c < c . n for k < £.

ik lie (i4.2)

Relation (U.2) states a rather natural requirement: namely, that the

cost of substituting a catalog size for a given size increases as the

U6
1

difference between those two sizes increases. It is inconceivable that

such a condition would not be satisfied in any realistic situation.

The import of (^.l) on the calculation of optimal catalogs results from

the fact that the minimization in (3-3) does not therefore need to be

carried out for all j with i <_ j <_ m. Rather, it only needs to be performed for i j £. j(i+l)j where j(i+l) is some minimizing value for

G(i+l). By choosing J(i+l) to be the smallest value of j that minimizes

G(i+l), one obtains the recursion

.1 G(i) = min {k . + Z c, .d + G(.]+1)}. (U.3)

i < j < J(i+1) J t=i

^

This reformulation of (3-3) can reduce substantially the computation involved in the determination of optimal catalogs. A similar sort of

reduction in computational effort can be achieved in the case of models

for fixed n, through an analogous reformulation of (3.^).

hi
h.2 Extension to a Two-Dimensional Model

In all the models heretofore considered, the problem addressed has been

one of selecting a catalog of items characterized by a single dimension

of size. For example, structural steel beams can be characterized by

section modulus, plate glass by thickness, and so forth. There may,

however, be situations in which a single scalar quantity would not be

considered adequate to characterize an element in potential demand. In

this case, a multidimensional version of the catalog selection problem

might be of interest, where several quantities (e.g., section modulus

and unbraced length) are used to characterize a catalog of standard

items. A two-dimensional version of the (discrete) catalgo selection

problem will be developed in this section.

First, the essential features of this two-dimensional model are briefly

summarized:

1. Each potentially demanded element e is characterized by two

scalar quantities, s(e) and t(e). The finite sets S and T indicate

the possible range of values for these two characteristics.

2. The underlying demand for each possible element is known over

the set S X T, defined below.

3. The demand for any element u can be met by an element v whenever s(v) > s(u) and t(v) > t(u). All demands must be met.

kQ
h. A catalog of supply elements e^. • • 9 e } is to be

chosen from S x T, with s(e^) < s{e^) < ... < s(e^) and t(e^) <

t(e2) < ... < t(e^)

5. There is no limit to the demand that can be met by using a

given supply element.

6. Various costs are associated with the selection of a catalog:

o the cost of failing to meet demand exactly,

o the cost of stocking the specified catalog of elements.

In the above, suppose that the sets S = {s^, s^, s^} and T =

{ti, tg, . •

.

,

t^} represent possible discrete sizes in each of the two

"size dimensions". The set S x t denotes the Cartesian product set,

consisting of all (s,t) with s from S and t from T. An example of this

product set is shown by the rectangle in Fig\ire T. Clearly, not every

possible size s. and size t. are feasible in combination. Indeed, it

1 J appears likely that large values of s^ will be associated with large

values of t., and small values of s. will be associated with small

J 1 values of t . . In such cases, the nonexistent elements are simply

J assigned a corresponding demand d(i,j) = 0 and a very large stocking

cost. More generally, the demand for an element with first size

characteristic s^ and second size characteristic t^ is given by d(i,j)

_> 0. A typical pattern of zero-nonzero demands is shown in Figure T.

with the positive d(i,j) indicated by solid dots.

The imposition of strict inequalities here is not an essential re-

'] u

i

rern''nt , but rather is used to simplify the subsequent exposition.

U9
11

50

Figure

"7.

_he

Sets

S,T

and SxT

for

the

Two-Dimensional

Problem
For this formulation of the problem, Assiimption 3 above means that if a

demanded element is not available, the catalog element which is supplied

must be at least as large in each dimension as the requested element.

Note that since all demands must be met, the element corresponding to the

upper right-hand corner of the rectangle S x T always needs to be in

the catalog. Assumption k indicates that only certain collections of

elements are possible candidates for a catalog. That is, the catalog

elements must be "nested": in other words, it should be possible to

arrange the catalog elements in sequence so that each element is greater

in both its size characteristics than the preceding element in the

sequence. An example of such a nested catalog is given by the circled

dots in Figure 1

.

The assumption of a nested sequence of catalog elements is not at all

unreasonable, inasmuch as actual elements can often be characterized by

two quantitative features which tend to increase (or decrease) together.

Thus, it is believed that actual problems do exist where such an

assumption is realistic. More importantly, this assumption enables efficient solution of the multidimensional catalog selection problem.

Non-nested problems (which also exist) are excluded from study here, but

it appears that insights into techniques for their solution can be gained

from investigating nested catalogs.

As before, there are two costs associated with any given catalog. Let

k(a,b) denote the stocking cost for the element with size dimensions s a and t^, and let c[u,v; a,b] denote the substitution cost in using a

51
catalog element (s ah, t, ) instead of a demanded element (s , t ). Then

u V

the cost of any specified catalog {(s^ 5 "t. ) > ? "t. )» •••5 (s^. , t. )}

is given by the following expression:

"1' Jl ^2 ’^2 \ Jn

C(i^, . •, J 1’ "^n^ ^ c[u,v; d(u,v)], (U.U)

^ 1

where Z indicates a summation taken over all pairs (u,v) with

either ^£-1 < ^ < "£ and !> v| h

or •^£-1 < V < j£ and v| ^£

The set of (u,v) defined in the summation Z is illustrated by the reversed L-shaped region in Figure 8. For convenience, we specify i^ =

= 0 as well as i = P, j = !• It is noted that the collection of

0 n n

£

Z , £ = 1, n, partitions the rectangle of Figure 7 into disjoint

subsets

.

Using equation (U.U), one can evaluate the cost of any specified catalog,

and thus compare (on a cost basis) a number of proposed alternative configurations. In addition, it is possible to solve for an optimal catalog

using an appropriate dynamic programming formulation. To this end, let

us define W(i,j) to be the set of all elements (s , t ) where either u V

i £ u ^ p or j £ V <_ q. Also, define Z(i,j) to be the set of all elements (s , t ) where both i < u < p and j < v < q. Then the important

quantity to be calculated is

G( i, j

)

= the minimum cost achievable using elements chosen

from Z(i,j) to meet demands over W(i,j).

52

If the quantity G(l,l) can be determined, then it represents the minimum

cost of a (nested) catalog chosen from Z(l,l) = S x T to meet demands

over ¥(l,l) = S x T.

As a matter of fact, a recursive relation can be found linking the

values G ( i , j )

.

Namely , for i < p and j < q

G(i,j) = min {k(a,b) + c[u,v; a,b]d(u,v) + G(a+l,b+l)}, (U.5)

(s^,t^)eZMi,j)

where indicates a summation over all u,v with u < a, v < b and either

ab — —

u ^ i or V _> j

. In addition, Z*(i,j) is derived from the set Z(i,j)

by removing all (s^, t^) with u = p or v = q, but not both. Thus,

Z*(i,j) consists of all elements (s^, t_^) with i ;< u < p and j £ v < q,

together with (s , t ). Because the catalog must always contain (s ,t ) p q p q

and because strict inequalities hold in Assumption h, the use of Z*(i,j)

instead of Z(i,j) in (^.5) is permissible.

In addition, define for i = p or j = q (or both)

G(i,j) = k(p,q) + c[u,v, p,q]d(u,v), (^.6)

and set

G(p+1, q+l) = 0. (^. 7 )
Then using (U.5) - (^-7), one can calculate in succession all G(i,j)

for l;lif.P 5 example, all G(i,j) with i = p and/or

j = q can first he calculated, followed by all G(i,j) with i = p-1

and/or j = q-1, and so forth until all the values G(i,j) have been calculated. Eventually, G(1,1) will have been determined, and this quantity

represents the minimum cost of any two-dimensional (nested) catalog over

S X T. By keeping track of the minimizing a* and b* in (U.5), an optimal

catalog (or all optimal catalogs) can be found.

Certainly, the two-dimensional version of the problem does not lend

itself to as transparent a dynamic programming formulation as the basic

V/agner-Whitin model. The computations, while certainly Increased over

those for the single-attribute model, are nonetheless straightforward.

It should also be clear that the model and its associated solution

strategy can be generalized appropriately for catalog selection problems involving more than two size dimensions.

55
U . 3 Estimation of Demands

In the basic model of Wagner and Whitin, it is assumed that demands

are known for all potential sizes in the set S = {s^ , s_, .... s }.

Therefore, this model is quite appropriate when an existing catalog

with many sizes needs to be reduced to a smaller number of standard

sizes. There is also the possibility that new sizes, not in the

current catalog, shoiild be considered for introduction. Thus, there

are known historical demands for certain sizes, but these do not make

up the entire set S of potential sizes in a new catalog. As mentioned

at the end of Section 3.2, it is important in this case to have demand

estimates for all sizes potentially in demand.

In this section, a simplified procedure for obtaining such demand estimates

is developed. Suppose, then, that historical demands are known for some

subset E of S, where E = , e„, ..., e } and e^ < e_ < ... < e . 1 2 r 12 r

It appears reasonable that the current (historical) demand for size e^

represents the cumulative demand for all possible sizes s _< e^, that

the demand for e^ represents the CTomulative demand for sizes s with

e^ < s £ e^, and so forth. This is just another way of saying that the

underlying demand for various sizes is already reflected through the

existing sizes e^.

56
Therefore, the cumulative demand for sizes e^, e^, •••, can he

plotted in the form of a ( ciimulative ) distribution curve, as illustrated

in Figure 9* The ordinate value corresponding to e^ represents the

existing demand for e^, the ordinate value for e^ represents the

existing demand for e^ and e^, and so forth. A continuous c\irve which

approximates this cumulative demand curve can be efficiently obtained -

for example, through the use of spline functions [12]. Note that it

is not necessary (cf. Section 3.1) to obtain in this case an analytical

representation for the approximating curve h(x) over [e^,

Using this curve, it is then direct to estimate the resulting demand

for sizes s.,12m , s^, ..., s . Thus, assuming that s^12< s_ < . . . < sm

and that every s. lies in the range [e^, e ], the demand for various

1 1 r sizes s^ can be found by differencing. Namely, the demand for size

s^ can be estimated as h(s

2^), the demand for size S 2 as h(s

2

) - h(s^),

and so forth. If the sizes s. do not all lie in the range from e, to e , 1 1 r then determining the maximum and minimum sizes for which any demand could

exist will be usefiol in extrapolating the curve h(x).

The above procediire represents a simple method of obtaining demands for

sizes not already in an existing catalog. It should be possible to

refine such a procedure, if needed. In any event, the sensitivity of

optimal catalogs to changes in the demand profile should definitely be

analyzed. Specifically, the dynamic programming approach should be

exercised for a variety of demand scenarios, in order to see how

sensitive (or how robust) selected catalogs are to the demand distribution assumed.

57
\

•M

a>

X

Q 3 < 3 LiJ O Q i o

Figure

9.

Approximating

Demand

Curve

for

Existing

Sizes
5. AEEAS FOR FURTHER INVESTIGATION

In summary, this report has presented and analyzed various models for

solving different versions (continuous and discrete) of the catalog

selection problem. After a careful assessment of both the models and

their solution procedures, one model was singled out for further examination. Certain refinements and extensions were then proposed for this

discrete model and its associated dynamic programming calculations. This

model emerges as not only the most promising among existing models, but

also as one flexible enough to allow further modification.

It has been stressed throughout that such a model can be used in two

distinct ways. First, the model allows one to evaluate, on a cost

basis, any mmiber of proposed alternative catalogs. In this sense,

the model allows the user to weigh the cost aspects of proposed configurations against any other desirable characteristics of the configurations.

Second, the model permits calculation of an optimal (and indeed every

optimal) catalog relative to the stated cost expression. This information

can be especially valuable as a baseline representation of what the

minimum possible cost would be for any catalog. Therefore, it allows

a trade-off analvsis to be nerformed between the additional cost of a

nronosed catalog and other desirable properties of the catalog (e.g.,

inclusion of a preferred number series [ 5 ])» Moreover, the pattern of

sizes indicated by an optimal catalog, or the collection of all optimal

catalogs, can be valuable when attempting to structure catalogs in order

to satisfv several criteria (and not ,1ust that of minimiun cost). As

59
the above di;5cussicn indicates, nhe process of catalog selection can

usefully he viewed as an interactive procedure, involving several iterations between the user and the model.

A computer program in FORTRAN for finding optimal catalogs under the

basic model (3.5) has already been developed. Preliminary testing of

the programmed version of the model has also been undertaken. Before

any intensive testing and evaluation of this automated version of the

model are performed, several other issues need to be explored and

resolved:

1. Further investigation of methods for obtaining a realistic

demand profile should be undertaken. Implementation of a computerized scheme for obtaining such estimates (through use of appropriate curve-fitting techniques) can then be pursued.

2. Realistic estimates for the various cost parameters need to be

obtained, preferably through consultation with and cooperation of

interested industrial groups.

3.

Decisions about the advisability of further modifications of

3 the model, such as the incorporation of capacity restraints or

inclusion of preferred number series^ should also be made. Again,

In the case of capacity constraints, certain alternative models may

become attractive. They appear in the literature in contexts where possible catalog sizes correspond to possible warehouse sites, and demanded

sizes correspond to "customer sites" to be supplied from the warehouses.

Such models, which are Solved by "mixed integer programming" techniques,

are not discussed in this report but warrant further investigation.

ii The inclusion of preferred number series poses an especially interesting

challenge for modeling and analysis, and this topic certainly merits addiLional research effort.
these decisions should be based on consultation with potential

(industrial) users.

U. Once demand and cost estimates are available, and after appropriate modifications of the model have been agreed upon, an automated version of the model should be employed within the framework of a realistic setting.

5- Parametric analyses should be performed in order to assess the

sensitivity of optimal catalogs to demand and cost estimates.

Thus, while the present report has identified and developed a reasonable

approach to catalog selection problems, actual implementation will require further steps. The joint efforts of modelers and users are essential in order for that implementation to be effective and acceptable.

6l
6. REFERENCES

[1] Apostol, T.M. , Mathematical Analysis , Addis on-Wesley, Reading,

Mass . , 1957

[2] Bellman, R.E. and Dreyfus, S.E., Applied Dynamic Programming , Princeton University Press, Princeton, N. J. , I962 .

[ 3 ] Cohen, G.D. , "Comments on a Paper hy M.L. Wolfson: Selecting the

Best Lengths to Stock", Operations Research, Vol. lU, No. 2 ( 1966 ),

3^+1.

[U] Hanssraann, F., "Determination of Optimal Capacities of Service

for Facilities with a Linear Measure of Inefficiency", Operations

Research, Vol. 5, No. 5 (1957), 713-717-

[ 5 ] International Organization for Standards, "Preferred Numbers - Series of Preferred Numbers", ISO 3 - 1973 (E), 1973.

[6] Jackson, D.M. and Zerbe, D.R., "Determination of Standard Sizes

to be Manufactured Using Dynamic Programming", J. Industrial Engineering, Vol. 19 , No. 8 ( 1968 ), UOI-U06 .

[ 7 ] Lind, N.C. et al., "Four Papers on Catalog Optimization", Solid

Mechanics Division, paper No. 138, University of Waterloo (1976).

[8] Newell, G.F. , "Dispatching Policies for a Transportation Route",

Transportation Science, Vol. 5, No. 1 (l97l), 91-105*

[ 9 ] Pentico, D.W. , "The Assortment Problem with Probabilistic Demands",

Management Science, Vol. 21, No. 3 (l97^), 286-290.

[ 10 ] Pentico, D.W. , "The Assortment Problem with Nonlinear Cost Factions", Operations Research, Vol. 2k, No. 6 (1976), 1129-11^2.

[ 11 ] Sadowski, W., "A Few Remarks on the Assortment Problem", Management Science, Vol. 6, No. 1 (1959), 13-2k.

[ 12 ] Schultz, M.H., Spline Analysis , Prentice-Hall, Englewood Cliffs,

N.J., 1973 .

[ 13 ] vom Saal, R.J., "Fast Analytic Solutions for Optimal Schedules

Under Time-Varying Demand", M.S. thesis, Massachusetts Institute

of Technology ( 1968 ).

[lU] Wagner, H.M. and Whitin, T.M. , "Dynamic Version of the Economic

Lot Size Model", Management Science, Vol. 5, No. 1 (1958), 89- 96 .

62
[15] Ward, D.E. , "Optimal Dispatching Policies by Dynamic Programming",

M.S. thesis, Massachusetts Institute of Technology ( 1966 ).

[ 16 ] Wolfson, M.L., "Selecting the Best Lengths to Stock", Operations

Research, Vol. 13, No. U ( 1965 ), 570-585-

[it] Zangwill, W.I., "A Backlogging Model and a Multi-Echelon Model of

a Dynamic Economic Lot Size Production System - A Network Approach",

Management Science, Vol. 15, No. 9 ( 1989 ), 506-527.

63
APPENDIX A

Stability Aspects of Iterative Procedures

In this appendix, we examine certain stability properties of iterative procedures for solving the catalog selection problem. For concreteness, attention will be focused on the behavior of the Lind procedure when n = 2 and all c(x^) = 0. However, the concepts and results presented here can be extended to other iterative schemes, to

n ^ 2, and to more general stocking costs.

Suppose that an optimal catalog of n = 2 sizes {x*, x*} is to be determined. Then the basic iterative relation (3.2) becomes

1 a

Recall that it is required to find a value x^ in [a, b] such that the

x^ calculated as above equals b. The Lind algorithm reduces in this

instance to the following:

LI. Select x^.

L2. Calculate x^ from (A.l).

L3. If Ixg-bl < e, STOP.

Otherwise, calculate z = x^ -

using x^ = z return to Step L2.

6h
Suppose that is a solution of (A.l) with x^ = h- Then x^ satisfies

the first-order conditions for a relative extremiam over [a,b]. Intuitively, we consider that x^ is a "stable" solution of (A.l) under

the Lind scheme if, after a small perturbation is applied to x^, the

scheme insures convergence back to the value x^. More precisely,

y

= x^ is termed stable for our purposes if

b = y

+ f(y)

y

/ f(x)dx (A. 2)

and if for all 6 sufficiently small, the Lind scheme started with the

trial value y+6 yields at the next iteration a value x^ = y with

|y - y| < l<5l

.

Note that in Step L3 of the Lind algorithm

y

= x^ - h(x^).

where

(A. 3)

X

1 1

^ h(Xi) = -[x^ + / f(x)dx - b].

1'^ a (A.U)

Since h(y) = 0, for the starting value x^ = y + 6, we have

y = y + 6 - h(y + 6)

= y + 6 - [h(y+6 ) - h(y) ]

,

65
or equivalently

(y-y)/<5 = 1 - [h(y+6)-h(y) ]/6 .

Using the definition of the derivative.

h'(y) = lim^_^Q[h(y+6)-h(y) ]/6,

we see that y is stable if and only if

l-h'(y)| < 1. (A. 5)

Using (A.U), h’(y) can be evaluated as

h’(y) = 2^1 +

2

y

f (y)

{f(y)f(y) - f'(y) / f(x)dx}]

= ^[2 - / f(x)dx].

f (y) a

Condition (A. 5) then becomes

/ f(x)dx

f (y) a

< 2

or, using (A. 2),

|Q(y)| = (b-y)f»(y)

f(y)

< 2 . :a.6)

66
The indicated quotient Q(y) in (A. 6) can he readily computed and used

to characterize solutions y of (A. 2). Namely, a solution y of the firstorder condition (A. 2) is stable for the Lind algorithm if (A. 6) holds

at this value y. On the other hand, if (A. 6) is not satisfied at y

then we have an unstable solution. For example, it can be directly

shown that any relative maximum of the catalog cost function

^1 b

C(x^) = / (x^-x) f(x)dx + / (b-x) f(x)dx

a x^

(A.T)

is always unstable. Indeed,

1 b b

C(x^)' = x^ / f(x)dx + b / f(x)dx - / xf(x)dx

a x^ a

^1 b b

= (x^-b) / f(x)dx + b / f(x)dx - / xf(x)dx

3. 3 3

= (x^-b) / f(x)dx + K, a

where K is a constant independent of x^. Therefore,

^1

C'(x^) = (x^-b) f(x^) + / f(x)dx,

a

C’’(x^) = (x^-b) f'(x^) + 2f(x^).

If x^ corresponds to a relative maximum of C(x) then C"(x^) < 0 or equivalently (since f(x) > O)

6T
> 2 . (b-x^) f’(x^)

f(x^)

Relation (A. 6) is thus not satisfied at y = x^ and so x^ is an unstable

solution.

“X 2

For Example 1 of Section 3.1, f(x) = e over [0,b], vith b = 1 + e .

It can be shown that y

= 2 is the only solution to (A. 2). Moreover, the

quotient in (A. 6) is

Q(y) =

-

e ^

y-b.

whence

Q( 2 ) = 2 - (1 + e^) = 1 - e^ = -6.389 < - 2 ,

and so y

= 2 is unstable with respect to the Lind procedure. As a

result the Lind procedure, begun with any starting value x^ 5^ 2, will

never converge to the required solution y = 2 .

2

For Example 2 of Section 3.1, f(x) = 3x - 2.0Ux + O.U15 over [0,l].

The quotient in (A. 6) thus becomes

(l-y)(6y-2.0it)

Q(y) = —^ 3y -2.0Uy + O.U15

When evaluated at the three solutions of (A. 2 ): u = O.2769, v =

0.5265 and w = 0 . 7116 , this quotient yields

68
Q(u) = -3.h2,

Q(v) = 3.07,

Q(w) = 1.33.

It follows that u represents an unstable (minimuim) solution, v represents an unstable (maximum) solution and w represents a stable (minimum) solution, with respect to the Lind scheme.

i

69
APPENDIX B

Computational Refinement for the Wagner-Whitin Model

This appendix considers the basic Wagner-Whitin model, described hy

the dynamic programming formulation (3-3):

G(i)

j

min {k. + S

i_< j _< m

^ t=i

Here G(i) represents the minimiam cost achievable using sizes chosen

from S. = {s., s,.,, s } to meet demands over S.. Let j(i) be

any minimizing value of j in the above equation; similarly j(i+l) refers to any minimizing value of j in the corresponding expression for

G(i+1).

We demonstrate in this appendix the validity of the relation

j(i) £ j (i+l)

,

(B.l)

under the assumption that d^ > 0 and

c < c .

.

for k < 1. ik Ik (B.2)

First, note that if j(i) = i, then j(i)=i<i+l£ j(i+l), and so

the result (B.l) holds automatically. Accordingly, it is assumed in

what follows that j(i) > i.

TO
Since j(i) and j(i+l) are minimizing values of G(i) and G(i+l),

respectively.

j (i

)

G(i) = k.(.) + (B.3)

and

j ( i+1

)

Also, because j(i) is a minimizing value of j for G(i) with j(i) ^ i

and because j(i+l) ^ i+1,

j (i+l)

"C 1

using (B.U). Furthermore, because j(i+l) is a minimizing value of j for

G(i+l) with j(i+l) i+1, and because j(i) > i,

j (i)

G(l+1) < k.(i) +

using (B.3). Therefore,

71
and so

G(i+1) < G(i) - c. d. < G(i) < G(i+l) + c. ./.^.Nd.

c

.

1 < c .1 ,o(i+l)

d. . 1

In the case where d.

1 > 0, then

c

.

1 , j(i)

< c — i,j(i+l) (B.5)

From this relation it follows that j(i) £ j(i+l), since otherwise

j(i) > j(i+l) and so by (B.2)

^i,j(i)

^ ^i,j(i+l) ’

contradicting (B.5)«

In the case when d.

1 0, the expressions for G(i) and G(i+l) become

j

G(i) = min {k, + Z G(j+l)} , i < j < m

^ t=i+l ^

3 G(i+l) = min {k. + Z c .d + G(j+l)}.

i+1 5 0 < m

^ t=i+l ^

If the first minimum occurs for j=i, then i is a j(i) for which (B.l)

holds; if it does not occur for j=i, then j(i+l) is a j(i) for which

(B.l) holds. As a consequence.

72
J(i) < J(i+1),

where J(i) represents the smallest value of j minimizing G(i), and

similarly for J(i+l). As a result, even when = 0, an optimal catalog can he found by using the formulation (U.3). However, it may not

be possible to retrieve all optimal catalogs in this case.

73
NBS-1 14A (REV. 7-73)

U.S. DEPT. OF COMM. BIBLIOGRAPHIC DATA

SHEET

1. PUBLICATION OR REPORT NO.

NBSIR 78-1539

2. Gov't Accession

No.

3. Recipient’s Accession No.

4. rn LF AND SUBTITLE

Mathematical Models for Selecting Catalogs of Standard-Sized

Items

5. Publication Date

6. Performing Organization ( ode

7. AUTHOR(S)

Douglas R. Shier

8. Performing Organ. Report No.

9. PERFORMING ORGANIZATION NAME AND ADDRESS

NATIONAL BUREAU OF STANDARDS

DEPARTMENT OF COMMERCE

WASHINGTON, D.C. 20234

10. Project /Task/ Work Unit No. 7120153

11. Contract/Grant No.

12. Sponsoring 0rgani2ation Name and Complete Address (Street, City, State, ZIP) 13. Type of Report & Period Covered

14. Sponsoring Agency Code

15. SUPPLEMENTARY NOTES

16. ABSTRACT (A 200-word or less factual summary of most si^ificant information. If document includes a significant

bibliography or literature survey, mention it here.)

This report identifies and discusses various mathematical models for

selecting a best' catalog of standard sizes. A survey of existing models

for continuous and discrete versions of the catalog selection problem

is presented. The advantages and disadvantages of such models are asV sessed with regard to both range of applicability eind computational

feasibility. This evaluation shows that a frequently-advocated iterative

procedure may produce erroneous results and identifies another approach

as the most promising. Various refinements and extensions are then pro- posed for this latter (discrete) model and its associated solution technique (dynamic prograj^ng). In particular, a multidimensional version

of the catalog selection problem is formulated and analyzed. Areas for further investigation, and unresolved issues, are also discussed.

17. Kh-V' WORDS (six to twelve entries; alphabetical order; capitalize only the first letter of the first key word unless a proper name; separated by semicolons

Catalog; dynamic programming; iterative procedure; models; optimization- stability; standards ’

18. AVAILABILITY Q_ U nl imited

I For Official Discribucion. Do Not Release to NTIS

Order From Sup. of Doc., U.S. Government Printing Office Washington, D.C. 20402, SD Cat. No. CH

E2 Order From National Technical Information Service (NTIS)

Springfield, Virginia 22151

19. SECURITY CLASS

(THIS REPORT)

UNCLASSIFIED

20. SECURITY CLASS

(THIS PAGE)

UNCLASSIFIED

21. NO. OF PAGES

22. Price

USCOMM-OC 29042-P74
I,

>

'1

* >’

I 5