NBSIR 75-737

Mathematical Methods of Site

Selection for Electronic Message

Systems (EMS)

Christoph Witzgall

Applied Mathematics Division

National Bureau of Standards

Institute for Basic Standards

Operations Research Section

Washington, D. C. 20234

Technical Report

toU.S. Postal Service

June 1975

Final

U S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS

NBSIR 75-737

MATHEMATICAL METHODS OF SITE

SELECTION FOR ELECTRONIC MESSAGE

SYSTEMS (EMS)

Christoph Witzgall

Applied Mathematics Division

National Bureau of Standards

Institute for Basic Standards

Operations Research Section

Washington. D. C. 20234

Technical Report

toU.S. Postal Service

June 1975

Final

U.S. DEPARTMENT OF COMMERCE, Rogers C.B. Morton, Secretary

James A. Baker, III, Under Secretary

Dr. Betsy Ancker-Johnson, Assistant Secretary for Science and Technology

NATIONAL BUREAU OF STANDARDS. Ernest Ambler. Acting Director

TABLE OF CONTENTS

ABSTRACT ii

INTRODUCTION 1

1. PROBLEM FORMULATION 3 1.1 Prescribed Number of EMS-Installations 3

1.2 The Cost-Benefit Approach 7 1.3 Nested Solutions 9

2. PRESCRIBED NUMBER OF INSTALLATIONS 10

2.1 The Ranking Method 10

2.2 The Maximum Increment Method 12

2.3 Quadratic Integer Programming 13

2.4 Linear Integer Programming 14

2.5 Concave Minimization Program 19

3. THE RHYS APPROACH 23

3.1 Network Formulation 23

3.2 Penalty Parametrization 26

3.3 Cost-Benefit Parametrization.. -,....27

4. RANK APPROXIMATION 30

4.1 Potentials 30

4.2 Rank- Op timiz able Objectives 32

5. RECOMMENDATIONS 38

6. REFERENCES 40
ABSTRACT

The concept of electronic message (mail) transmission has been

the subject of several feasibility studies during the past decade.

It requires the installation of electronic message handling facilities

at selected locations. If transmission is to be via communications

satellite, then any such facility can transmit to and receive from any

other one. In this report, the mathematical aspects of choosing the

number and locations of these facilities are examined. An inventory

of solution methods is presented, along with recommendations as to

which among them should be employed or developed further.

Key words: communication, cost-benefit, deployment, electronic transmission,

facility location, mail, mathematical programming, message

network synthesis, network optimization, satellite, service

improvement.

- ii -
INTRODUCTION

The work reported here has its source in earlier studies by postal

personnel on planning an electronic message system with the aid of

postal-volume data. This previous work is described in detail in

references [l] and [2] and more briefly below.

Both of these references are concerned with designing an electronic

message system (MS) made up of individual electronic message facilities

(MFs) so as to maximize the volume carried within the MS. Both obtain

average daily volumes from a large postal data base called ODIS (Origin

Destination Information System [3]). The ODIS data are obtained from

20-30 million individual mail pieces which are selected each fiscal

year by a nationwide sampling system.

The concept of the message service considered here is to transmit

the information of the mail piece electronically (e.g., via satellite)

rather than transporting the material mail piece. Thus the electronic

message system requires an electronic transmission subsystem. It also

requires an input subsystem to convert mail information to electronic

form and an output subsystem to convert the transmitted information to

the form in which is to be delivered to addressee.

This concept dates back within the Postal Service to the late 1950s,

when an experimental system called "Speed Mail" was operated between

Washington, D.C., Detroit, Michigan, and Battle Creek, Michigan.

However, in 1961 the Post Office discontinued the Speed Mail program

and, until recently, there have been no significant postal programs on electronic mail.

The final configuration for a network of MFs will depend upon

customer satisfaction with and use of electronic message services and on postal policies concerning the nature and extent of these services.

However, for initial planning purposes, data on mail flows and volumes

may be used to identify market areas, to estimate network volume, and to

identify network configurations likely to yield the highest revenue, give

the greatest improvement in service, or provide the greatest profit (or

smallest loss).

- 1 -
The studies of references [1] and [2] were initial planning efforts

which developed methodology as a by-product during their performance..

Numerical results were obtained manually. By contrast, the present study

has an explicitly methodological purpose: to determine what mathematical

methods are "useful" for solving the large problems posed in references [1]

and [2], where "useful" means that the method is practical to code on a computer and that excessive computer time will not be required for solving

systems involving 100 or more potential EMF sites. An additional concern

is to explore alternate problem formulations related to those in [1] and [2].

The body of the paper is divided into four parts. The first of these

outlines three different formulations of the problem of synthesizing

networks: optimal deployment of a given number of EMFs, cost-benefit

optimization of the size of the EMS, and, finally, generation of an optimal "nested" sequence of networks. Solution methods for each of

these three problem areas are discussed in the three subsequent parts,

respectively. Finally, our recommendations as to preferred problem

formulations and solution methods are summarized.

A collection and description of pertinent methodologies has also

been given as part of a General Dynamics Study [12]. it mentions some network flow techniques which are also referred to in our report.

The two studies, however, differ radically in their approaches and

formulations

.

The exposition of the material is predominantly mathematical. That

is because this report is intended as a technical basepoint and reference

for use by mathematical analysts pursuing the recommended courses of

action. A less detailed account is given in a letter report (Witzgall [13])

previously submitted in completion of our contractual documentation obligations.

The author gratefully acknowledges the lively interest and partipation

by other NBS mathematicians in this project, as well as the advice,

guidance, and general helpfulness of Mr. Emile Sherrard of the U.S. Postal

Service.

- 2 -
1. PROBLEM FORMULATION

In this Part we will consider essentially three ways of formulating

EMS network site selection as an optimization problem. It is understood

that all such optimization formulations are more or less idealizations in

that they are based on estimates, involve concept-simplifying assumptions

and ignore some side conditions of a politico-societal nature which

are present in real world planning. These limitations do not detract

from the usefulness of solving idealized optimization problems in

order to assess the overall utility of a given system, with the option

of then adjusting for special conditions as they are recognized. It

does, however, warn against solution techniques which expend excessive

computational efforts in order to find a "true" optimum.

1 . 1 Prescribed Number of EMFs

The following two sets will recur in our discussion:

(1.1.1) N = set of all potential sites which are considered,

K = set of all actual EMF sixes (to "be chosen).

Clearly, K is a subset of N, symbolically K«=:N, and

0 <_ k <_ n ,

where

potential sites,

EMF sites.

Roughly speaking, the problem is to optimize the selection of actual

sites from a multitude of potential sites, in terms of some measure of

goodness

.

(1.1.2) n = |N| = number of

k = | k( = number of

- 3 -
This statement has to be clarified. A main problem, clearly, is

to decide how many EMFs should be built in the first place. Since

the facilities will obviously not be installed all at once, one might

also ask in which sequence the facilities are to be introduced.

With an eye on these higher level problem formulations, we initially

pose the somewhat simpler question of how to select a

given number k

of installations in an optimal fashion. Plotting the values of these

optimal solutions for different values of k may then yield (Sherrard [2])

a criterion for deciding on the number of facilities to be installed.

Further specification is needed with respect to the measure of

optimality to be employed. The alternatives of foremost interest

appear to be

revenue , service improvement , cost-benefit .

Use of these measures requires a capability to predict transmitted

volumes. ODIS [3] data will provide

(1.1.3) transmissible volumes ,

i.e. the presently observed amounts of mail suitable for EMS-transmission

which move between potential sites. A first guess is to assume that the

transmitted volume would be proportional to this transmissible volume,

and that revenue in turn is proportional to transmitted volume. These

two assumptions are somewhat contradictory. The latter of them seems to

envision a flat rate. Under a flat rate, however, the portion of electronically

transmissible mail which will actually be transmitted must be expected

to be larger for greater distances because of the greater time-savings

provided and of tne consequently increased attractiveness to the customer.

- 4 -
The improvement in the quality of service between two sites is

roughly proportional to their distance. This improvement should be

weighed by the number of customers who are able to take advantage

of it. Thus it is plausible to assume that the measure of service

improvement is proportional to the product of distance with transmissible

volume.

Cost-benefit would be given by the difference of revenues

realized by different modes of transmission and adjusted "by the corresponding

difference in costs.

Obviously there are many alternative measures of optimality. The

rate structure will enter into most of them, and almost all measures of

benefit will be strongly dependent on distance. Exploration of these

alternatives should certainly be an important part of further EMS

planning.

Regardless of which particular benefit criterion has been selected,

we will use the notation

j predicted benefit of EMS serviceV

(1.1.4) v

±

. =1 h= link benefit , ^ ) from site i to site j ,

- realized whenever both sites i and j are chosen for EMFs - and make the

(1.1.5) Assumption : The total predicted benefit of the system is

the sum of all realized link benefits.

In other words:

(1.1.6) Total benefit = V = Z. T. „ ...v.. . leK jeK,jfi xj

The assumption (1.1.5) is not automatically satisfied. For example,

the benefit derived from one EMF may conceivably be influenced

by the proximity of a competing facility. There may be other effects

which influence the total benefit in a nonadditive way. One will have

to assess the extent of such effects in view of the overall accuracy

required.

- 5 -
We are now able to state the

(1.1.7) Network Synthesis Problem for Prescribed Number of Installations :

' Maximize Z. Tr E . Tr ._#.v. . subject to: leK jeK,j?i ij J

total number of EMFs = |k| = k = given .

Suppose all potential sites are numbered sequentially:

i = 1, ... , n .

An equivalent expression of the above problem - a formulation more common

in Operations Research literature - is as follows:

n n

(1.1.8) Max .E..Z. v. .x.x. subject to l=lj=l ij x j

Here the variables x_^ are capable of only two values, namely 1 and 0,

depending on whether or not i is the site of an EMF. Note that the

total benefit is formally stated as a summation over all potential sites;

but since the product x.x. will be zero unless both values x. and

i J i x. equal 1, only those coefficients v. . for which both sites i and i J ij

carry EMFs will enter into the summation. Thus the two formulations

are indeed equivalent.

There are simple operations, useful for later purposes, which can be

applied to the matrix of link benefits v_ without thereby changing the

optimal installation pattern. Adding a common constant to all v^. is

such an operation, since it changes the total benefit function only by an additive constant. One may therefore assume without loss of generality

- 6 -
that all link benefits v^. are positive. This relies on the fact that

the number k of installations is fixed. One wants to keep careful

track of such modifications in order to permit proper adjustments if

the resulting optimal benefits are to be compared for different values

of k.

Each pair of counter-directed link benefits v. . and v. . may be

ij Ji

combined, since

n n n i-1

E E v . . x . x . = I £ (v .

. +v . . ) x . x . . i=l j=l 1J 1 J i=2 j=l 1J J1 1 J

In other words, the total benefit depends only on the sums v

^j

+vji ' One can therefore

(1.1.9) symmetrize

the problem by replacing the vjj' s with the modified benefits

v. . = ^-(v. .+v. . ) = v. . .

This symmetrization does not require the number of installations to be

fixed, nor does it affect the total benefit in any way.

1.2 The Cost-Benefit Approach

Synthesizing an EMS-network with a prescribed number of installations

may be of direct interest in some planning situations. More likely,

however, it will be employed as a subanalysis in the process of gaining

some idea of how many installations should be built.

If estimates of costs for amortizing, operating and maintaining EMFs are available, then one could introduce them into the model as factors

limiting the proliferation of facilities and hopefully producing a most

cost-efficient EMS-network. Note that direct operating costs, i.e. the

costs per volume processed, can and should be spread over the links by

adjusting the link benefits v . The

- 7 -
which are independent of volume processed, are the costs to be associated

with sites. The quantity now to be maximized is the difference between

total benefit accruing on the links - adjusted for direct operating

costs - and the total (indirect operating) cost

(1.2.2) C - Z ieKCi

incurred at the facilities. This gives rise to the following

(1.2.3) Network Synthesis Problem with Cost-Benefit Optimization:

n

Z c.x. subject to

1=1 1 1 —J

1 <_ i <_ n .

This approach has been explored - for a more general setting - in an important paper by J.M.W. Rhys [4], who was able to show that the

problem is dual to a network-flow problem and is therefore particularly

easy to solve. The paper of Rhys is discussed in greater detail in

Part 3. It was brought to our attention by D.R. Shier, Post-doctoral

Research Fellow, NBS Applied Mathematics Division. The problem is also

treated in a recent report by Picard and Ratliff [5],

The main difficulty of the cost-benefit approach is that it requires

cost and revenue figures, which may not be available or may need to

await further decisions on rate structure, etc. It also requires demand

estimates that may be hard to come by. In this situation the model

should be used

(1.2.4) parametrically ,
i.e. one should explore the performance of the system for a variety

of possible values of the unknown but critical factors like rates,

demand responses, operating costs, etc.

1 . 3 Nested Solutions

Taking into account the fact that EMFs are not built all at once,

and that the total number to be built is unknown, one is led to formulate

a somewhat different class of optimization problems in which interest

centers on some kind of optimal sequence in which to install EMTs.

A first cut at this problem is to require that the network solutions

be

(1.3.1) nested ,

that is, the network generated for k-1 E>fFs is a subnetwork of the one generated for k EMFs. Methods which successively generate nested networks

will be called

(1.3.2) sequential methods ,

and two prototypes will be discussed in Sections 2.1 and 2.2.

The problem then presents itself as finding optimal nested sequences

of networks, where one of the tasks is again to suitably define optimality.

Note that the optimal solutions to the Network Synthesis Problem

(1.1.7) for a prescribed number of EMTs are not necessarily nested.

The following example involving 4 potential sites is a case in point:

The numbers attached to the links

describe the combined transmission

and reception benefit. The optimal

solution for 2 facilities is {2,4},

whereas the optimal solution for 3

facilities is {1,2,3}.

- 9 -
2. PRESCRIBED NUMBER OF INSTALLATIONS

This Part discusses various methods and approaches directed at

optimal Network Synthesis for a given number of EMFs . The first two

methods represent what one might call "sequential" methods in that

they generate nested sequences of optimal solutions. They have been

employed previously to a limited extent for synthesizing networks based

on ODIS data. While these methods will in general not find a true

optimum, they will come close enough for practical purposes. Furthermore,

they are attractive because they mimic the sequential process

of actual construction. Subsequently, various possible integer

programming formulations are described and some heuristic approaches are

discussed. Application of Dynamic Programming has not been considered.

2.1 The Ranking Method . The following method for arriving at a first cut at EMS-network

synthesis was proposed by R. Ruckman [1] : The potential sites are ranked in linear order by the estimated amount of mail volume

generated for EMS transmission, including the amount of comparable

local business. The sites are then selected in this order, namely

the highest ranking site first, to be followed by the second ranking

site etc.

The rationale behind this method is as follows: Suppose revenue - and therefore volume - is to be maximized, and one makes the

(2.1.1) Assumption : The transmitted volume at each site will

distribute among the other sites^ proportionally

to the respective totals of transmission volumes

of the receiving sites .

Let then

v . , 1 < i < n ,

- 10 -
be the total "transmissible" mail at site i:

n

where

V

ii

is the estimated amount of local business of the transmissible kind,

Assumption (2.1.1) then means that there are factors

p , i - 1, . . . , n ,

such that

Consequently

v . . = p . v

.

ij 1 J

n n n

where

v. = £ v.. = E p.v. = p. E v. = p.V , 1 -liJ , i i i . , i i j=l J 3=1 J j=l J

n

V = E v

is the grand total transmissible mail volume. Thus

V

i

p i = r

and

v. v. (2.1.2) v.. =

- 11 -
It now follows that

n n ^ n n

E E v..x.x. = — E E (v.x.)(v.x.) , 1=1 j=l ^

1 J V

1=1 j-1 1 1 J J

and it is clear that this expression is maximized by selecting the k

nodes of highest ranking .

The above argument shows the limitation of the ranking method:

If distance enters the benefit assessment - as it does if one seeks

to maximize service improvement or cost benefit rather than

volume - then assumption (2.1.1) is clearly not valid. Even for

volume maximization, the assumed proportionality of the volumes

is problematical. This is particularly true if there is a large

discrepancy between transmitted and received mail volumes such as exists,

for instance, for Washington, D.C., as pointed out by Sherrard [2].

Ranking by combined transmitted and received volumes, however, would

avoid the latter difficulty.

It is interesting to see that in order to infer the relationship

(2.1.2) from assumption (2.1.1), it was necessary to include the "local"

volume v. . . Without this inclusion the representation of v. . will n ij

be more complicated and not even symmetric (see (4.2.7)). However,

we will see in Part 4, that even then the ranking method produces nested

solutions that are truly optimal.

2.2 The Maximum Increment Method

The best solution for two installations (i.e. k=2) is to find the

highest symmetrized (1.1.9) link benefit - combining transmission and

reception - and build installations at the two ends of this link.

- 12 -
The idea of the maximum increment method is to simply add to a best

solution S for k facilities by building at a new site i (not

in S) which maximizes the incremental benefit

2. c (v. ,+v. .)

achieved by the enlarged capacity of the system. The networks thus

synthesized will be nested but not necessarily optimal. Nevertheless

they are sufficiently close to optimal to provide a workable model

and in general are superior to the solutions obtained by ranking.

Obvious variations are to add two or three sites at once, maximizing

their combined contribution. Adding more than three facilities at once

will, however, be too expensive computationally.

One might also suggest scanning each solution as to whether any of

its installations could profitably be shifted to another site. The

sequence of solutions thus generated may, however, no longer be nested.

The maximum increment method has been employed by Sherrard [2] in

manual synthesis of some volume maximizing networks. It is excellently

suited for automation on a computer.

2 . 3 Quadratic Integer Programming

Problem (1.1.8) can be transformed into a quadratic integer programming

problem of the kind solvable by an algorithm of Witzgall [6]. The

transformation is to replace the products x

j_ x

j ^y the expressions

2 x.+x.-(x.-x. ) *

1 2 i J 2

* The writer does not remember from what source he learned this "trick"

in 1971.

- 13 -
Indeed, these expressions have the same value as x

^xj for all 4

combinations of 0,1 values which x^ and x^ can assume. The quadratic

programming algorithm further requires integer coefficients in the

function to be maximized. This means that the link benefits v. , should

ij

be nonnegative integers divisible by two. This can always be achieved

by adding a suitable constant to insure nonnegativity and by suitably

scaling so that the rounding to an even integer does not introduce an appreciable error.

The method will produce an exact solution. It is, however, not

recommended for problems with more than 20 potential sites, since

running time will be a problem.

2.4 Linear Integer Programming

The Problem (1.1.7) can in various ways be formulated as a Linear

Integer Programming Problem. We will present three such formulations,

two of them closely related to the reformulations of general polynomial

0,1-programs developed by Glover and Woolsey [7]. In all three cases one replaces the product x^x . a new variable y _

(2.4.1) y. . = x.x. for all 1 <_ i,j <_ n , i£j .

Linear side conditions will have to be introduced to enforce this

nonlinear relationship.

The first formulation is due to A.J. Goldman (NBS Applied Mathematics

Division):

- 14 -
n

(2.4.2) Max 2 Z v. y . subject to

i=l j=l 1J 1J

2 y. . = (k-l)x. for 1 < i < n .

y.. = y.. for 1 < i,j < n ,

n

2 x. = k , i=l 1

x

i =[i

for 1 < i < n ,

0 < y < 1 for 1 < i,j < n .

The first set of equations expresses the fact that for each site i "with

value x^=l precisely k-1 of the products x^x. , i^j , have value 1 , whereas x.x. is always zero if x.=0 . These equations are therefore

i J i

necessary. They are also sufficient. Indeed, 2x^=k implies that

there are precisely k nonzero values x_^ . For an i with x_^=0 , all values y. . must vanish. For an i with x.=l , there can he at

ij i

most k-1 nonzero values y. . since y..=y. .>0 requires x.=l ; since the values y. . for fixed i add up to k-1 , all y. . must

assume their maximum value, namely 1 . It follows that y. .=1 whenever

^- J x.=l and x.=l , and y. .=0 whenever x.=0 or x.=0 . In other words,

1 J !J 1 J y. ,-x.x. , which was to be shown,

ij 1 J Clearly only half of the variables y are needed, as y^=y^ . However, the formulation becomes pesky for expository purposes if carried

out in terms of only those variables y. . for which, say, i < j . Note that the integrality of the variables x^ enforces integrality

of the variables y so that the latter need not be explicitly required.

The problem is therefore a mixed integer program ( see Garfinkel and Nemh*uSPr rsl)

i.e., some but not all variables are required to be integral. There are general purpose computer programs available for such mixed integer programs.

- 15-
They are expensive to run and not recommended for n > 30 . "Branch and

Bound" methods can be devised for solving problem (2.^.2) which should be

superior to the use of a general purpose package, but they will still be

expensive inasmuch as they will require the solution of a large continuous

linear program (see Gass [9]) as a much repeated subprogram.

The second formulation is due to D. Shier (UBS). Here it is convenient

to introduce only the variables y. . with i<j . As a consequence we will

consider the symmetrized (1.1.9) benefits

v. . = l/2(v. . + v. . ) , 1 < i < j < n .

Shier' s formulation will require that

> 0 i°L 1 < i < j < n .

As was shown in Section 1.1, this can be achieved by adding a sufficiently

large constant to all link benefits v. . . As the number k of installations

is fixed, this will not influence the optimality pattern.

n-1 n

(2.^.3) Max 2 Z v. .y. . subject to \ ~> 1 it 11 - i=l j=i+l J J

y.. < x. , y.. < x. for 1 < i < i < n ,

n

Z x. = k , 1-1 1

Clearly y.. < x.x. . Since we are maximizing a linear function with

ij - 1 J positive coefficients, the variables y^. will assume their largest

possible values, whence y .

. = x.x.

.

- 16 -
This is a mixed integer program (see for instance Garf inkel and

Nemhauser [8]). It has many more constraints than the program (2.4.2),

and it is consequently less suitable for the application of a general

purpose mixed integer package. It is, however, better suited than (2.4.2)

fnr a Branch and Bound method, since its continuous linear program with

0 ^_ x^ <_ 1 has a particularly tractable structure: If it were not for the

presence of equation Zx_^=k, the continuous linear program would be the

dual of a network problem (a proof of this statement will be given in

Section 3.1). Such problems are particularly easy to solve, even in the

presence of one (or several) side-conditions.

A formulation suggested by J. Edmonds (NBS Applied Mathematics Division)

works only with variables y. . , i < j , and does not consider variables

x_^ . Note that the y-variables are in 1-1 correspondence with all possible

links between sites. These links define a

For each of the many other subgraphs S , including S = G , we define

(2.4.4) graph G .

The actual installations and the links between them define the

(2.4.5) subgraph S .

(2.4.6)

where I denotes links and y^ denotes the corresponding y-variables.

Finally if (P,P) denotes a

(2.4.7) partition

of the sites into two classes, then the

(2.4.8) cutset C(P,P)

- IT "
is defined as the set of all links with one end in P and the other

end in P . In these terms, Edmonds suggests the formulation (|p|,

cardinalities of P , P)

Max Z _ y v subject to

m - ^

V JP for jeeG .

for partitions (P,P):

y(C(P,P))< max{(k-h)h | max{0,k- |p| ] < h < minfk, |p| }}

The above conditions are necessary. Indeed, if h denotes the number

f EMFs in P, then there are k-h EMFs in P, and the cut set C(P,P)

oconsequently contains (k-h)h links between EMFs . As h < |P

k-h < |p| , h can range as follows

and

max (0,k-|p| } < h < minfk, |p|

}

and the maximum of (k-h)h achieved for integers in this range is clearly

an upper bound on C(P,P).

It is conjectured that the inequalities also suffice to make this a correct problem formulation. It is not suitable for a general purpose

integer programming package because now all variables have to be integer

and because of the huge number of constraints. It might lend itself,

however, to an efficient stepwise computational method based on a linear

program which at each stage imposes only a subset of the constraints,

adding one or more of those violated by the "solution" at the preceding

stage. Development of such a method would be an advanced research project.

- 18 -
2.5. Concave Minimization Program

For the sake of completeness, and without discussing possible solution

methods, we note that the problem (1.1.7) of selecting a fixed number of

EMFs can also be formulated in terms of minimizing a concave function

subject to linear equations and inequality conditions.

The reader verifies immediately that

n-1 n n-1 n Min Max E E y. . = Min E E min{x.,x.}

Ex.=k y.. < x. i=l j=i+l 1J Ex.=k i=l j=i+l 1 J i ij ~ i . l

J 0<x. <ly..<xJ 0<x.<l - i ~ iJ ~ j - i ~

We now claim that

(2.5.1) the expression

n-1 n

Y(x) = E E min{x. ,x. } , i=l j=i+l 1 3

where

E x.=k , 0 < x. < 1 for 1 < i < n , i=l 1 ~ x ~ — ~

-

is minimized for 0,1-values of x^ , satisfying the above conditions

Note that no weights v. . are considered in the above minimization.

All feasible integer solutions are therefore optimal with Y(x) = k(k-l)/2

the minimum value.

- 19 -
Proof : Consider any non-integral solution, and assume for simplicity

of notation that

(2.5.2) x

x

< x

2

< ... < x

n

,

so that min{x

± ,x } = x

± for i < j and therefore

n-1 n n-1 n n Y(x) ~ 2 2 x = Z (n-i)x = I (n-i)x

± = nk - £ ix

i

i=l j=i+l 1 i=l i=l 1=1

Let s be the smallest index such that

x

g

> 0 ,

and t the largest index such that

x

t < 1 •

We claim that Y(x) is not minimal as long as there exists a non-integer

x. ,

0 < x < 1 ,

in other words, as long as s <^ t . Note that s = t would imply that

just one of the values x_^ was not integer, contradicting the fact that

all x_^ add up to integer k. Thus s <_ t implies

s < t .

In the latter case, let

= min{x , 1-x } > 0 , s t

and modify the values x^ as follows:

f x - 9 if i = s -x.=Jx+0 ifi=t t x^ otherwise,
Clearly, Ex. = k and 0 <_ <_ 1 for 1 <_ i <_ n . Furthermore, the

order-relationships (2.5.2) remain unchanged. Thus

n

Y(x) = nk - S ix.

i=l

1

and

Y(x) -Y(x) = - S i(x.-x.) = s6 - t6 < 0 , i=l

1 1

which shows that integrality is necessary for Y(x) to be minimized.

It is clearly sufficient, as all 0,1 values x.11with Zx. = k

yield Y(x) = k(k-l)/2, which thus is the actual minimum value.

We now denote by

M

a very big number, and claim that

(2.5.3) —the______ solutions _ (x- ,x ) of the minimi z at ionprobi em

n n-1 n Min Z Z (M-v. . )min{x. ,x. } subject to

£=1 j=i+l *J 1

^ n

Z x =k , i=l

0 <_ x_^ <_ 1 for 1 <_ i <_ n

are also the_ solutions of the problem (1.1.8).

Proof : For sufficiently large M , the above minimization will behave like

the minimization of Y(x) in (2.5.1), and therefore admit only integer

values x. as minimum solutions. For such solutions

l

- 21 -
min {x ,x, } = x.x.

and therefore

MinEE (M-v. . )min{x. ,x. } = - MaxEEv. .x.x. + const,

ij i 3 ij i J

22-
3. THE RHYS APPROACH

In this part we will elaborate on the cost-benefit approach to

network synthesis. We follow the lines established by J.M.W. Rhys [4]

for more general system design problems.

3 . 1 Network formulation

We are dealing with the Network Synthesis Problem with Cost-Benefit

Optimization as spelled out in (1.2.3). We linearize the problem using

the method described in (2.4.3) for the case of positive link benefits

'« !

n-1 n n

(3.1.1) Max Z E v.. v.. - £ c.x. subject to

i=l j =i+l J i=l

yij -

X

i ' yij -

X

j — 1 -

1 <

^ - n '

x

i = S ^ for 1 <_ i <_ n .

The difference between formulations (2.4.3) and (3.1.1) is that the

constraint Zx^ = k has been removed and instead of it a penalty

term Zc.x. has been added to the objective function. 11 J

Now, the important observation is that in (3.1.1) the condition , {:

can be replaced by

0 < x. < 1 — l —

without changing the problem. In other words, problem (3.1.1) is in

reality not an integer programming problem but a normal continuous

linear program:

_ 23
n-1 n n

(3.1.2) Max E E v .y - E c x subject to

1=1 j=i+l J J 1=1

y

lj -

X

i ' yij -

X

j — 1 -

1 <

J -

n '

0 1 x

i 1 1 for 1 < i < n .

The equivalence of formulations (3.1.1) and (3.1.2) is due to the fact -

to be shown below - that problem (3.1.2) is the dual of a network flow

problem of the kind described for instance in Ford and Fulkerson [10}.

We have mentioned this fact already in Section 2.4. Such network

problems and their duals automatically yield integer values for variables

with integer bounds. Furthermore, problems of this kind are computationally

much easier to handle than continuous linear programs and certainly much,

easier than general integer linear programs.

(3.1.3) Theorem : Problem (3.1.2) is the dual of a minimum cogt flow

network problem .

Proof : In order to dualize (3.1.2), we introduce multipliers corresponding

to its constraints (see for instance Gass [9]):

r. > 0 for 1 < i < j < n (y. . - x. < 0) , lj — — — J lj i — '

s . . > 0 for 1 < i < j < n (y. . - x. < 0) ,

t. > 0 for 1 < i < n (x. < 1) , l — — — i — '

n Min E t subject to

i=l

r. . + s . . = v . . for 1 < i < i < n

ij ij ij ~ J -

n i-1

- E r..- Es. . + t. - w. =-c. for 1"< i < n , j=i+l J j=l

r . . >s. . ,t. ,w. > 0 . ij ij x i -

-2h-
Substituting

i-l_

s.. = v. . - r. . , c* = -c + Z v , ij ij ij i 1 j= i

J 1

and adding an irrelevant constraint gives

n

(3.1.4) Min E t. subject to

i=l 1

n n n

- I t. + E w. = - 2c*,

. , i . , x . , i

i=l i=l i=l

n i-1

-I r. . + £ r.. + t. -w. = c* for 1 < i < n , J-i+1 1J j=l J1 1 1 1 ~

~

0 -

< r. . < v. . for 1 < i < j < n , ij - ij -

t . , w_, > 0 for 1 < i < n . l i — — —

In order to see that the first constraint equation is indeed superfluous,

we note that the sum of all constraint equations is identically zero, as each coefficient r „ occurs exactly twice with opposite signs

.

Now construct a network as follows: nodes are the numbers 0,1,..., n . The links adjacent to node 0 are one to and one from each node i ^ 0,

with flows corresponding to variables t. and w. , respectively. The

remaining arcs point from each index i > 0 to all indices j > i , with capacities v. . and flows corresponding to the variables r. . . The constraint equations are "Kirchhoff conditions", stating for each

node the balance equation:

-(flow out) + (flow in) = (sink strength)

This proves Theorem (3.1.3).

- 25 -
The integrality of x. follows from the fact that x. is the

° J i i

shadow-price for the constraint equation corresponding to node i , and

these shadow-prices are obtained as additive combinations of the costcoefficients, which are in our case of value 1 and 0.

3.2 Penalty Parame trization

Suppose that all site-related costs are equal:

c

i = c for 1 £i < n .

Then the objective function of (3.1.1) becomes

n-1 n n

(3.2.1) I I v. .y. , - C Z x. . i-1 j-i+1 ±J 1J i-1

1

We can now treat C as a

(3.2.2) parameter

of the problem, i.e. we can ask for the solutions of (3.1.1) in dependence

on the value of C. A small change in C will in general not change the

optimal solution (the optimal deployment of facilities). The C-axis is

thus divided into a number of intervals ("regimes") in each of which a certain network is optimal. Parametric Programming (see Gass [9]) is a computational technique for efficiently determining in succession the

"breakpoints" which are the boundaries of the various regimes.

Since v > 0 , the optimal solution for C=0 is to put an EMF

at every site. As C increases, a network of fewer sites is encountered,

and so on, until finally the penalty C becomes so big that the optimal

strategy is to build no facilities at all. There will thus be a sequence

of sizes

(3.2.3) n=k > k,> k9

> . . . > 0 o 1 I

of optimal solutions. Clearly, each of these networks will be optimal

when compared to others of the same size.

- 26 -
If the link-benefits are indeed revenues expressed in monetary units,

then the penalties C can be interpreted as average installation costs.

However, if the link-benefits represent quantities other than revenues

as, for instance, mail volumes or service improvements, then C becomes

just an abstract

(3.2.4) penalty .

No meaning attaches to its values as such. Its purpose is to generate a sequence of networks of sizes (3.2.3). These networks will then be

solutions to the Network Synthesis Problem with Prescribed Number of

Installations (1.1.7) for the k-values in (3.2.3). The sequence (3.2.3)

may not contain all numbers between 0 and n, but it is expected that

it contains a majority of them. The penalty interval associated with

each optimal network, i.e. the range over which the penalty can vary so that the same network will be optimal, yields a measure of preference

for the network: if the penalty interval is big, then the associated

optimal network is a preferred one. The above penalty parametrization

method will therefore produce a set of preferred network sizes for arbitrary

measures of benefit.

3.3 Cost-Benefit Parametrization

For the purposes of a direct cost-benefit analysis, let

r.. = electronic mail revenue - conventional mail revenue

c. = direct electronic operating cost - direct conventional

operating cost.

Then

p.. = r.. - c. . = operating revenue (benefit)

ij ij ij

for transmissions from site i to site j .

- 27 -
In order to demonstrate one possible parametric approach - not

necessarily a recommended one - we assume that there are flat rates

for both electronic and conventional transmission per unit of mail;

that costs are distance independent and proportional to volume; and that

demand volume is a uniform fraction of

v.. = ODIS transmissible volumes

ij

This uniform fraction is denoted by

D = demand level

If

then

and

where

R = electronic rate - conventional rate,

B = electronic unit cost - conventional unit cost ,

r . . = RDv . . , c .

. = BDv . . ,

P

ij = r

ij " C

ij = D(R-B)v

ij = ^ij

T = D(R-B) .
With

= indirect operating costs at site i ,

we then have the parametric problem

n-1 n n Max T E Z v.-.y. . - E c,x. subject to

j i j i ij ij „ , i i

J i=l i=i+l J J 1=1

y.. < x. , y.. < x.

0 < x. < 1 . — i —

This is a parametric program in its simplest form: linear in the single

parameter T . More sophisticated formulations would be nonlinear in

a single parameter or linear in two parameters.

-20-
4. RANK APPROXIMATION

Finding "best nested" solutions (1.3.1) can be defined and treated

as finding the best approximation of the given problem by problems

which are solvable by ranking.

4 . 1 Potentials

We recall the observation of Section 2.1 that if the link benefits

Vj . have the special form

v.v.

(4.1.1) v = , i£j ,

where v. , v. > 0 will be called

i J

(4.1.2) potentials

associated with sites, then ranking by potentials will yield an optimal

solution for each prescribed number of installations.

Note that if potentials exist satisfying (4.1.1), then there also

exist potentials v^ satisfying

i (4.1.3) V±j - Vj .

Indeed, all one has to do is replace v. by v /-yj V •

For arbitrary link benefits v potentials will not in general

exist such that (4.1.3) is satisfied. However, one may ask the

question what is the "best" approximation - say, in the sense of least

squares - of the given link benefits v_^ by numbers of the form v

£vj

• Ranking by the potentials v^ so determined, can be considered to define

a best sequence of nested solutions.

- 30 -
If a least squares approach is adopted directly, then the following

minimization problem results:

n-1 n

2 (4.1.4) Min I I (v -v v.) subject to

i=l j=i+l 2 2

v4 L 0 for 1 ± i ± n .

Note that we have passed from the m to the symmetrized quantities

v^. (1.1.9) , since we seek to approximate by symmetric quantities

(v^Vj = v

j v^) • This is a nonlinear programming problem - the objective

function is a polynomial of fourth degree - whose solution does not appear

easy enough for this approach to be attractive.

A more tractable approach can be obtained by passing to logarithms:

u = log v , u

± = log v

±

.

Noting that the desired exact relation v = v^v. is equivalent to

u. . = u.+u. , we are led to replace (4.1.4) by

ij i j

n-1 n

2 (4.1.5) Min £ Z (u -u.-u.) , 1=1 j=i+l iJ 1 2

This problem admits a simple closed-form solution (A.J. Goldman, NBS).

Indeed, equating the i-th partial derivative of the objective function

(4.1.5) to zero yields

n

I (U - u - u ) = 0 , 3=1

or equivalently

n n

(n-l)u. + 2 u. = I u. . , 1 j=l^

j^i 3*±

31
which can be rewritten

n n

(4.1.6) (n-2)u. + Z u - E u . 1 j=l J j=l 13

Summing (4.1.6) over 1=1, 2,..., n yields

n n n n

(n-2) Z u. + n E u = Z Z u , i=l

1 j=l 3 i=l j-1 1J

or equivalently

n n n

(2n-2) Z u. = 2 Z Z u. . . j=l J i=l j-i+1 1J

Solving this for the sum on the left-hand side, substituting the result

into (4.1.6), and solving for u^ , yields our final result:

n n n

(4.1.7) u. = ( Z u..)/(n-2) - ( Z Z Tu ,)/ (n-1) (n-2) . 1

J-1 J k=l j=k+l 2 3*1

4 . 2 Rank-Op timiz able Objectives

The objective function to be maximized is

n n

F = Z X v, .x.x. . i-1 j-1 ij 1 J

Jrfi

It was seen before, that if the objective function has coefficients of

the form

v. . = v.v. , ij 1 J

where v^ , v, are nonnegative site-associated potentials (4.1.2), then

ranking by potentials yields an optimal solution for each prescribed

number of installations. We say therefore that such an objective function

is

- 31 -
(4.2.1) rank-optimizable

In order to describe other rank-optimizable functions, let <j> be an arbitrary function of two variables. With respect to some given sequence

of potentials v. we then form the link benefits v.. = c(v.,v.) . i ij i J Under which circumstances is the corresponding objective function rankoptimizable?

(4.2.2) Theorem: Given potentials v_^ > 0 for each site, a function <J> of two variables defines an objective function ,

= c(v

i?

v_.) for if*j ,

which is rank-optimizable (4.2.1) by the potentials v_^ , if £ is monotone increasing in each variable in the

positive quadrant :

» z — 2 ) ~= 0

3Z

1 for z i

,z

2 — ® ' —TZ — > 0

Proof : Suppose the sites are numbered by decreasing rank,

v.1—2> v 0 ... > v — n

Then deploying EMFs at sites l,...,k realizes the value

k k

F = F({l,...,k}) = I I «Kv.,vJ

i=l j=l 1 2

of the objective function. Let then

m

1

< m

2

< ... < ^

- 33 -
be the site indices of any other deployment of the prescribed number k

of facilities. It will realize the value

k k

F = F({m_ ,...,m, }) = Z Z <J>(v ,v ) . 1 * i=l j=l m

i "k

Clearly,

whence

m

±

>_ i , nij >. j ,

m. — i ' m. — i 1 3

Thus monotonicity gives

<Kv ,v ) < 4>(v. ,v ) <_ (J)(V ,v ) , m.m. — im. — 11

1 3 3

and therefore

F —

< F , o

which was to be shown.

For symmetric functions <f> , C.R. Johnson (Postdoctoral Research

Fellow, NBS Applied Mathematics Division) has derived a sufficient and

necessary condition for generating a rank-optimizable objective function,

(4.2.3) Theorem: v^ = 0(v^,v^) is rank optimizable (4.2.1) in v^ if

and only if

(4.2.4) (f>(y ,z) >_ max{cf) (x,y) ,<j> (x,z) } whenever x <_ y <_ z
Proof: (4.2.4) is necessary for any function $ . Take n=3, k=2, v^=z,

V2=y, v

2=x • If rank-optimizability is to hold, the solution set must

be {y,z} rather than {x,y} or {x,z} so that (4.2.4) must apply.

To prove sufficiency, assume again that the sites are numbered by

decreasing rank, so that we have to show that the sites {l,2,...,k} are optimal. Consider any other set

M = {m , m

2

, . . . , m^} ^ {1,2,3, ... ,k}

with

m

l

< m

2 < < \

so that

V > V > . . . > V

ml~ m

2 "

"

There exists some index h <_ k which is not in M . Let then M' be

the set which arises from M by removing m^ and adjoining h instead.

Using the notation F(M) and F(M') for the total benefits accruing

from deployments M and M' , respectively, we have (using the symmetry

of <f>)

k k k-1 k-1 k-1

F(M) = Z E d»(v ,v ) = I E 4(v ,v ) + 2 Z f(v ,v ) i-1 j=l m

i

m

j i=l j=l m

i m

j 1=1 m

i

_Uk

k-1 k-1 k_i

3=1

F(M')= = Z Z <b(v ,v ) + 2 E d»(v ,v, )

. , . , m. m. . n m. n 1=1 3=1 i J i=l i

and consequently

- 35 -
k-1

(4.2.5) F(M') - F(M) = 22 (<J,(v ,v. ) - #(v ,V )) . 1=1 m

i

h m

i \

Now distinguish two cases: (I) m_^ < h; (II) h < .

In case (I) ,m^<h<m^ as m^ > k >_ h , whence

x = v <y = v <z = v , \

h m

i

and (4.2.4) gives in view of symmetry

<f>(v ,v ) = <|>(z,y) = <f>(y>z) > *(z»x) = A(v ,v ) . m^ n — m^ m^

In case (II) , h < m_^ <_ , whence

x = v <y = v < z = v, , — m

i —

and (4.2.4) gives

frTM > vi,) = <Ky>z) l<j)(x,y) - 4>(v ,v ) . n — iik m^

Thus F(M') -F(M) >_ 0 , which was to be shown.

Condition (4.2.4) is weaker than monotonicity(4.2.2) . This is shown

by the following example (W.A. Horn [11]) of a symmetric function <}> which

satisfies (4.2.4), but is not monotone (4.2.2).

{x+y if | x—y | <_ 1 _x_ _^

and <j> 2 (x,y) - e X y

2min(x,y)+l else

Theorem (4.2.2) yields that, for instance, the benefit pattern

(4.2.6) v.. = b + av. + cv. + v.v., i^i , ij i 3 i j a, b, c > 0 ,

-36 -
is rank-optimizable. This more flexible expression should permit a closer

approximation to a given set of v

ij'

s than do the simple products v

£v

j

mentioned in Section 4.1.

Another rank-optimizable objective function is generated by

(4.2.7) <Kx,y) = » 0 < x < a .

This function relates to the case discussed in Section 2.1, where the

potentials v_^ are the outgoing, non-local mail volumes at location i,

n

v. = E v . , 1 • i in

3=1 J

the link volumes v.. are proportional to the non-local mail volumes at

the destinations j (2.1.1)

v. . = p .v. ,

and volume is to be maximized. Clearly

v. = E v . . = p . E v . =p. (V-v . ) , 1 ... 11 1./. J x 1

and therefore p^ = v_^/(V-v_j,), where V is total outgoing non-local mail

volume. Thus there is indeed a functional relationship between link

benefits and the potentials v^ of the form (4.2.7), which then establishes

rank optimizability (4.2.1).

- 37 -
5. RECOMMENDATIONS

Four different approaches have been evaluated in Parts 2-4:

(1) Use sequential methods such as the maximum increment method

to arrive at almost optimal networks for given numbers of installations.

(2) Use integer programming methods for determining "true" optimal

networks for given numbers of installations.

(3) Use the Rhys approach employing network optimization to cost

out installation expenses versus link benefits, thereby arriving at a suggested number of installations in optimal position.

(4) Approximate the link benefits by expressions in some associated site "potentials" by which to rank the sites.

Approach (2) does not appear suitable: the available mixed-integer

programming packages, when applied to the problem at hand, will most

probably be too expensive to run. Good algorithms specifically tailored

for the problem are not yet known. The necessity of finding a "true"

optimum, in view of the approximations necessarily involved in the

problem formulation, seems hardly urgent enough to warrant high computer

or research expenses.

The usefulness of approach (4) depends critically on the data., The

calculation of the best approximation may not be cheap, and there seems to

be no inherent reason why its results should be better than the ones derived

by the sequential methods of (l). A low level experimental and developmental

effort may nevertheless be rewarding.

Automation of the maximum increment method is definitely recommended.

This method will be able to rely mainly on ODIS data and provide an efficient and reliable configuration tool for EMS-studies. Its capabilities

include optimization of total transmissible volume as well as total service

improvement

.
A strong recommendation is to implement the Rhys approach.

The advantage of this approach is that it permits the inclusion,

interpretation, and evaluation of marketing information for a straight

cost-benefit analysis. The approach addresses the problem of how many

installations can be justified, not just how to deploy a prescribed

number of them. Even in the absence of cost and marketing information,

the Rhys approach can be definitely useful for parametric analyses over

a wide range of critical variables.

The power of the Rhys approach is not restricted to the problem at

hand, but can be used in other system planning problems. The

implementation of this approach would provide a quite general planning

tool of considerable potential.

- 39 -
6 • REFERENCES

[I] R. Ruckman: Electronic Mail Handling Network Conceptualization

June 1972. U.S. Postal Service Document.

[2] E. Sherrard: Two Networks for Electronic Transmission of Interoffice

Mail, Sept. 1973. U.S. Postal Service Document. ''r

'

[3] ODIS Data-base; Origin-Destination Information System.

Data Collection Procedures

Methods Handbook M-61

United States Postal Postal Service, Dec. 1972.

[4] J.M.W. Rhys: A Selection Problem of Shared Fixed Costs and Network

Flows, Management Science, JL7, 200-207, 1970.

[5] J.C. Picard and H.D. Ratliffe: Minimum Cuts and Related Problems,

Research Report No. 74-6, Industrial & Systems Engineering Department,

University of Florida, Gainesville, May 1974.

[6] C. Witzgall: An All-Integer Programming Algorithm with Parabolic

Constraints, SIAM J., 11, 855-871, 1963.

[7] F. Glover and E. Woolsey: Converting the 0-1 Polynomial Programming

Problem to a 0-1 Linear Program, Oper. Research, 22, 180-182, 1974.

[8] R.S. Garfinkel and G.L. Nemhauser: Integer Programming, John Wiley,

New York 1972. '

[9] S.I. Gass: Linear Programming, 3rd edition, McGraw-Hill, New York,

1969. —

[10] L.R. Ford and D.R. Fulkerson: Flows in Networks , Princeton University

Press, Princeton, N.J. 1962.

[II] W.A. Horn: Oral communication, June 1974.

[12] General Dynamics : Study of Electronic Handling of Mail. Collection

and Distribution. Report R69-046-2, March 1970.

[13] C. Witzgall: Methods for Synthesizing Networks of Electronic Mail

Systems. Letter report to USPS, July 1974.

USCOMM-NBS-DC - 40 -
NBS-114A (REV. 7-73)

U.S. DEPT. OF COMM.

BIBLIOGRAPHIC DATA

SHEET

1. PUBLICATION OR REPORT NO.

NBSLR 75-737

2. Gov't Accession

No.

3. Recipient's Accession No.

4. TITLE AND SUBTITLE

Mathematical Methods of Site Selection for Electronic

Message Systems (EMS)

5. Publication Date June 1975

6. Performing Organization Code

7. AUTHOR(S)

Dr. Christoph Witzgall

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

1 1 I nntr 9 f*t / (1 rani* Mr\

12. Sponsoring Organization Name and Complete Address (Street, City, State, ZIP)

United States Postal Service

R&D Dept., 1711 Parklawn Drive

Rockville, Maryland 20852

13, Type of Report & Period

Covered

Final

14. Sponsoring Agency Code

15. SUPPLEMENTARY NOTES

16. ABSTRACT (A 200-word or less (actual summary of most significant information. If document includes a significant

bibliography or literature survey, mention it here.)

The concept of electronic message (mail) transmission has been

the subject of several feasibility studies during the past decade.

It requires the installation of electronic message handling facilities

at selected locations. If transmission is to be via communications

satellite, then any such facility can transmit to and receive from any

other one. In this report, the mathematical aspects of choosing the

number and locations of these facilities are examined. An inventory

of solution methods is presented, along with recommendations as to

which among them should be employed or developed further.

17. KEY WORDS (six to twelve entries; alphabetical order; capitalize only the first letter of the first key word unless a proper name; separated by semicolons) Communication; cost-benefit ; deployment; electronic transmission

facility location; mail; mathematical programming; message network synthesis;

network optimization; satellite; service improvement.

18. AVAILABILITY H Unlimited 19. SECURITY CLASS

(THIS REPORT)

21. NO. OF PAGES

1 1 For Official Distribution. Do Not Release to NTIS

UNCL ASSIFIED 44

1 1 Order From Sup. of Doc, U.S. Government Printing

Washington. D.C. 20402. SD Cat. No. C13

Office 20. SECURITY CLASS

(THIS PAGE)

22. Price

IX 1 Order From National Technical Information Service

Springfield, Virginia 22151

(NTIS)

UNCLASSIFIED $ 3-75

USCOMM-DC 29042-P74