I

I

1 OHIO

UNIVERSITY

I

I

I

I

I

I

l

I

I

I

I

I

I

I

I

//¢"/3

i/i_,

ON ORBITAL ALLOTMENTS

FOR GEOSTATIONARY SATELLITES

David J.A. Oonsalvez

Charles H. Reilly

Clark A. Mount-CampbeU

The Ohio State University

ElectroScienceLaboratory

Department of Electrical Engineering

Columbus, Ohio 43212

Technical Report 718688-2

Grant NAG 3-159

November, 1986

National Aeronautics and Space Administration

Lewis Research Center

21000 Brookpark Rd.

Cleveland, Ohio 44135

(bAS_-C_-181617) Cl_ C_£IIAJ. A_ICI_ENT5 EGB

C-kCS_IIC_h_ SA_LLI_,_S (Chio 5rate Univ.)

151 _ Avail: N_IS HC A08/?.} A(_I CSCL 03C

G3/13

N87-227CG

Uncla_

0077627
NOTICES

When Government drawings, specifications, or other data are

used for any purpose other than in connection with a definitely

related Government procurement operation, the United States

Government thereby incurs no responsibility nor any obligation

whatsoever, and the fact that the Government may have formulated,

furnished, or in any way supplied the said drawings, specifications,

or other data, is not to be regarded by implication or otherwise as

in any manner licensing the holder or any other person or corporation,

or conveying any rights or permission to manufacture, use, or sell

any patented invention that may in any way be related thereto.
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

5O272 -tO_

REPORT DOCUMENTATION PAGE 1 '" REPORT NO" 1z"

4. Title and Subtitle

ON ORBITAL ALLOTMENTS

FOR GEOSTATIONARY SATELLITES

7. Author(s)

David J.A. Gonsalvez_ Charles H. ReiUy xClark A. Mount-Cam_pbell '

9. Performing Orl|enization Name end Address

The Ohio State University Eb'*'troScience Laboratory

1320 Kinnear Road

Columbus, Ohio 43212

12. Sponsorin i Orl|lnizetion National Aeronautics and Space Administration

Lewis Research Center

21000 Brookpark Rd.

Cleveland, Ohio 44135

]15. Supplementary Notes

3. Recip,ent's Accession No

S. Report Date

November_ 1986

6.

I. Performing Orlenizetion Rapt. No

718688-2

10. ProleCt/Task/Work Unit No.

!1. Contract(C) or Grant(G) No

(C)

(G) Grant NAG 3-159

13. Type of Report & Pertod Covered

Technical Report

14.

16. Abstract (Limit: 200 words)

The following satellite synthesis problem is addressed: communications satellites are to be

allotted positions on the geostationary arc so that interference does not exceed a given acceptable

level by enforcing conservative pairwise satellite separations. A desired location is specified for

each satellite, and the objective is to minimize the sum of the deviations between the satellites'

jL_....................................

Two mixed integer programming models for the satellite synthesis problem are presented.

Four solution strategies, branch-and-bound, Benders' decomposition, linear programming with

restricted basis entry, and a new switching heuristic, are used to find solutions to example synthesis

problems. Computational results indicate the switching algorithm yields solutions of good quality

in reasonable execution times when compared to the other solution methods.

It is demonstrated that the switching algorithm can be applied to synthesis problems with the

objective of minimizing the largest deviation between a prescribed location and the corresponding

desired location. Furthermore, it is shown tlmt the switching heuristic can use no conservative,

location-dependent satellite separations in order to satisfy interference criteria.

17. Document Analysis a. Descriptors

b. Identifiers/Open-Ended Terms

c. COSATI Field/Group

IS. Availability Statement

A. Approved for public release; distribution is unlimited. [_.

See ANSI-Z39.IS) See Instructions on Reverse

19. Security Unclassified Class (This Report)

Secority Cl|ss (This Pale)

Unclassified

21. Nn of Pales

150

22. Price

OWrlONAL FORM 272 (4--77)

(Formerly NTIS-35)

Department of Commerce
I

I

l

l

I

I

l

I

I

I

l

I

I

I

I

I

l

I

I

TABLE OF CONTENTS

LIST OF TABLES .............................

LIST OF FIGURES ............................. vi

I. INTRODUCTION ........................... 1

II. PROBLEM DESCRIPTION AND BACKGROUND ................ 8

2olo

2.2.

2.3.

Mathematical Programming Formulation of the

Satellite Location Problem ................. I0

The Concept of Minimum Required Satellite

Separation (AS) ...................... 13

Literature Review ...................... 16

III. THE FOUR SOLUTION TECHNIOUES ................... 21

3 • 1 • ....... _LA_U Irite ge r LI _ea_ PEo gramm In g . . . . . . . . . . . . , . 21

3 • 2 • Benders' Decomposition • • • • • • • • • • • • • • • • • • . 25

3.2.1. On Solving the Master Problem ............... 33

3.2.1.1. The Fixed Interval Line Search ............. 35

3.2.1.2. The Golden Section Search Method ............ 37

3.2.1.3. The Rounded Linear Programming Solution ......... 38

3.2.1.4. The Subgradlent Method ................. 39

3.2.1.5. The AdJustment Method .................. 41

3.2.2. Generation of Bounds on the Optlmal Solution to

the Master Problem .................... 43

3.3. Linear Programming with Restricted Basis Entry ....... 46

3.4. The Switching Method .................... 48

IV. EMPIRICAL STUDY OF THE FOUR SOLUTION TECHNIOUES .......... 56

4olo

4.2.

4.3.

4.4.

4.5.

4.6.

Implementation of the Mixed Integer Programming Method . . . 56

Implementation of the Benders' Decomposition Method ..... 57

Implementation of the Restricted Basis Entry Method ..... 62

Implementation of the Switching Technique .......... 63

Generation of the Test Problems ............... 69

Discussion of the Experimental Results ........... 71

II:_IECEDII_tGPAgE _..A_ r,_T F[Lk,_D

°°°

111

_I,,,._JN,TENBONALLY BLANK
V. SWITCHING HEURISTICS FOR VARIATIONS IN THE SATELLITE

LOCATION PROBLEM ......................... 74

5.1.

5.2•

5.3•

Minimization of the Maximum Deviation of Prescribed

Locations from the Corresponding Desired Locations ..... 75

Feasible Arc Constraints for the Satellite Location

Problem ........................... 78

Experimental Results for the Satellite Location

Problem with Different Objective Functions and

with Feasible Arc Constraints ................ 85

On Using A_ in Place of AS ................. 93

Application of the Switching Heuristic to the

Region 2 Scenario ...................... 99

Vl. RECOMMENDATIONS AND CONCLUSIONS .................. 103

601.

6.2.

6.3.

6•4•

The Allocation of Arc Segments to Service Areas ....... 103

The Explicit Allocation of Frequency Channels ........ 109

On the Possible Application of the Switching

Heuristics to Classes of Job Scheduling Problems ...... iii

Conclusions ......................... 112

APPENDICES

A. A Demonstration that Lagrangean Multipliers for the

Optimum Solution to the Benders' Master Problem May

Not Exist .......................... 114

B. Identification of Redundant AS Values Once the

Satellite Ordering Is Specified ............... 117

C. On Avoiding the Repetition of Satellite Orderings

in a Major Iteration .................... 120

D. The Seven Test Scenarios .................. 124

E. The Region 2 Scenario ..................... 135

LIST OF REFERENCES • . • . • • . • . • • • • . • • . • • . • • • • • • • 139

iv

I

I

I

I

I

I

l

I

I

I

I

I

I

I

i

I

!

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

TABLE

I.

2.

o

o

,

,

.

LIST OF TABLES

Comparison of the performance of the four solution methods

Switching heuristic runs on the seven scenarios with the

objective of minimizing total deviation and with limits on

the feasible arcs ......................

Switching heuristic ru_s on the seven scenarios with the

objective of minimizing maximum deviation and with limits

on the feasible arcs ...................

Comparison of the switching solutions to MIP solutions

- Minimize total deviation (with feasible arcs) ......

Comparison of the switching solutions to MIP solutions

- Minimize maxim_n deviation (with feasible arcs) .....

Comparison between switching with /k_ and switching with /kS

- Minimize total deviation (with feasible arcs) ......

Comparison between switching with /k@ and switching with /kS

- Minimize maximum deviation (with feasible arcs) .....

8. Results of runs with the Region 2 scenario ........

PAGE

72

86

88

91

92

96

97

I01
FIGURES

1.

2.

3.

4.

LIST OF FIGURES

PAGE

A simplified satellite system and interference geometry . . 4

Mathematical formulation of the satellite location problem II

Variation in /k_ with satellite location ........ . 15

0-I Mixed integer formulation of the satellite location

problem .......................... 23

5. 0-1 Mixed integer formulation of the satellite location

problem {Constraint matrix contains only +1,-1, or 0) . . . 24

6. 0-1 Mixed integer formulation of the satellite location

problem (Used in Benders' decomposition) ......... 28

7. The master problem in Benders' decomposition ....... 30

8. The subproblem (primal) in Benders' decomposition ..... 31

9. The subproblem (dual) in Benders' decomposition ...... 32

10. The Lagrangean relaxation formulation of the master problem 34

11. "Almost" linear programming formulation of the satellite

location problem with complementarity constraints ..... 47

I2. Primal linear programming formulation for the satellite

location problem with satellites in a given ordering . . . 51

13. Dual linear programming formulation for the satellite

location problem with satellites in a given ordering • . . 52

14. Flow chart for Benders' decomposition as applied to the

satellite location problem ................ 58

15. Flow chart for the switching heuristic .......... 64

16. The primal formulation for the satellite location problem

with the objective of minimizing the maximumdeviationand

for a given ordering ................... 77

vi

I

I

I

I

I

I

I

I

I

I

l

I

I

I

I

I

I

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

17.

18.

19.

20.

21.

The dual formulation for the satellite location problem

with the objective of minimizing the maximum deviation

for a given ordering ................... 79

The dual formulation for the satellite location problem with

feasible arcs - the objective function is the minimization

of total deviation .................... 82

The dual formulation for the satellite location problem with

feasible arcs - the objective function is the minimization

of maximum deviation ................... 83

The primal formulation of the linear program for the arc

segment allocation problem with a given ordering of the arc

segments ......................... 106

The dual formulation of the linear program for the arc

segment allocation problem with a given ordering of the arc

segments ......................... 108

vii
I

I

I

I

I

I

I

I

I

l

I

I

l

I

I

I

I

I

One of the major advances in the technology of communications has

the use of satellites in geostationary orbit as broadcast and

relay stations for various types of commmEdcations signals. Arthur C.

Clarke [1945] suggested using a chain of satellites in order to

broadcast television proErsms over the entire earth; the orbit he

suggested for these satellites has since come to be known as the

geostationary orbit.

The geostationary orbit is located in the equatorial plane at a

distance of 42000 _n from the center of the Earth. The orbital period

of a satellite in such an orbit is 24 hours; therefore, for a

terrestrial observer the satellite appears to be fixed in the sky.

When transmitting signals in the microwave spectrum, a transmitting

station on the surface of the Earth has an effective broedcast ranEe of

perhaps 50 to 100 kin, depending on the tower height aud the terrain.

On the other hand, a satellite in Eeostationary orbit can brosdcast a

signal beam that will cover up to one third of the globe.

In the past two decades, a number of nations, private companies,

and multinational consortia of private companies have placed satellites

in the Eeostationary orbit in order to improve their communication
2

capabilities. Quite socm it was realised that the unique geostationary

orbit and the usuable frequency spectrum are limited resources. Hence,

by international agreement, it was decided that a series of World and

Regional Administrative Radio Conferences (e.g., WARC-77, RARC-83,

WARC-85, WARC-88), facilitated by the International Telecommunications

Union (IqIJ), would generate allotments which would specify how these

resources are to be distributed among the nations of the world.

Problems in resource allocation are frequently solved by applying

optimization techniques to appropriate mathematical programming models.

The resource allocation problems associated with satellite deployment

in the geostationary orbit can be modelled as mathematical programs.

Consequently, the application of optimization techniques in the field

of satellite system planning has aroused considerable interest in the

international communications community.

The optimization problems associated with the distribution of the

orbit/frequency spectrum resource are c_%sidered to be extremely

difficult to solve. The complex interactions between the system

geometry, the size, shape, and location of the areas (nations, portions

of nations, or combinations of nations) being serviced, and the nature

of electronic transmissions make developing and solving an optimization

model of the entire system difficult. The system geometry, the service

areas, and the equipment used for transmission and reception determine

the strength of the signals from transmitting satellites that are

received at earth station receivers in the service areas. Hence, these

factors also determine the .... adequacy of the system.

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

l

I

I
I

I

I

I

I

I

I

I

I

I

a

I

i

|

I

i

i

I

i

3

For the Broadcasting Satellite Service (BSS), a scenario is

defined as adequate if the resulting overall equivalent protection

margins, calculated in decibels (dB) at suitable receiver locations,

are all positive numbers. These margins are a complicated function of

the desired signal strength, the strengths of the interfering signals,

and the frequency separations between the carrier of the desired siEnal

and those of the interfering signals (WARC ORB-85 [1985] ). Wang

[1986] has shown that this requirement is the same as requiring the

ratio of the desired carrier signal to an equivalent interfering signal

to exceed a threshold value. In the case of all satellites

transmitting at the same frequency (only co-channel interference), the

equivalent interfering signal power is the same as the aggregate

interference power, i.e., the sum of the powers (in Watts) of all the

interfering signals. In this case, the requirement for positive

equivalent protection margins is satisfied if the ratio of the desired

signal power C to the aggregate interference power I (aEEreE_te C/I

ratio) exceeds the required protection ratio.

No international agreement has been reached on the procedure to be

adopted for the Fixed Satellite Service (FSS), but the same type of

requirement appears applicable for the down-link calculation. The

problem addressed here is the optimization of FSS orbital allotments on

the basis of only down-link considerations.

In Figure 1 a simplified system is shown. There are two service

areas A and B with their boundaries indicated by continuous curves.

Each has its own satellite, denoted by S, and Sn, respectively. A

signal broadcast from SA to service area A has some desired strength at
Geostationary

orbit

Ear th

desired signal path

interfering signal path

A , B - service areas

SA , $8 - satellites broadcasting to service areas \ and B

respectively

Fio_ure I. A Simplified Satellite System and Interfer'ence Geometr_ _

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

5

all points on the dotted ellipse surrounding A. The strength of the

signal intensifies as one moves toward the center of the ellipse.

Since a portion of the ellipse covers parts of service area B, if

satellite Ss were transmitting to country B at the same frequency and

polarization as S,, then there would be considerable interference from

S, in country B.

The reduction of such spillover interference to as low a level as

possible, or at least to a level that satisfies some desired protection

ratio, is an essential part of the optimization problems associated

with satellite communications in the geostationary orbit.

Simultaneously, requests for satellite orbit locations and frequency

channel assignments that are made by the administrations of service

areas have to be satisfied to the greatest extent possible.

The positioning of satellites, the allocation of frequencies, and

the assignment of polarizations, have a major economic impact on most

nations of the world. It is surprising that, although the installation

of a system of broadcast satellites can cost upward of a billiom

dollars, there have been only a few efforts to optimize the orbit

locations of these satellites and the frequency assignments.

In this research, the focus is on one of the optimization problems

associated with the allotment of communications satellites, namely, the

satellite location problem. This problem is defined here as the

minimization of the deviation of assigned satellite locations from

given desired locations, subject to meeting the required protection

ratio. Four methods for solving this problem are presented : mixed

integer programming, Benders' decomposition, a restricted basis entry
6

procedure, and a switching heuristic. Solutions are obtained for some

real problems using the four methods, and the performance of the four

solution techniques is evaluated. A parallel is drawn between the

formulation of the satellite location problem and some classes of

scheduling problems.

In Chapter 2, the satellite location problem is formulated as a

nonlinear mathematical programming problem. The concept of minimum

required satellite separation, which is essential to the development of

the formulations and solution methods described in this manuscript, is

presented in Chapter 2. A review of other satellite allotment problems

and associated solution methods which have appeared in the literature

is provided in Chapter 2.

The four solution methods are discussed in detail in Chapter 3,

along with a review of past work with similar techniques. In the same

chapter, other mathematical proEramming formulations for the satellite

location problem are presented. These formulations avoid the

nonlinearities in the formulation given in Chapter 2 through the use of

variables restricted to integer values or through the implementation of

complementary variables (pairs of variables, one of which al_ys has to

be zero).

The specific details of the implementation of the four solution

methods in computer codes are presented in Chapter 4. Experimental

results obtained using the solution methods on a set of test problems

are also discussed in the fourth chapter.

In Chapter 5, the versatile nature of the fourth solution method,

the switching heuristic, is explored. Its application to alternate

I

I

I

I

I

I

i

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

il

I

I

I

I

I

I

I

I

I

I

i

I

7

formulations of the satellite location problem with different objective

functions or with feasible arc limitations is considered. The ability

of the heuristic to allow for minimum required orbital separations that

vary with satellite location is also discussed in the fifth chapter.

Experimental results for these variations are presented.

Chapter 6 consists of a summary of the research and its

contributions to the area of satellite system synthesis and the field

of Operations Research. Recommendations for future work in the

application of the switching heuristic to problems related to the

satellite location problem are also presented in the same chapter.
CHAPTER II

PROBi/_D_IPTI_AND_GROUND

In Broadcasting Satellite Service (BSS) and Fixed Satellite

Service (FSS) system synthesis, a common objective is to provide every

user with si&_als that are adequately protected from interference by

other users (Christensen [1981], WARC [1985]). There are two basic

ways that a system can be designed to accomplish this. The first way

adequate protection can be achieved is by providing sufficient physical

separation in orbit between the satellites that interfere with one

another. The second option is to provide sufficient frequency

discrimination through the allocation of adequately separated channels

to possible interferers. The allotment procedure, therefore, has to

specify orbit locations and frequency channel assignments for

satellites so as to achieve the goal that every desired signal is

adequately protected from interference. Constraints, such as the

satellite locations having to be within the arc visible from the

corresponding earth stations and the channel assignments having to be

made from a given frequency spectrum, are also pert of the satellite

system synthesis. In addition to meeting the above criteria the system

design will have to satisfy, to the greatest extent possible, various

requirements that might be requested by the governments of the

8

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

!

I

I

il

il

I

I

I

I

I

I

I

I

I

I

I

9

countries involved. Otherwise, there would be little hope of reaching

international agreement on any allotment scheme.

The amount of separation that is required between satellites and

between frequency channel assignments to provide the required

protection from interference is a function of the design parsmeters of

the satellite and the receiving earth station. Since various nations

have vastly differing economic and technological capabilities,

technical desiEn persmeters are largely left to the discretion of the

individual administrations, subject to meeting certain standards agreed

to by all the participating nations. At present, the technical design

parameters for ind/vidual administrations are not available as

variables that can be adjusted to optimize the system design. For the

purposes of this research, a fixed and known level of technology for

all satellites and earth stations is assumed.

The problem under consideration is the satellite location problem.

In essence, this problem involves the assigmment of satellite locations

to administrations so as to meet signal adequacy cTiteria, subject to

visible arc and elevation angle requirements. Frequency allocation is

not treated as part of the problem -- the ass_aption is either that the

full frequency bandwidth is assigned to all administrations or that the

frequency assignments are pre-specified.

If the system synthesis problem can be solved through the

assignment of satellite locations only, then that solution is

preferable to one which assigns both satellite locations and

frequencies. WARC ORB-85 [1985] tentatively recommended to the second

session of the conference that each ITU member should receive at least
I0

one allotment consisting of an orbital position with which a bandwidth

of 800 _z is associated in certain up-link and down-link bands

totalling 1600 MHz of bandwidth. This would appear to imply full

spectrt_ use in the case of at least these allotments. Hence the

assumption about full bandwidth frequeDx_y assignments is reasonable.

There has been a considerable amount of work done in the area of

frequency allocation, mostly in the area of ground based radio

communication. The satellite location problem is the focus of this

research, partly because it has not been studied as extensively as the

frequency allocation problem and partly because of the computational

advantages associated with the solution strategies which can be used to

solve it.

2.1 Mathematical Programming Formulation of the Satellite Location

Problem

In the course of this research, several mathematical programming

techniques are applied in order to solve the satellite location

problem. In Figure 2, a basic mathematical formulation of the problem

is presented. Variables and pamameters are defined along with the

formulation in Figure 2. Later, this formulation is modified and built

upon. The nature of the problem, the assignment of satellite locations

satisfying the signal adequacy criteria, will remain the same

throughout this manuscript.

I

I

I

I

I

I

I

I

I

I

I

i

I

I

I

I

I

I
I

l

n

l _N'Z_ _ ( x+x] + )

subject to

| g +X +-X _ ; d

J J J J

I :x -x : > Zls

i j - ij

(2.1)

j:l,...n (2.2)

i:l,...n-1 (2.3)

j=i+l,...n

E < X < W __i ...n l, 4_

j- j- j

X., X., X > 0 j:l,...n (2.5)

,J o J11

l

l

l

I

I

l

X : actual location of satellite j

J

+

X , X = distance between assigned and desired locations of

J J

satellite j to the east and west, respectively

d = desired location for satellite j

J

/kS.. : minimum orbital separation required between

Ij

satellites i end j

E , W : eastern and western limits, respectively,

J J

on feasible locations for satellite j

n : number of satellites

: a : : absolute value of a

Figure 2. Mathematical Formulation of the Satellite Location Problem
12

The objective function (2.1) used here and for most of the

research described herein is the minimization of the sa_ of the

deviations of the assigned locations of satellites from given desired

locations. From now on, this objective will be referred to as

minimizing the total deviation.

Constraints (2.2 ) measure the deviations of the assigned

locations from the corresponding desired locations. Constraints (2.3)

enforce the required minimum satellite separations (/_S) between pairs

of satellites. Constraints (2.4) require a satellite to be located

within a given feasible orbital arc. Constraints (2.5) are nonnegativity constraints on the decision variables.

The absolute value of the difference between two decision

variables appears in constraints (2.3). As a result the program is

nonlinear. The measurement of this absolute value in terms of the

decision variables is what makes the problem difficult to solve in the

context of mathematical progrsmming. In Chapter 3, alternate

nonlinear and mixed integer progrsmming models for the same problem are

presented.

This model also uses the concept of the minimum required orbital

separation between pairs of satellites (/_S). This concept simplifies

mathematical programming formulations for the satellite location

problem considerably, since without it all the complex calculations to

determine interferences would have to be included in the formulation.

In a sense, the calculation of /_S acts like a preprocessor allowing

the mathematical programming techniques to focus on the optimization

rather than on the demanding interference computations. Levis et al.

i

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

I

I

I

I

l

l

I

i

I

I

I

I

13

[1983a] provide a formulation that includes the interference

calculations, and the extreme complexity of that formulation as

compared to the simplicity of formulations using /kS is easily

observable. In the next section, the satellite separation concept is

discussed in more detail.

Finally, it should be noted that all satellite locations are

required to be non-negative. This implies a rescaling of parameters

from the conventional negative and positive longitude system (-180" to

+180o). Here, the eastermmost boundary amonE all the feasible arcs is

designated as 0 degrees, and all other longitudes are correspondingly

adjusted.

2.2 *'he concept of minimum required satellite separation (/kS)

The minimum separation required between a pair of satellites i and

j, in order to provide adequate co-channel signal interference

protection to each from the other at ground stations on the boundaries

of their respective service areas, is denoted by /kS ij. By using these

separation values for all pairs of satellites, the nonlinearities and

trigonometric functions arising from the system geometry and the

antenna and frequency discrimination functions can be avoided in the

mathematical programming formulations.

Christensen [1981] and Ito et al. [1979] have devised solution

methods for satellite synthesis problems which use the concept of

minimum orbital separation matrices. In this research, the separation
14

concept as developedby Wang[1986] is used. Wangdefines the minimum

required orbital separation between two satellites i and j as

/ksi_ " _ { /_j,, } (2.6)

k6'K

where K corresponds to a set of locations equally spaced in the common

feasible arc of satellites i and j, ___i jk is the required separation

between satellites i and j when the separation is centered at location

k, and this separation is such that the signals of both satellites are

sufficiently protected from a single entry oo-channel interference

level which has been selected as likely to result in meeting aggregate

interference protection ratio requirements. If the feasible arcs for

the two satellites do not overlap, the required separation is

calculated with the center of the separation being the midpoint between

the closest endpoints of the two feasible ar_s. The iterative

procedure for calculating /kS is described in Wang [1986].

There are two issues that have to be considered with the

definition of the minimum required orbital separation given above.

1. As indicated earlier, /kSij is the maximum of /_.__t.tk over the

feasible arcs of satellites i and j. A functional relationship can be

established between /k_| jk and the longitude in the center of the

separation between the satellites i and j, and for most pairs of

satellites the shape of the function is as shown in Figure 3.

It can be seen that the variation in /_ is not great when the

satellites move from a position directly over the service areas. The

increase in /k_ is more rapid at low elevation angles. Occasionally

the function is concave rather than oonvex - this occurs when the

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

[5

East of

service areas

Directly over

service areas

West of

senice areas

Location of longitude inbetween and equidist,%nt from satellites

Figure 3. Variation in/_¢ _ith Satellite Location
16

service areas being served by the satellites are separated by latitude

but not by longitude ( Yamamura and Levis [1985] ).

In the mathematical programming formulations developed for the

satellite location problem, the maximum required separation value /_S

is used. As a result, the solutions obtained will always satisfy

single entry interference requirements, but might be oonservative in

that the actual separations between satellites may exceed the

separation required to meet the signal protection ratio criterion for

the assigned satellite locations. The case might also arise that while

the actual problem has a feasible solutiun our formulations might be

unable to find it, owing to the usage of the conservative maximu.

separation AS. In Chapter 5, some comparison studies in the use of

l__ ij_'s in place of /kS i_'s are discussed.

2. The calculation of /_S values considers only single entry cochannel interference, and, therefore, any solution found may not meet

the equivalent margin requirements for aggregate multi-channel

protection. This problem can be alleviated to some extent by increasing

the single entry protection ratios so as to make it likely that the

required aggregate multi-channel protection will be achieved.

2.3 Literature Review

In this section, previous work done on the problems of satellite

location and frequency allocation is reviewed.

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
!

!

I

I

!

I

I

I

I

I

i

I

I

I

I

I

I

I

i

17

At the preparatory seminar for the 1983 RARC (Regional

Administrative Radio Conference) in Ottawa, Canada, in 1981, the

Canadian delegation presented a method for generating BSS allotments.

The overall objective was to assign orbital locations, frequencies and

polarizations to service areas so that the capacity of the

spectrum/orbit resource was optimally used, subject to protection ratio

and technical constraints. The method _s a combination of manual

synthesis and automated heuristic procedures. Christensen [1981]

provides a comprehensive review of the entire system and its

development. The system was based on the ideas of Chouinard and Vachon

[1981] and Nedzela and Sidney [1981]. It involved an initial

generation of service area clusters by the user fr_.._^k.i,_, transmission

discrimination and minimmJm required orbital separation matrices were

generated. C_m%neis and polarizations were manually assigned and the

plan was checked for satisfaction of protection ratio requirements. At

this point, the user had several choices - a neighbourhood search,

manual assignment changes, generation of new cluster configurations, or

termination. The system was tested on some BSS problems with limited

success. No results of applications to actual problems are available.

Levis et al. [1983a] formulated a nonlinear programming model for

BSS synthesis and developed a gradient search pr_)cedure that was

applied to some small BSS problems. They attempted to assiEn orbit

locations and frequencies so as to minimize the worst protection ratio

violation. Reilly et al. [1986] implemented a cyclic coordinate method

for the same model, and performed an experiment to assess the

performance of the two methods on synthesis problems. They foumd that
18

the cyclic coordinate method outperformed the gradient search technique

for the set of BSS test problems used in the experiment.

Ito et al. [1979] proposed two methods for the optimization of

satellite locations in the geostationary orbit. These methods have

been applied to small problems with some success and led to the

development of ORBIT-II, an orbit spacing minimization progrsm [1984].

They formulate the problem as a nonlinear programming problem which

attempts to minimize the length of the orbital arc occupied by the

satellites to be positioned, subject to meeting single entry and

aggregate interference criteria. The first solution method uses a

penalty function algorithm which is commonly used in nonlinear

programming, and the second uses successive linear approximation of

non-linear constraints.

In the literature om satellite system synthesis, the approaches

presented by Christemsen and Ito et al. are the only methods that have

actually been applied to the satellite location and frequency

allocation problems. No ccmgutational experience is reported for

problems involving more than I0 satellites with any of these methods.

Ottey et al. [1986] have proposed the use of several optimization

techniques on a set of variations of the satellite location and

frequency allocation problems - the variations mainly being in the

objective function. They do not indicate whether any attempt at actual

implementation of the methods they propose has been made.

In actual scenario generation, there has been considerable use of

interactive synthesis methods. These methods essentially oomsist of am

experienced system designer generating a seem6rio which is then

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

19

evaluated using an analysis program. The designer can vary the

scenario based on the results of the analysis. This method was used in

generating the BSS scenario for Region 9 (North, South and Central

America) at RARC '83.

The frequency allocation portion of the problem has received

considerable attention in the literature, since it is similar to the

frequency allocation problems of land-based radio broadcasting.

channel to each service area so as to minimize the number of channels

required, subject to restrictions on co-channel assignments to

interfering service areas. He observed that the problem could be

formulated as a graph colouring problem, and proposed solving it by

solving a sequence of minimum cardinality set covering problems.

Baybars [1982] formulated th_ same problem as a 0-I programming problem

and added additional constraints to restrict adjacent channel

assignments. He used graph theoretic results to establish bounds on

the solution and presented empirical results for some small problems.

Zoellner [1973 ] investigated frequency assignment strategies

under the condition that the assigner does not possess prior

information about successive cases that will require assignment.

Zoellner and Beall [1977] assume c_mplete knowledge of all the

assignment cases that must be accommodated. In both studies node

colouring order based assignment procedures are used.

Levis et al. [1983b] indicate alternate set covering formulations

for the frequency assiEr_ent problem. They also provide a formulatien

for multiple channel assignments.
2O

Mathur et al. [1985] develop integer programming models for the

frequency assignment problem with the constraints that intermodulation

interference is maintained within desirable limits. They also consider

the incremental problem of adding to an existing network. The context

of their work is ship-to-ship transmissions, but the models can be

applied to satellite transmissions.

Fiizuiki et al. [1984] propose a method of evaluating co-channel

interference in terms of the margin with respect to the minimum

required carrier-to-interference protection ratio. They generate an

interference matrix and use it to allocate frequencies with an

assignment problem approach.

For analysis purposes, a program such as SCUP [1983] (Spectrum

Orbit Utilization Program) can be used to evaluate scenarios. The

program's features make it extremely useful in analysing a solution

generated by a synthesis procedure. SOUP is also capable of measuring

the impact of using satellite separations based on single entry cochannel interference, e.g. /_S, to find solutions to synthesis problems

where aggregate interference levels have to be below threshold values.

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

!

I

I

CHAI_ III

THE FOUR SOLUTION TECHNIQUES

In this chapter, four solution techniques for the satellite

location problem are presented. These techniques are mixed integer

linear progrMminE, Benders' decomposition, linear progrsmming with

restricted basis entry, and a switching heuristic. In each case, the

corresponding math_natical progrsmming formulations are discussed, and

past applications of the technique, and variations thereof, that have

appeared in the literature are reviewed. The specific implementations

and modifications that are used in this research are also mentioned.

The minimization of total deviation is the objective function used for

the satellite location problem throughout this chapter.

3.1 Mixed Integer Linear Programming

Mixed integer linear pro_, hereafter referred to as mixed

integer progrmnming or MIP, is a widely used technique in the field of

mathematical progrsmming. Garfinkel and Nemhauser [1972] provide a

comprehensive suwmary of momt of the com_n classes of problems that

can be solved using this method and an in-depth review of several

implementation strsteEies. The most ommnon strateEy used for problems

21
22

with no special structure is that of enumeration, which is usually

implemented using some version of a branch and bound technique.

The satellite location problem, as formulated in Figure 2, is not

an MIP formulation since it is not linear and none of the decision

variables are restricted to integer values. To convert that

formulation into a mixed integer progrsm the non-linear constraints are

replaced with a combination of integer variables and linear

constraints. This MIP formulation is given in Figure 4. The nonlinear constraints (2.3) of the formulation in Figure 2 are replaced by

the constraints (3.3) and (3.4) and the binary variables denoted by

Yi,{.

The objective function in the MIP (3. I) is identical to that in

the first formulation (2.1 ). Constraints (3.2), (3.5 ), and (3.6) are

identical to constraints (2.2), (2.4), and (2.5), respectively, in

Figure 2. Together, constraints (3.3), (3.4), and (3.7) enforce the

minimum required orbital separation between pairs of satellites.

An advantage of using an MIP model is that the optisman solution is

always found if the given problem is feasible. The drawback is that

the computational requirements for solving the problem tend to grow

exponentially as the problem size (in terms of the n_nber of integer

variables) increases. By applying this technique to small problems a

standard, the optimum solution, is obtained against which the

performance of heuristic methods can be compared.

The model shown in Figure 4 can be reformulated into a more

elegant model by rescaling. The advantage of this reformulation

(Figure 5) lies in the fact that the constraint matrix consists of

i

i

i

I

I

i

i

I

i

i

I

I

I

I

I

I

l

I

I
I

I

I

I

I

I

I

I

I

I

I

!

I

I

I

I

I

23

n

_'- + -

+ x )

j=/_T ( xj J

subject to

X +X -X

J J

=d

J

X -X + (e-w-Zls..) Y.. _> (e-w)

i j ij Ij

-X + X - (e-w-Zis..) Y > /kS..

i j Ij ij - ij

E _< x < w

o J- j

4-

X ,X ,X > 0

o J J -

Y :Oorl

ij

where

(3.1)

j:l,...n (3.2)

i=l,...n-I (3.3)

j=i+l,...n

:i,...n-i (3.4)

:i+l,...n

j:l,...n (3.5)

j:l,...n (3.6)

i:l,. .n-I (3.7)

j:i+l_...n

u

X , X. , X , d , /kS.. , E , W. , n are as defined in Figure 2.

J O j j 1O j O

e = mln {E } ; w = max [W.} ; j=l,...n

J J

Yij = I 01otherwiseif satellite i is located to the west of satellite j

Figure 4. 0-I Mixed Integer Formulation of the Satellite Location

Problem.
24

MINIMIZE

n

i-- + -

j/----I (X J + X J

subject to

X + X - X : d j:l,...n

J J J J

X - X + Y < I - L_S. i:l,. .n-I

i j ij - zj j:i+l;...n

X - X + Y > /kS i=l,. .n-I

i j ij - ij j:i+l;...n

E. _ X < W j=l,...n

J J - j

X , X , X > 0 j:l,...n

J J J -

(3.8)

(3.9)

(3.10)

(3.11)

(3.12)

(3.13)

: 0 or 1 i:l,...n-I

Yij j:i+l,,,,n

(3.14)

where

+

X , X. , X , d. , /kS.. , E , W. , n are as defined

J J J _ _j j J

in Figure 2 and scaled by {(w - e) + max /kS}

e = min {E } ; w : max {W } ; j:l,...n

j

(e and w are computed beforJe scaling)

Y = { 1 if satellite i is located to the east of satellite j

ij { 0 otherwise

Figure 5 . 0-I Mixed Integer Formulation of the Satellite

Location Problem.

( Constraint matrix contains only +I,-I or O)

I

I

i

!

I

I

I

I

I

I

!

I

I

I

I

I

I

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

25

elements that are either +1 ,-1 or 0. This permits the constraint

matrix (often called the "A" matrix) to be com_m_tly stored, and thus

allows for a more efficient handling of the basis. In mathematical

terms, the two models are equivalent.

3.2 Benders' Decomposition

Benders [1962] developed a method for decomposLnE large scale

mathematical proErsmming problems into "master" and "sub" problems,

which, when solved in an iterative fashion, yield the optimal solution

to the original problem. The advantages over solving the original

problem as a whole are that both the master problem and subproblem are

smaller and easier to solve and may posess some special structure which

facilitates their economical solution.

Benders' decomposition can be summarized as follows : A master

problem and a subproblem are derived from the original problem. A

master problem is solved, yielding a solution which defines a

subproblem. Next, a subproblem is solved or determined to be

infeasible. Dual solutions or extreme rays then define one or more

constraints or "cuts" for the master problem. These cuts are added to

the master problem. The new master problem is solved and the iterative

process continues. Finite convergence of the algorithm follows from

the finite number of possible constraints. The algorithm must

terminate, either with the information that the original problem is
26

infeasible or unbounded, or with the optimal solution, in a finite

number of iterations.

The concepts involved will become clearer as the development of

the Benders' decomposition model for the satellite location problem

progresses. An attractive feature of this method is the availability

of upper and lower bounds on the optimal objective function value. At

each iteration in the solution of a minimization problem, the upper

bound is the best solution found among all the subproblem solutions in

the current and previous iterations. The lower boumd is the optimal

solution to the current master problem. A test for optimality is the

condition that these bounds are equal.

In solving mixed integer programs with Benders' decomposition, it

is often the case that the best decomposition strategy occurs with the

master problem heine a pure integer program containing the integer

variables and the pure integer constraints. The subproblem is then a

linear program in the continuous variables and the remaining

constraints, the integer variables heine held fixed at the values

assigned to them in the optimal solution of the preceding master

problem.

Benders' decomposition has often been used in practice. In most

cases, some special structure in the master problem or subproblem is

exploited and problems that were computationally intractable with

respect to implicit enumeration techniques are solved quite

efficiently.

Sherali and Adams [1984] apply Benders' decomposition to a set of

discrete location allocation problems. They consider a master problem

I

I

I

I

i

I

I

I

I

I

I

I

i

I

!

i

I

i

i
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

27

in which they relax some of the integrality constraints and then solve

it using a partial enumeration scheme. The subproblem reduces to a

transportation problem. Geoffrion and Graves [1974] designed a multicommodity distribution system using this approach. Their problem

serves as a classic example of Benders' decomposition with the original

problem decomposing into a set of transportation problems when the

binary variables are held fixed. Federgruen and Zipkin [1984]

addressed a combined vehicle routing and inventory allocation problem

with a version of Benders' decumposition.

Mount-Campbell et al. [1986 ] have formulated the satellite

location problem as a mixed integer program. Their formulation is

shown in Figure 6. The objective is the minimization of total

deviation. In this formulation, satellites are assigned to positions

in an ordering; the locations of the positions are simultaneously

determined. Constraints (3.16) insure that there is only one satellite

assigned to each position, snd constraints (3.17) insure that each

satellite is assigned to some position. If satellite i is assigned to

position j, then the distance of position j from the desired location

of satellite i is measured by constraint (3.18). The minimum required

orbital separations between pairs of satellites are enforced by

constraints (3.19). Constraints (3.19) also ensure that positions with

a high index are west of positions with a low index. This formulation

is a relaxation of the problems formulated in Figures 2 and 4 because

of the absence of boundaries on the feasible arc for each satellite

location.
i

MINIMIZE

subject to

where

n

(Y +Y

J J J

n

i ij

n

j ij

1 j:l,...n

1 i=l,...n

n

!

28

!

(3.15)

!

(3.16) I

(3.17) H

Yj+ - = d X j=l,...n (3.18) j i i ij

Yj+k- Y j -/_Sih(Xij- > (l-X h,j+k ))

•.n-l;

_---]',[..n-j;

i=l, ••.n;

h=l, ...n

Y , Y , Y > 0 j=l,...n

J J J -

X = 0 or 1 i=l,...n; j=l,...n

ij

n : number of satellites and satellite orbit positions

Y : actual longitude of satellite orbit position j

J

(3.19) I

(3.20) I

(3.21)

!

Y÷Y: J ( ) : westward desired location (eastward)of distance the satellite of an inorbit that position position. from the !

X = 1 if satellite i is assigned to position j, 0 else

ij

/__Sih = required separation between satellites i and h

d : desired location for satellite i

i

Figure 6. 0-I Mixed.Integer Program for the Satellite Location Problem

_usea in J:_enaers" Decomposition)
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

l

I

29

Mount-Campbell et al. sugEest using Benders' decomposition to

solve the formulation given in Figure 6. The form of the master

problem and the subproblem are indicated in Figures 7 and 8,

respectively. The procedure used to decompose the problem (Figure 6)

is a classic illustration of Benders' decomposition. The integer

variables and the correspondinE constraints (3.16),(3.17) and (3.21)

are retained in the master problem while the continuous variables and

the constraints (3.18),(3.19) and (3.20) make up the linear subproblem.

There is an interesting physical interpretation of the decomposition in

this case - the master problem orders the satellites, and given the

ordering, the subproblem assigns locations to positions while enforcing

required orbital separation between pairs of satellites.

The dual of the subproblem is shown in Figure 9. The dual

variables are used in comstructing the Benders' constraint for the

mester problem as indicated in equation (3.26). The _traint matrix

in the dual of the subproblem is unimodular. Even though the number of

variables in the dual can be large for actual problems, a majority of

them can be discarded because a large number of the corresponding

primal constraints are redundant, omce an ordering is fixed. The dual

of the subproblem, therefore, is easily solvable using standard linear

programming methods.
3O

MINIMIZE Z

subject to n n

_- _- q

Z > ___ =ZI aq X + c q-l,...s (3.22)

- i j ij £j

where

°

___X - 1 j-1,...n (3.23)

I

i ij

n

j=_ Xij = 1

X =Oorl

ij

i=l,...n (3.24)

i=l,...n;j=1,...n (3.25)

S = number of Benders' constraints generated so far

Z = "dummy" variable

X

ij

q

a

ij

q

C

is as defined in Figure 6

th

= coefficient of X in the q-- Benders' constraint obtained by

ij

collecting coefficient terms from the expended constraint 3.26

th

= collected constant terms for the q-- Benders' constraint

I

I

I

The Benders' constraint before collection of coefficients is :

n n n-1

_-- _-- ___ n_ nX- nXz>__ _ _dj ixij ÷j__ _&_:__," %-_-x "" h,j+k )_w_jkih

d and /kS are as defined in Figure 6

i ih

q f q w = v if X = I and X = I in the previous

jkih [ jk ij h, j+k

( assignment ; 0 else

q q th

u andv

j jk

(3.26)

(3.27)

are the dual variables from the q---

(See Figure 9)

subproblem

Figure 7. The Master Problem in Benders' Decomposition

th

(at the q"-- iteration)

I

I

I

I

I

I

I

I

I
I

I

31

I

m n

• Y÷

j---I j j

I subject to

y +y+_y- :

J J J I

I

I where

J

q

y - y _ Qj+k j jk

(3.28)

I

I

j=l,...n (3.29)

j:l,...n-1;k:l,...n-j (3.30)

Y , Y. , Y > 0 j=l,...n (3.31)

J o J -

Kq : Right hand side of (3.18) with X.. given by master problem

j zj

Qq : Right hand side of (3.19) with X given by master problem

jk ij

@

Y , Y. , Y are as defined in Figure 6

J J J

I

I

Figure 8. The 8ubproblem (Primal) in Benders' Decomposition

th

(at the q-- iteratiom)

I

I

I

I

I

I

I
I

I

32

n n-I n-"

j=i j j j=1 = jk jk

subject to

- =_ v < 0 (3.33) u I j ij -

j-1 n-" v

uj + k__Vk,j_k - k__ jk i 0 j:2,...n-I (3.34)

n-1

Un + k___v < 0 (3.35) i

k,n-k -

-1 _<u. ! 1 j=l,...n (3.36)

J

v > 0 j=l,...n-1; k=l,...n-j (3.37)

jkwhere th

u : the dual variable corresponding to the j-- constraint, in the

j set of constraints (3.29_ in the primal subproblem (Fzgure _)

th

: the dual variable corresponding to .the jk--constraint in _e I

Vjk set of constraints (3.30) in the prims/ subproblem (Fzgure )

Kq Qq _e as defined in Figure 8 I

j ' jk I

Figure 9. The Subproblem (Dual) in Benders' Decomposition

th

(at the q-- iteration)

I
I

I

I

I

I

I

I

I

I

I

l

I

I

I

I

I

I

I

3.2.1 On Solving the master problem

33

The master problem (Figure 7) is a pure integer program except for

the single continuous variable z. At each iteration one constraint of

type (3.22), a Benders' constraint, is s_ded to the master problem.

This constraint is generated from the dual variable values of the

solution to the subproblem at the previous iteration. In the absence

of these constraints, the master problem reduces to an assignment

problem, to which a solution can be found extremely efficiently.

Therefore, in order to take advantage of this fact, the Benders '

constraints are taken into the objective function using Lagrangean

relaxation as shown in Figure I0. Fisher [1981] and Shapiro [1979]

discuss the concept of Lsgrsngean relaxation and present thorough

expositions of the subject.

The relaxed master problem has an additional set of variablesthe Lagrsngean multipliers. The determination of these multipliers is

not easy; in Appendix A, a master problem for which optimal Lagrangean

multipliers do not exist is shown.

Since a Lagrangean relaxation of the master problem is being

considered, for any feasible set of Lagrangean multipliers, the

objective function in the relaxation is a lower bound on the optimal

solution to the master problem. Therefore, determining Lagrangesn

multipliers such that the Lagrangean objective function is maximised

ensures the tightest possible lower bound on the solution to the master

problem, and perhaps even the optimal solution. Since the optimal

solution to the master problem is not obtained in most cases, the lower

I
34

(3.38)

j=l,...n (3.39)

i=l,...n (3.40)

MINIMIZE

subject to

S n n

ij ij

q

-c )

n

£=_ Xij

n

j=_ xij

= 1

= 1

X :Oorl

£j

i=l,...n;j=l,...n (3.41)

where

S : nunber of Benders' constraints generated so far

q q

Z, a.., c , X are as defined in the master problem (Figure 7)

ij ij

Lq tJa : Lagrangeanmultiplier for the q---Benders' constraint

(The Lagrangeanmultipliers are non-negative and sum to unity)

Figure I0. The Lagrangean Relaxation Formulation of the Master Problem

th

(at the q-- iteration)

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

35

bound obtained is substituted in place of the master problem optimal

solution, as the lower bound on the optimum solution to the oriEinal

problem.

In the following sections, the different methods that are used in

trying to determine the Lagrangean multipliers are presented. All the

methods are heuristic methods in the sense that none of them can

guarantee findinE the multipliers that yield the optimum solution to

the master problem. In section 3.2.2, a method of computing upper and

lower bounds on the optimum solution to a master problem is introduced.

The upper bound corresponds to a feasible solution to the master

problem and can be used if the heuristics cannot find a better

solution.

3.2. I. I The fixed interval line seerch (FILS)

In this method, a line search is performed at fixed intervals over

the range [0,1] for the Lagrangean multiplier value correspondinE to

the latest Benders' constraint. All the previous Benders' constraints

are combined into a single constraint. In creating this combined

constraint, it is assmsed that the LagranEean multipliers of the

previous constraints remain in the same proportion to one another in

this Benders' iteration as they were at the end of the last Benders'

iteration. This assumption is made with the expectation that

relationships between LaErsnEean multipliers remain reasonably

constant, allowinE the search procedure to concentrate on the
36

determination of the value of the newest multiplier and to avoid a

search for all the multipliers at each iteration.

The fixed interval line search is performed as follows :

STEP I : Combine all the previous Benders' constraints into a sinEle

constraint. In combining these constraints the coefficients in a

constraint are weighted by the value of the LagranEean multiplier

corresponding to that constraint at the previous Benders' iteration,

i .e., the contribution of each previous constraint to the "combined

constraint" is proportional to its LagranEean multiplier value at the

previous iteration.

STEP 2 : Construct a Lagrangean relaxation of the master problem with

the new Benders' constraint and the combined constraint. All the

previous constraints are d/scarded in this relaxation except for their

contributions to the combined constraint. AssiEn a multiplier "L" to

the new constraint and a multiplier "I-L" to the combined constraint.

STEP 3 : Solve this Lagrangean relaxation of the master problem as an

assignment problem, for values of L going from 1.0 to 0.0 in equal

steps, to find that value of L which provides the tiEhtest lower bound

on the optimtm solution to the master problem.

STEP 4 : Determine the actual master problem objective function value

for each of the assiEnments generated in step 3.

STEP 5 : If any of the objective function values calculated in step 4

is between the bounds on the optima/ solution to the master problem ,

then return to the Benders' procedure with the solution to the

relaxation whose value in the master problem is closest to the lower

bound on the master problem. Update the lower bound on the original

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

37

problem with the largest Lagrangean objective function value found if

the lower bound is thereby improved. If no solution within the bouads

is found and the best assignment solution found has already been used

to generate a Benders' cut, terminate the Benders' procedure or use

another method to find a solution to the master problem.

3.2.1.2 The Golden Section Search Method

A golden section search

problems where the objective

of a unimodal fm_ction of one variable over a given range.

conditions are met, it is an optima/ search strateEy.

The procedure in this method is as follows :

STEP 1 : _uue as S'rEP 1 inFILS.

STEP 2 : Same as STEP 2 in FILS.

STEP 3 : Perform a Golden section search to determine that value of

"L" which maximizes the solution of the LaEranEean relaxation. Simmons

[1975] describes the implementation of the standard Golden section

search technique used here.

STEP 4 : Same as STEP 4 in FILS.

STEP 5 : Same as STEP 5 in FII_

is a sequential search strateEy for

is to determine the maximum (or minimum)

When these
38

3.2.1.3 The Rounded Linear Programmir_ Solution (RLPS)

This method does not use LaaTanEean multipliers - instead the

master problem is solved as a linear program, i.e,, with the

integrality constraints relaxed. The solution is rounded to give an

integer assignment which is taken as the solution to the master

problem.

STEP 1 : Set up the master problem with all the Benders' constraints

explicitly stated. Relax the inteErality constraints.

STEP 2 : Solve the linear proETam created in step I.

STEP 3 : Round the continuous solution obtained in step 2 to an integer

assignment as follows:

a. Determine the largest variable value and identify

the corresponding row and column.

b. Set the value of this variable to 1.

c. Set all other variables in this row and in this

columm to 0.

d. Remove this row and column from further consideration.

Repeat a, b, c, and d until an assignment is generated. If all nonzero values are zeroed out before an assignment is obtained, complete

the assignment based on the order of increasing desired locations.

STEP 4 : Return to the Benders' procedure with this assignment as the

solution to the master problem.

The solution to the linear proErsmminE relsxation of the master

problem is a lower bound on the optimum solution to the master problem,

I

I

I

I

I

I

i

I

I

I

!

i

i

m

I

I

!

I

I
I

I

I

l

I

I

I

I

I

I

I

I

I

I

I

I

I

I

39

and hence, it is also a lower bound on the optimum solution to the

original problem and is used as such.

3.2.1.4 The SubEradient Method (S(_D)

SubEradient optimization is frequently used as a method of solving

problems involving Lagz_mEean relaxation. Held et al. [1974] describe

the technique which had been discussed by Held and Karp [1971] in the

context of the tmvelinE salesman problem. Held et al. showed that

subEradient optimization is effective in approximatinE the maximum of

piecewise linear concave ftmctions. Poljak [1967] discusses the

theoretical aspects of the algorithm and presents results on the mates

of convergex_ce. Shapiro [1979] and Fisher [1981] provide exoellent

reviews of su]_Tadient optimization in the context of LagranEean

relaxatlon.

In this method all the LaErar_ean multipliers are considered

explicitly - no proportionality assumptions about the multipliem of

previous constraints are made.

Let Z be the optimal solution to the master problem (Figure 7 ),

and let ZD(L) be the optima/ solution of the _ean relaxation of

the master problem (Figure 10), where L is the vector of _ean

multipliers. As mentioned earlier, Z,(L) _< Z (Fisher [1981]) and

maximizing Zn(L) with an appropriate choice of L yields the tightest

lower bound on Z.

Let Z, = max Z,(L) (3.42)

L
The set of feasible solutions to the relaxation

{x t , The

large.

40

can be represented as

t:l,...T }. value of T is finite, but it can be extremely

Then

ZD : max w

subject to

\ q

w_< y-EL (

q_S

(3.43)

n n

\ \ q t q

Y - L /__a x - e ) t:l,...T

i:l j:l ij ij

(3.44)

\ q q

/__. L : 1 ; L >__0 q_S ;

q_s

(3.45)

The ftmctionZ.(L) is oontinuous and concave and is the lower envelope

of a finite family of linear functions. The function ZI(L) is nondifferentiable at any L' where the _ean problem

optima. A vector g is a subEradient of Z.(L) at L' if

Z.(L) ! Z.(L') + g(L - L') for ali L

The function Z.(L) is subdifferentiable everywhere.

components are indicated in (3.47) is a _ent

for which xt solves the La_TanEesn relaxation.

has multiple

(3.46)

The vector whose

of Z.(L) at any L

n n

\ \ q t q

-Y + L L a x + c q=l,...,:S: (3.47)

i=l j=1 ij ij

convex combinations of these subgrsdients are also subgradients. A

solution L* is optimal (i.e. it is the vector of Lagrangeanmultipliers

for the solution Z.) if and only if 0 is a subgrsdient of Z.(L) at L*.

The subgradient method can be stated as follows : Given an

I

l

I

I

I

i

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

I

I

I

I

l

I

I

I

I

I

I

I

initial set

with

where

of Lagrangean multipliers L0,

41

Eenerate a sequence { L_ }

Lk+, = Lk + tk (-Yk + A_k + R) (3.48)

Xk = the optimal solution to the iagrangean

relaxation with multipliers L_ ,

dk (Z' - ZD(Lk))

tk = scalar step size = , (3.49)

ll-Yk + ,__k + _cli '

dk = scalar such that 0 (_ dk _< 2 , do = 2 , and

Z* = upper boumd on Z,(L) generated using heuristics

In practice, dk is halved whenever Z,(L) fails to incTease in a

given number of iterations. Even though the algorithm theoretically

converges to the optimum value of L, practical limitations necessitate

termination on a prespecified iteration limit. The values for tk and dk

given above, and the use of san iteration limit, are sugEested by both

Fisher [1981] and Shapiro [1979].

3.2. I. 5 The Adjustment Method

In this section, a method of find/ng Lagrangesn multipliers based

on a weighted adjustment technique is introduced. The aim here is to

find a solution that lies within the bounds on the optimal solution

value to the master problem, and thereby, avoid premature termination

of the Benders' procedure.
42

STEP 1 : Set k = 0 and initialize the Lagrangean multipliers L ik for

all i_S where S is the set of indices for Benders'

constraints.

STEP 2 : Solve the LagranEean relaxatiom, an assiEnment problem, with

the multipliers L ik.

STEP 3 : Evaluate each Benders' caazstraint with the optimal assiEnment

as ZB|, i:l,...,:S:

STEP 4 : Compute the "mean constraint value" (ZM) and the "ranEe" (ZR)

as follows :

ZM : (ZB, + ZB= + ... + ZB,) / S (3.50)

ZR : max (ZBI) - sin (ZB,) . (3.51)

STEP 5 : Update La&Tar_ean multipliers as follows :

Li,k+, : Lik $ (1-WF) + ((ZBI - 224) / ZR) ¢ WF (3.52)

where WF = given weightinE factor. (WF = 0.1 in experiments).

STEP 6 : Normalize the multipliers Li ,k** so that the multipliers sum

tol.

STEP 7 : Set k = k + 1 . If k < maximum iterations Eo to step 2,

otherwise return to Benders' procedure with best solution

found. (There is no _rantee that this solution will lie

between the bounds on the optimal solution to the master

problem).

This method is designed principally for finding a solution to the

master problem that lies within the bounds on the optimal solution,

rather than for yielding an extremely tiEht lo_er bound. An attempt to

achieve this is made by weiEhting the LaEranEean multipliers in such a

manner that the contribution of each Benders' constraint wheB taken

I

I

I

I

I

I

I

I

i

I

I

I

I

I

I

I

l

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

l

I

I

I

43

into the Lagrangean objective function is approximately equal. There

is no guarantee that the method will find a solution to the master

problem which lies within the bounds ¢m the optimal solution.

3.2.2 Generation of bom_ds on the optimal solution to the master

problem

In this section, a method to determine upper and lower bounds on

the optimum solution to the master problem at any iteration in the

Benders' procedure is developed.

For the ease of exposition, consider the case where the master

problem (Figure 7 ) has two Benders' constraints. Suppose two

assignment problems are solved, the first with objective function alx

+ c t and the second with objective function a2x + c z (i.e. the right

hand sides of the first and second Benders' constraints respectively).

Let the optimal assignments to the two problems be x* and x2,

respectively. Let

A** = a*x _ + c _

AS* = a2x z + c 2

j A zl = alx z +c I

, and A 11 = aZx I + c z (3.53)

By optimality A** _ A** and A 22 _ A** . Without loss of generality

assume A** < A z2 • Then the three possible cases can be plotted on a

line diagram as follows :

Case 1 : A** _ ,,,

Case2 :

,: A**

A z2 _....... : A**

At* ¢, ,: A*2

A *_ * ....... : A**
Case 3 : A 'I _ ' : A 12

A 21 :---------Z A 12

increasing function va/ue -------->

44

These are the only three possible cases when A tl < A 22 . The lower

bound on the objective function value of the master problem in all

three cases is A z2 • If A I2 is not the lower bound then there exists

some assignment which yields an objective function value for the second

problem that is less than A 22. But this violates the fact that A 21 is

the optimal solution value to the assignment problem with the second

objective function.

The upper bound is given by the minimum of the two right endpoints

in each case, i.e., A 12 in case I, A zl in case 2, and A 22 in case 3.

These are obviously upper bounds because in each case there is an

assignment that satisfies all the Benders' constraints. If the upper

and lower bounds are equal, as in case 3, then we have the optlmui

solution to the master problem.

This result can be extended to the general situation with ',S:

Benders' constraints.

n n

kq \ \ q k q

Define A : L_ L_ a x + c q,k_S (3.54)

i=I j=l ij ij

k

where x is the optimal solution to the assignment problem with

ij

objective function given by

n__ n_

\ \ k k

L_ L a x +c

i:l j:l ij ij

I

I

I

I

I

I

i

I

I

I

I

I

l

I

I

I

I

I
I

I

I

I

I

I

I

I

l

I

I

I

I

I

I

I

l

I

I

45

A lower bound on the master problem is given by

qq

LB = max { A } (3.55)

z q_S

An upper bound on the optimal solution to the master problem is

given by

UB =rain {A

z {

m,n{_S {

mq mn }

A < A for all q_S , q_n }

rq mn }

A >_ A for some q_S and for all r_S}

(3,56)

Proof : Let the lower bound as defined by equation 3.55 be APP. If

APP is not a lower bound on the optimal solution to the master problem,

then there is some optimal solution to the master problem, say, xk such

that the right hand side of constraint p evaluated with this vector is

A kp, and A kp < APP. But, by definition, APP is the optim_n solution to

the assignment problem with the right .hand side of constraint p as its

objective function. Therefore, no solution xk such that AkP < App

exists, and App is a valid lower bound on the optimal solution to the

master problem.

Evaluated at xt, the right hand side of every Benders' constraint

has a value less than or equal to UBz as defined in equation 3.56. By

definition, xB is an assignment. Therefore, a feasible solution vector

(xu) which yields a master problem objective function value equal to

UBz exists. Hence, UBz is an upper bound on

the master problem.

Calculation of these bounds involves

the optimal solution to

solving one assignment

problem at each iteration q (assuming one Benders' constraint added per

iteration) and making 2(q-1) functional evaluations. It also involves
46

storing the indices of the variables in the assignment at each

iteration.

3.3 Linear Programming with Restricted Basis Entry

In this section, the initial non-linear mathematical prograa_ing

model (Figure 2) is reformulated as an "almost" linear program with a

set of complementarity constraints. These constraints are non-linear,

but through some modifications in the simplex method for linear

programming they can be enforced. However, there is now no guarantee

of optimality, or even of feasibility, upon termination of the

algorithm. Ignizio [1984] has used complementarity constraints in goal

programming approaches to minimal interference scheduling problems. He

claims that the method is an extremely efficient heuristic. He does

not indicate how the method was implemented, other than saying that a

restricted basis entry rule was used.

In Figure iI, a formulation of the satellite location problem as

an "almost" linear program with complementarity constraints is shown.

The objective function (3.57) is the same as that in Figure 2, i.e.,

minimization of the total deviation. Constraints (3.58) evaluate the

deviation of assigned locations from desired locations. Constraints

(3.59), (3.60), (3.63 ), and (3.64 ) together enforce the minimum required

separation between pairs of satellites, constraints (3.64 ) being the

complementarity constraints. Constraints (3.61) establish the

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
!

I

I n

MINIMIZE ._-

subject to

(x +x )

J J

I X +X + -X - =d

J J J J

I X -X -P +N i j ij ij

= 0

47

(3.57)

j=l,...n (3.58)

i=l,...n-I (3.59)

j=i+l,...n

I Pij + N..xj >_ /kS..xj

i=l,...n-I (3.60)

j=i+l,...n

E <X <W

I j_ j_ j

+

I X J ,X J ,X- J ->0

j:l,...n (3.61)

j:l,...n (3.62)

I

I

I

I

I

P.., N.. ! 0 i:l,...n-I (3.63)

xO IJ j:i+l,...n

P • N = 0 i:l,...n-I _o'".64)

ij ij j:i+l,...n

where

X., X., X., E., W., d., L_.., n

j j j j j j xj

are asdefined in Figure 2.

P.. (N..) = degrees west (east) of satellite j that

xj xj

satellite i is located.

Figure II. "Almost" L_ne_Progr_ Formulation of the Satellite

Location Froplemwxth Complementarity Constraints
boundaries on the feasible arc for each satellite.

are the non-negativity constraints.

48

Constraints (3.62)

The satellite location problems that are formulated in Figures 2,

4, and II are equivalent - the differences lie in the mathematical

programming formulations. The absolute value constraints (2.3) in

Figure 2 are expressed as a combination of integer variables and linear

constraints in Figure 4, and are now expressed as a combination of

continuous variables and linear and complementarity constraints in

Figure II.

In the implementation of the formulation in Figure II, constraints

(3.64) are not explicitly specified. P_ther they are enforced through

a restrieted hasis entry procedure within the simplex method. At each

iteration, only those variables whose complements would be nonbasic

after a change of basis are considered for entry into the set of basic

variables. Pivots in which the entering non-basic variable is the

complement ofthe leaving basic variable are permitted. Through the

application of these rules, the complementarity constraints are

implicitly enforced. Non-basic variables always have value zero, and

one variable of a complementarypair is always forced tobe non-basic.

3.4 The Switching Method

In this section, a heuristic switching method for the solution of

the satellite location problem is introduced. This technique has been

developed because it is likely that in most optimal solutions to

I

I

i

!

I

!

!

i

I

I

I

I

I

!

I

!

!

I
I

II

I

II

I

I

I

II

I

II

II

II

I

l

i

II

II

I

I!

49

problems of this type, the prescribed location of a satellite will not

be far from its desired location. Therefore, if one starts with the

satellites ordered by their desired locations and consider

perturbations in this order, there is a reasonably good chance of

finding the ordering that yields the optimum solution or at least an

ordering that yields a very good solution.

To apply this method, a systematic determination of orderings to

be considered is required. In the interests of efficiency, the

examination of previously considered orderings should be avoided. A

further requirement is a procedure for efficiently determining the

solution to the satellite location problem for a given ordering. A

switching technique which permutes small subsets of adjacent

satellites, combined with a linear programming procedure which solves

the satellite location problem for any given permutation of the

satellites, fits these requirements.

A basic outline of the method is as follows :

I. Determine an ordering of the satellites.

2. Solve a linear program with the ordering from step I to obtain

a solution to the satellite location problem. (The LP minimizes

total deviation while ensuring that minim%_ separation

requirements are met. )

3. Repeat steps 1 & 2 for a different ordering.

If there are n satellites there are n! possible orderings and it

is obvious that all possible orderings cannot be evaluated for large

values of n, for example, n > I0, in reasonable amounts of computer

time. This method considers orderings in which the satellites are
50

likely to remain in the vicinity of their desired locations. The total

number of orderings considered is but a tiny fraction of all possible

orderings.

A linear progrsmming formulation for the satellite location

problem with a specified ordering of the satellites is shown in Figure

12. The objective function is the minimization of total deviation.

Constraints (3.66) measure the deviation of each assigned location from

the corresponding desired location. Constraints (3.67) ensure that the

minimt_ required orbital separation between all pairs of satellites is

met. Since index k is always greater than index j, position k and the

corresponding satellite S(k) is to the west of position j and the

satellite in position j, S(j). Since an ordering is specified,

absolute values, nonlinear constraints, or integer variables are not

needed to enforce the minimtn required separation.

In Figure 13, the dual of the linear program presented in Figure

12 is shown. The constraints in the dual formulation refer only to

orbit positions. All references to satellites occupying specific

positions occur only in the objective function. Therefore, a feasible

solution to the dual problem is feasible irrespective of the satellite

ordering; it may not be optimal, but it will be feasible. It is this

property that is exploited to efficiently examine orderings.

From duality theory in linear programming, it is known that at

optimality the primal and dual objective function values are identical,

and that if the primal is solved, the dual solution can also be

obtained and vice-versa (Bazaraa and Jarvis [1977]). Therefore, no

information is lost by solving the dual problem. Instead, a great deal

I

I

I

II

II

I

i

II

I

i

!1

I

II

I

I

I!

I

II
n

| /

subject to

I y+ Y + -Y- = d

j j j i

m y -Y >

k j - Asih

Y , Y+ , Y- > o

J J J -

where

i:S(j); j=l,...n

51

(3.65)

(3.66)

_-SI_I; ; j:l,...n-I K:j+l,...n (3'.67)

j:l,...n (3.68)

II

I

I

I

a

n = number of satellites and orbit positions

Y : the actual location of orbit positicm j

J

+

Y , Y : the deviation to the east and west resuectively, of

J J the _rescribed location of position j _romthe aesired

location of the satellite in position j

S(j) : the satellite currently occupying position j

d = desired location of satellite i

i

/_Sih : required orbital separation between satellites i and h

Figure 12. Primal Linear Programming Formulation for the Satellite

Location Problemwith Satellites in a Given Ordering

(Used in the Switching Heuristic)
52

n n-I n

j i j j k=j+l ih jk

subject to

j-I n I

u+ vj k: 1 Vjk_< 0 j=l, ..n (3.70) I--

-I __<u _< 1 j=l,...n (3.71)

J

v > 0 j=l,...n-l;k=j+l,...n (3.72)

jk -

where

th

u = dual variable corresponding to j-- constraint in set (3.66)

J

in the primal formulation (Figure 12)

v

jk

th

= dual variable corresponding to jk---_nstraint in set (3.67)

in the primal formulation (Figure 12)

n, di, ZlSih are as defined in the primal formulation (Figure 12)

Figure 13. Dual Linear Programming Formulation for the Satellite

Location Problem with Satellites in a Given Ordering.

(Used in the Switching Heuristic)
I

II

li

I

I

I

I

II

I!

i

I

i

I

II

I

!

II

53

is gained in this case. In the dual, there are only n explicit

constraints as opposed to the primal where there could be as many as

0.5n 2 + n constraints. On the other hand, in the dual, there are many

more variables than in the primal, but in general, many variables are

easier to handle than many constraints in linear programming.

The switching heuristic can be summarized as follows :

STEP 1 : Create an initial ordering O, by ordering satellites in

increasing order of desired locations.

STEP 2 : Solve the dual linear program to optimality with this ordering

01.

STEP 3 : Specify a starting subEroup size, say k, and a maximum

subgroup size, say k a.

STEP 4 : If k > k" ,stop. Otherwise evaluate all k! permutations of

the satellites in positions I to k, with the satellites in

positions k+1 to n not changing position. The locations of

all satellites may be changed. Each evaluation involves

reoptimizinE the dual after making the necessary changes in

the objective function. Update the ordering to the best one

found so far - the one which minimizes the objective function

value.

: Repeat step 4 with subgroups 2 to k+l, 3 to k+2, .... , and nk+l to n, updating the ordering at the end of the examination

of each subEroup.

: If no improved solution is found, increase k by I and go to

step 4. If an improved solution is found, go to step 4 with k

unchanEed.

STEP5

STEP6
54

The performance of this procedure can be considerably improved by

introducing a type of fathoming procedure in the reoptimization of the

dual. Initially, the dual is optimized with the ordering by desired

location. The optimal solution is the initial incumbent solution.

Once a switch is made, since the basis for the dual is still feasible,

the new objective function value for this feasible solution can be

determined. (The objective function coefficients are the only

,parameters changed in making a switch). If the value of the new

objective function is greater than the current incumbent solution

value, the switch is discarded since it cannot yield a better solution

on reoptimization. If the new objective function value is less than

the current incumbent solution value, reoptimization is required to

determine whether a better solution can be reached. After each primal

iteration in the reoptimization of the dual problem, an updated

objective function value is obtained since the dual solution is primal

feasible. If, after any iteration, this updated objective function

value exceeds that of the current incumbent solution value, the

reoptimization is terminated and the switch discarded from

consideration. If the reoptimization is completed, a new incumbent

solution has been found.

By using the fathoming procedure described above, the dual (or

primal) does not have to be solved from scratch for each permutation.

At most, a few primal pivots with the dual problem have to be performed

for the majority of switches, since a large portion of the solution

vector is unchanged when the switches made are on satellites in the

vicinity of one another.

I

I

I

I

I

I

I

l

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

55

The implementation issues are discussed in the following chapter.

Extensions of this method to include feasible arcs are presented in

Chapter 5. Feasible arcs oan introduce unboundedness in the dual, and

correspondingly, infeasibility in the primal for some or all orderings.

In the absence of feasible arcs, the primal and the dual are always

feasible and bounded.

Switching or interchange techniques have been widely used in the

past as heuristics for a large variety of problems. A seminal paper in

the area is the one by Reiter and Sherman [1965]. They propose the use

of an intelligent search based on the nature of the problem combined

with a random search to improve the probability of escaping from being

trapped at local optima. Lin and Kernighan [1973] use an interchange

heuristic in an effective procedure for generating near optimum

so!utiomq to traveling salesman problems. _..eir work is an extension

of an earlier paper by Lin [1965]. Eilon et al. [1971], Cassidy and

Bennett [1972], and Wren and Holliday [1972] all use variations of

interchange heuristics in their work on vehicle routing problems.

Federgruen and Zipkin [1984 ] use an interchange heuristic as one

approach to solving combined vehicle routing and inventory allocation

problems.
CHAFFER IV

_MPIRICAL SITDY OF THE FOUR SOLUTION TECHNIQUES

In the last chapter, four solution techniques for the satellite

location problem were presented. In this chapter, the computer

,implementation of these methods is discussed. The methods are tested

on a set of problems generated from real data and the performance of

each method is evaluated in terms of final solution value and the CPU

time required to reach that solution. Some of the difficulties

involved in the implementation of these methods am_ the steps taken to

overcome them are also mentioned.

4.1 Implementation of the Mixed Integer Programming Method.

General purpose mixed integer progrsmming packages are available

commercially. The mixed integer programs formulated in Figures 4 and 5

can be solved by any such cede. Since no commercial code was

available, a package developed by Martin and Gonsalvez [1981] is used

in the implementation of this method. The package solves mixed integer

programs using the branch and bound technique of implicit enumeration.

Branching directions are chosen through the evaluation of pseudo-costs,

which estimate the improvement or degradation in the objective function

value involved in following a particular path. The concept of pseudo56

I

I

I

I

I

I

I

l

I

I

I

I

I

I

l

I

I

I

I
I

I

I

I

I

i

I

I

I

I

I

I

I

I

I

I

i

I

I

57

costs was introduced by Benichou et al. [1971]. Gonsalvez [1983]

provides a brief description of the code and some of its features.

In trying to solve the satellite location problem as formulated in

Figure 4 with this computer code, there were several instances of

premature termination due to accuracy check problems. The accuracy

check problems appear to be caused by the large disparity between the

values of the constraint matrix coefficients (the differences ranging

to four orders of magnitude). These accuracy problems provided the

motivation for the reformulation of the model in Figure 4 which appears

in Figure 5.

4.2 Implementation of the Benders' Decomposition Method

A flow chart of the Benders j decomposition procedure, as applied

to the satellite location problem, is shown in Figure 14. The diagram

highlights the major modules of the computer program and the

relationships between them.

The initialization portion of the code consists of the input of

the problem data : the service areas, the minimum required separation

matrix, and the desired locations for the satellites. An initial

assignment, in which the satellites are ordered by increasing desired

location, is generated.

Once an assignment (i.e., an ordering) is specified there are a

large n_nber of redundant separation constraints in the subproblem

(i. e., constraints of type (3.30) in Figure 8). These redundant

constraints are identified by the procedure described in Appendix B.
58

......................................... !

START I

!

T

!

INPUT DESIRED I

LOCATIONS i

, J

J I

! INPUT & SETUP !

] /kS MATRIX i

i. i J

I....... d i

'I CREATE INITIAL l

i ASSIGNMENT i

i-- .i

I

I

!

, I

ELIMINATE REDUN- ! l

DANT VARIABLES IN _............ '

SUB-PROBLEM DUAL l

J

I

i i

COMPUTE OBJECTIVEt

FUNCTION I

COEFFICIENTS l

I

[

i

SET UP & SOLVE

SUB-PROBLEM DUAL

USING L.P. CODE

i

L

i COMPUTE NEW I!

[ BENDERS' CUT p ........ _._ .......

IFROM SOLUTION TO I

ISUB-PROBLEM DUAL. I

i............................................................. !

I SETUP NEW t

D ASSIGNMENT i

L r ......................................... i

i

!NO

r...................................... J............................................. i YES

! TERMINATE ? i............................

......................... T............................................ _ '_

* I STOP i

IYES

l--- " _

NO I ACCEPT AS SOLN. I

!.............. q TO MASTER PROB. i

I SET UP & SOLVE i

I I ASSIGNMENT i

I I PROBLEM !

i !" J.................................................

l I RESET

i LAGRANGEAN

I MULTIPLIERS

t

!.................................................................................

Figure 14. Flow Chart for Benders' Decomposition as

Applied to the Satellite Location Problem.

I

I

I

!

I

i

I

l

I

I

I

I

!

I

I

!

I

I
59

Redundant constraints in the primal formulation of the subproblem

appear as variables in the subproblem's dual and these variables can be

discarded without affecting the optimum solution.

After identifying and discarding the variables corresponding to

redundant primal constraints, the subproblem's dual is set up in a form

acceptable to the linear programming code used by means of a matrix

generator. The subproblem dual is then solved. The linear pl_gramminE

code used is PROFOR developed by Martin [1979].

The Benders' constraint is constructed from the dual variables in

the optimmn solution to the subproblem as indicated in equation (3.26).

A general description of the generation of Benders' cuts is presented

in Lasdon [1970].

The constraints are stored using a ;_riation of sparse storage

techniques. The assignment from which the current subproblem was

generated is stored (this requires n storage elements where n is the

ntm_er of satellites in the problem under consideration). The solution

vector for the "u" variables in the dual formulatiun (Figure 9) is

stored (n storage elements). The ujdl portion of the coefficient for

X ij in the Benders' constraint (3.26) can be easily obtained from the

above two sets of stored values - d{ being the desired location of the

satellite in position j (given by the assignment) and us being directly

obtained from the solution vector. Finally, only those Xi j that were

equal to 1 in the previous assignment have /kSia Wjkia coefficients

(see equation 3.27) in the current master problem. These are computed

and stored (n storage elements). The coefficients of the variables in

each Benders' constraint are thus compactly stored using 3n storage
6O

elements, even though there are n 2 variables in each constraint and

most of these variables have non-zero coefficients. Without such a

storage technique for the Benders ' constraints, the storage

requirements for large problems would be so great as to necessitate

storing the majority of constraints in external memory.

The new Benders' constraint is added to the master problem. Upper

and lower bom_is on the optimum solution to the master problem are

generated using the procedure described in section 3.2.2. An

assignment which yields an objective function value within these bounds

is termed an "acceptable" solution to the master problem.

The master problem is now solved using one of the five heuristic

methods described in sections 3.2. I. 1 to 3.2. I. 5. In the experiments

presented in this chapter, the particular method used at each iteration

is selected at random. If the selected method fails to find an

acceptable solution to the master problem, then the next method in the

sequence {FILS, GSLS, RI/_, SGRD, ADJI} is used. If all five methods

fail to find a solution within the bounds on the optimum solution to

the current master problem, the procedure terminates. The procedure

also terminates if the lower bound (lower bound on the current master

problem) and the upper bound (best subproblem solution obtained so far)

on the original problem are equal, in which case the solution obtained

is the optimal solution. If an acceptable solution to the master

problem is found, the subproblem corresponding to this assignment is

generated and a new iteration started.

Four of the heuristics for solving the master problem are based on

LaEranEean relaxation. They repeatedly solve assignment problems in

I

I

I

I

I

I

I

I

I

l

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

I

I

I

I

l

I

!

I

I

I

I

I

61

the process of findinE a solution to the master problem. The code used

to solve these assiEnment problems is an adaptation of a code developed

by Burkhard and Derigs [1980], and is based on the shortest auEmentinE

path method.

The rounded linear program solution heuristic does not perform

well, in terms of computation time, on larger problems and hence was

not used in the set of experiments described in this chapter. The

constraint matrix for the master problem is extremely dense (i .e. few

coefficients are zero) and hence even solvinE it as a linear program,

with the integrality constraints relaxed, can be extremely time

consuminE. As the number of Benders' constraints increases with

successive iterations, the situation becomes worse. For example, in a

problem with 12 satellites, 76 iterations were performed in I minute of

_irw T _ru time with the ut/,=- - _-_ four heuristics 4.._ uu_ un-_A _.. I_ iteratior.a _uu_u_ be

performed in I minute when RLPS was included.

It was intended to first solve the master problem as a linear

proErsm, relaxinE the inteErality constraints, and then use the shadow

prices on the Benders' constraints as startinE values for the

LaErsnEean multipliers in the subErsdient method and in the adjustment

method. Since solvinE the linear proEram has proved impractical in

terms of computation time, these multipliers are initialized to the

values they had at the termination of the previous iteration. These

values are then multiplied by a factor of 0.9 and the multiplier of the

added constraint is arbitrarily set to 0.I in order to obtain a

feasible set of initial multiplier values for the current iteration.
62

4.3 Implementation of the Restricted Basis Entry Method

Enforcing restricted basis entry in a simple form requires only

minor modifications to any standard linear programming code. In the

implementation described in this section, a linear programming package

(PROFOR) developed by Y_rtin [1979] is used. The following

modifications are made to the linear programming package. At each

iteration, after the selection of the non-basic variable to enter the

basis, a check is made to ensure that the complement of the selected

variable will not be in the basis at the completion of the pivot. This

check is performed only if the entering non-basic variable posesses a

complement (i.e., the check is performed only for the Pi j and Ni j

variables as defined in Figure II). If a pivot will result in both

complements being in the basis simultaneously, thus allowing a

complementarity constraint to be violated, then a new entering variable

is selected from the list of candidate non-basic variables. If none of

the non-basic variables in the set of candidates can enter the basis,

then the procedure terminates.

The above procedure may terminate at infeasible or non-optimal

solutions. No attempt is made to influence the choice of pivot

elements, other than the step described above which prevents

complements from being in the basis at the same time. Standard

selection procedures for the entering non-basic variable and the

leaving basic variable are used. For a discussion of pivot procedures

and selection of the row and column for a pivot in the simplex method

l

I

I

I

I

l

I

I

I

I

I

I

I

I

I

I

I

I
63

for linear programming, the reader is referred to Bazaraa and Jarvis

[1977].

4.4 Implementation of the Switching Technique

The steps involved in generating an efficient Computer program for

the switching heuristic sine described in this section. The heuristic

is described in section 3.4. There are two distinct parts of the

program : generation of an ordering and the solution of the linear

progrsm that provides the optimal locations for satellites given an

ordering. A flow chert of the modules in the program and their interrelationships is given in Figure 15.

The line_" prog_am car, be -u_--7---;v_ b_ an)- =v=_a_= linear prom_-_-amming

code. It is preferable to use one that stores the inverse of the basis

in a product form, since this allows an efficient generation of

feasible starting ]mlses for the linear programs, as is described later

in this section. The linear programming code used is PRO_OR which was

developed by Martin [1979]. This program is based on the revised

simplex method and uses the product form of the inverse for basis

storage. Both the revised simplex method and the product form of the

inverse are discussed in Bazaraa and Jarvis [1977].

Even though the individual linear programs generated by the

switching heuristic are easily solved, solving each linear program from

the basis corresponding to the origin to the optimal solution is not

computationally practical, when the nt_aber of orderings to be
64

iSTART i

+

IINPUr DESIRED LOCS. I

FEASIBLE ARCS AND

/kS MATRIX

,f

IINImJr/SETUP ASSIGNMENT INITIAL Az

f

lsm_p • SOLVE L.P.

,[DUAL TO GET OBJ.FN.

I Z* AND BASIS B*

+

SETUP SWITCH.CHANGE i,

DUAL OBJ FN COEFFS. I

,

(X)MFZrI_ NEW 0BJ.FN. ZN _ BASIS B*

I •

YES ,MORE CONSIDERED SWITCHES BE] NO

f

DELETE REDL_qD_NT

COLUMNS I

÷

IS ZN > Z*

• IYES_

t

COLUMNS TO DUAL]

PROPOSED SWITCH

WILL NOT YIELD

IMPIiOVED SOLUTION"

DISCARD IT.

I REOPTIMIZE

STAIVFWITH BASIS B* I

+

ATION : OBJ FN

+

l RESET BASIS TO B* ]

BY DI%OPPING ADDED

ETA VECTORS

VES

IS ZP > Z* ? ]

¢_o _. IS ZP OPTIML,_I ?

NO

I REIN"_T]_T REQUIRED IF

+

IMPRO\]KD SOLUTION"

FOUND. SET Z*:ZP

' L_DATE %* & B* I

I

l

I

I

I

I

I

I

I

I

I

I

I

I

Figure 15. Flow Chart for the Switching Heuristic
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

65

considered through the switching method is taken into account. Each

linear program is not solved starting from the origin, rather the

optimal basis for the linear program corresponding to the ordering

before the switch is used as a starting basis. This basis is still

feasible after the switch since only the objective function

coefficients are changed in the dual formulation (Figure 13). It is

unlikely that a major portion of the solution changes after a switch

since only the satellites in the current subgroup change positions in

the ordering. Hence, this choice of a starting basis is likely to be

very close to an optimal basis for the linear program corresponding to

the new ordering.

Suppose the initial ordering is R. The linear program for the

dual formulation (Figure 13) is generated for this ordering and it is

solved tv^ ^_+_-"_'_- vw ........ j. Let S be the _+" vW _mE&_ I solution - _" ..M+__ ...... , Z* the

optimal objective function value, and B* the optimal basis. Since Z*

is the optimal dual objective function value, by the theory of duality

the optimal objective function value for the primal problem with

satellite ordering R is identical. Though the dual linear proErsm is

examined and solved, it is the primal objective function of minimizing

total deviation that is the actual goal and this corresponds to driving

Z* as low as possible.

A switch is made in the ordering R, resulting in a new ordering

RI. The basis B* is unlikely to be optimal for the dual linear program

corresponding to the new ordering RI, but it is still feasible.

Therefore, the solution vector S is also feasible and is used to

evaluate the new objective function (say Z"). If Z a is greater than
66

or equal to Z*, then ordering R1 cannot yield a better solution than

ordering R, since Zn can only increase when the linear program

corresponding to R1 is optimized. Reoptimization is not required and

ordering R1 can be discarded.

On the other hand, if Zn is less than Z*, then there is a

possibility that R1 might he a better ordering than R with respect to

the objective function. The linear program corresponding to R1 is

reoptimized using the basis B* as the initial basis. At each iteration

in the solution of the linear program, the current objective function

value (ZP) is computed. Since the dual formulation is a maximization

problem, Zp has to increase at each iteration. If Zp becomes greater

than or equal to Z* at any iteration, then the linear program can be

terminated and the ordering R1 discarded. The linear programming code

uses the product form of the inverse in which the inverse is stored as

a set of vectors called "eta vectors"; one eta vector for each pivot.

The inverse of the basis B x is regenerated by dropping the eta vectors

that were added to the inverse in the optimization of the linear

program corresponding to R1.

The final possibility is that the reoptimization with ordering R1

is completed, and ZP at this point is less than Z x . Therefore, the new

ordering R1 is an improvement on the old ordering R. The ordering R1

is now called R, the current basis is called B', Z z is set equal to ZP,

and the new solution vector takes the place of S. A new switch is

selected and the procedure is repeated.

During the reoptimization, all reinversions of the basis are

suppressed. This is done to allow an easy regeneration of the basis B x

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

I

|,

!

I

I

I

I

I

I

I

I

I

67

by dropping eta vectors when a switch does not improve on the current

best solution.

Once an ordering is specified there are a large number of

constraints of type (3.67) in the primal linear program which are

implicitly satisfied through other separation constraints. These

constraints in the primal formulation are termed "redundant"

constraints, and the corresponding variables in the dual formulation

are called "redundant" variables. In the context of the dual problem,

a basis, in which all redundant variables are nonbasic, exists for any

feasible solution and in particular for the optimal solution.

Therefore dropping redundant variables from the linear program dual

does not effect the solution obtained. The number of variables in each

of the linear programs generated by the switching heuristic is thus

reduced substantially; often this reduction is on the order of 90 %.

The procedure used for identifying the redundant variables is described

in Appendix B. For the solution of the dual linear program

corresponding to the initial ordering, all redundant variables among

the "v" variables are identified and removed. The "u" variables are

never redundant.

After a switch is made, a dual variable that was redundant before

the switch may no longer be redtmdant. A mi_ required separation,

which was previously implicitly satisfied through the other enforced

separations, now has to be explicitly enforced after the switch. A new

variable has to be added to the linear program dual, and this is done

by adding a column to the constraint matrix. Since this variable was

previously redundant, it is nonbasic with respect to the existing
68

basis. The existing basis still provides a feasible starting basis for

the linear program dual after the switch.

It is also possible that a nonredundant variable becomes redundant

after a switch, and can be removed from the problem. However, removing

a variable is not as straightforward as adding a variable. If the

variable to be removed is currently nonbasic, it can be deleted through

a rearrangement of column indices and corresponding changes in the

basis pointers. If the variable is in the basis, then a pivot has to

be performed to make it nonbasic before it can be dropped. Neither

situation lends itself to an efficient implementation. In this

implementation, these redundant variables are left in the problem until

their number exceeds a given limit, at which point they are all

removed.

The switching heuristic as stated in section 3.4 specifies that

all permutations of satellites within a subgroup are explicitly

examined. This leads to repeated examination of some orderings as

successive subgroups are considered. By considering only permutations

of a subgroup in which the last satellite in the subgroup does not

occupy the last position, repeated examinations of the same ordering

are avoided. All orderings that would have been considered previously

are still exsmined. A proof of these statements is given in Appendix

C.
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

4.5 Generation of the test problems

69

A set of seven test problems was created in order to compare the

performances of the four techniques. These scenarios were selected to

represent actual satellite location problems. For each scenario,

nations which are in geographical proximity to one another constitute

the service areas. Most of the satellites in a scenario are unable to

occupy the same geostationary orbit location without causing

unacceptable interference to the neighbouring service areas.

Therefore, the nations included in each scenario have to arrive at some

mutually satisfactory satellite location plan. The seven scenarios are

described in Appendix D, the names of the nations in a scenario, the

desired orbital location for the satellites, and the worst case minimum

required se_-ation matrices _,,_tI_,,.,,.,.,."--_'-_"'_o_.,.,.,,.._, being given.

Each service area in a scenario is specified by a set of test

points. These test points, denoted by geographical longitude and

latitude, are usually at the boundaries of the nation. The polygon

formed by joining these test points should envelope the country,

thereby ensuring that, if interference levels at the test points are

acceptable, then interference levels are acceptable throughout the

service area. The test points for each country in the scenarios were

determined using an atlas, with the criterion that the polygon formed

by the test points covered the entire country.

In these experiments, elliptical satellite signal beams are

assL_ed throughout, while Earth station beams are circular in crosssection. It is, therefore, necessary to compute the ellipse that will
7O

cover the polygon representing a service area most efficiently. This

ellipse is termed the m/nimtsn ellipse and is computed using the minimum

ellipse program developed by Akima [1983]. The minimt_n ellipse is

specified by the length of its major and minor axes, the beam center in

longitude and latitude coordinates, and an orientation angle. These

ellipse parameters and the corresponding minimum ellipse itself change

as the satellite location is shifted. Therefore, minimt_ ellipses are

computed at 2• intervals over the entire feasible arc for each service

area.

Once the test points have been specified and the minimt_ ellipses

determined, the minimum required orbital separation between each pair

of satellites is calculated. This required separation (/_#), which is

required in order to satisfy the specified threshold C/I ratio, varies

as the satellite locations change. The separation is computed at 4"

intervals over the entire common feasible arc for each pair of

satellites. The largest value among these separations is denoted as

the /"kS value (worst case minimtmm required separation) for that pair of

satellites. A complete /kS matrix which contains /_S values for all

pairs of satellites is computed for each scenario.

All the input that is required to define a scenario for any of the

four solution techniques is now available :

I. the service area names

2. the number of satellites for each service area

3. the desired location for each satellite

4. the /kS matrix

I

!

I

I

I

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

4.6 Discussion of experimental results

71

The four solution techniques, mixed integer programmin_ (MIP),

Benders' decomposition, the restricted basis entry method (RBE), and

the switching heuristic were applied to each of the seven test

problems. In every case, the objective was to minimize the total

deviation. Feasible arc restrictions were not imposed for amy of the

runs. The final solution obtained and the total CPJ time taken for

each of the twenty-eiEht rtumare presented in Table I.

Some restrictions on the lengths of individual rt_s were imposed.

Maximum time limits of 300 seconds and 60 seconds were set for the

Benders' procedure and the RBE method, respectively. The Benders'

procedure also hadamaximumiteration limit of 150 iterations.

vv_,_, ............ performs the other three

techniques both in terms of final solution value and in terms of total

time taken. The switchinE heuristic finds the best solution for six

out of seven scenarios and in the seventh case arrives at a solution

that is within I0_ of the best solution. With regard to solution time,

the switching heuristic is aEain the best alternative in six out of

seven scenarios.

The MIPmethod is Euaranteed to find an optimal solution if one

exists. However, with the satellite location problem, the method runs

into considerable difficulties with accuracy checks, often resulting in

premature termination. This may be due to the sensitivity of the code

used, or due to the structure of HIP model of the satellite location

problem. For only two of the seven scenarios does the method find the

I
72

TABLE I. £XIMPARISON OF THE P_ OF THE FOUR SOI//rION METHODS

Objective Function : Minimize total deviation

( without feasible arc limitations )

SCENARIO

(# Sat.)

S.AMERICA

(13)

SOLN.

TIME

E. EUt_PE SOLN.

(12) :TIME

W.EUROPE :SOLN.

(12) :TIME

S.E.ASIA :SOLN.

(I0) :TIME

I .....

N.AFRICA ISOLN.

(10) :TIME

EUROPE :SOLN.

(26 ) :TIME

il--wo_w

NCS AMERICA :SOLN.

( 26 ) :TIME

METHODS

M.I .P

0

21.92

83

BENDERS'

C

44.39

109

a c

53.46 51.63

13 95

O

31.40

161

a

24.25

20

a

38.72

110

a

212.56

301

a

125

C

47.13

95

C

29.84

68

C

24.49

66

b

230.18

300

b

106.30

300

RES. BASIS

52.84

8

110.01

9

81.25

8

80.85

3

6O

60

6O

SWITCHING

21.92

9

41.48

5

34.21

4

23.29

2

24.49

2

150.69

71

40.56

87

All times measured in Clm3 seconds on an IBM 3081-D

o - optimum solution

a _ termination due to accuracy checks

b - termination due to time limit

c - termination due to iteration limit

Zz$ - no feasible solution found at termdnation
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

73

optimum solution. In the remaining five scenarios, the program is

terminated by excessive accuracy checks with nonoptimal solutions.

The Benders' procedure did not perform as well as the switching

heuristic or the MIP method. Only in one case does it provide the best

solution, and in this case the switching heuristic reached the same

solution in 2.4 seconds compared to the 66 seconds taken by the

Benders' procedure. It was hoped that the Benders' procedure would

converge to near optimal solutions quickly. The procedure converges,

but only slowly when compared to the switching heuristic. The solution

times for Benders' procedure are of the same order of magnitude as

those taken by the MIP method.

Among the four techniques, the restricted basis entry method

converges to the worst solutions. Though it quickly arrives at

_I,,+_o__- for _,,- _ +_he smaller problems, it fsi!s +....... ge for

two of the larger problems with 26 service areas and one smaller

problem with I0 service areas.

From the results of these experiments, it is clear that the

switching heuristic is an excellent method for solving the satellite

location problem in terms of the "goodness" of the solution, the

solution time, and in reliability.
CHAImIZR V

SWITCHING HEURISTICS FOR VARIATIONS IN THE SATELLITE LOCATION PROBLEM

The switching heuristic, for solving the satellite location

problem wherethe objective function is the minimization of the total

deviation, was introduced in Chapter 3. The comparison study in

Chapter 4 showed that the switching heuristic outperformed the other

three solution methods that were applied to the set of seven test

problems, both in terms of the quality of the solution obtained and in

the time needed to reach that solution.

Variations in the switching heuristic are introduced in this

chapter. These variations extend the applicability of the switching

heuristic to different satellite location models. A new objective

function, the minimization of maxim_n deviation of the prescribed

location of a satellite from its desired location, is discussed. The

addition of feasible arc constraints to the satellite location problem

is considered. Even thouEh these constraints were specified in the

initial formulations in Figures 2,4, and 5, they were not enforced in

the experiment discussed in Chapter 4.

In the discussion of the minimt_ required separation matrices in

Chapter 2, it was mentioned that solutions obtained using /_S values

(worst case minimum required separation) might be conservative. The

use of /k_ (the minimm_n required separation for the current location of

74
I

i

i

!

I

I

I

i

i

I

I

I

I

I

I

I

i

I

75

the satellites) in place of /_S is investigated in this chapter.

Application of the switching heuristic to a set of test problems first

with /_S, and then with /k_ , shows that this change improves the

objective function value significantly. The switching heuristic can

easily accomodate /k_ in place of /kS, but the other three solution

methods have to undergo extensive modification and significant growth

in the n_ber of decision variables in order to implement the change.

In the final section of this chapter, the application of the

switching heuristic to a "real world" scenario consisting of 28 service

areas and 59 satellites is described. The results obtained confirm the

initial conclusions made about the effectiveness of the heuristic.

Although the variations on the satellite location problem

discussed in this chapter can theoretically be solved using any of the

o_her three ._1.._-.. _.ods, "_+_ some _ .... io_. _ *_ models,

only the switching heuristic is used in the experiments with these

problems. This decision is made based on the excellent performance of

the heuristic as evidenced by the experimental results presented in

Chapter 4.

5.1 Minimization of the maxim_, deviation of prescribed locations from

the corresponding desired locations.

Until now, the objective function for the satellite location

problem has been the minimization of total deviation. Other objective

functions for the satellite location problem might be appropriate, and
76

one such oSjective function is the minimization of the maximum

deviation between an assigned location and the corresponding desired

location (hereafter referred to as the minimization of maximum

deviation). Since this objective function ensures that the largest

deviation is minimized, it tries to prevent any one satellite from

having a large deviation so that the other satellites may have small

deviations, a situation which may occur when the objective function is

the minimization of total deviation.

Although the other solution methods can also be applied to the

satellite location problem with this objective function, only the

switching heuristic is used in this case. The switching heuristic that

is applied is the same as the one used with the objective function of

minimization of the total deviation. Changing the objective function

to the minimization of maxim%_ deviation affects only the linear

programming formulations associated with the switching heuristic and

does not require any changes in the implementation of the heuristic

itself.

The new primal linear progrssming formulation is shown in Figure

16. The objective function (5.1 ), the minimization of the maxim_mm

deviation, is acheived through the minimization of a single "dtmm_"

variable which represents the maxim_n deviation of an assigned location

from the corresponding desired location. Constraints (5.2 ) and (5.3)

together ensure that Z is the maximum deviation over all satellites.

For any satellite to the east of its desired location, constraint (5.2)

ensures that Z is at least as large as the deviation between prescribed

and desired locations. Constraints (5.3) perform the same task for

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

i

I

I

77

MINIMIZE

subject to

Y + Z > d

j - i

i:S(j);j=l,...n

Y - Z < d

j - i

- y _>

Yk j /_Sih

i:S(j);j:l,...n

_-SI_I;_=I;K:j+I_...n ,. .n-1

Y > 0 j:l,...n

j -

z > o I

where

n : number of satellites and orbit positions

Y = the prescribed location for orbit position j

J

Z = the maximum deviation from any desired location

S(j) : the satellite currently in orbit position j

d = the given desired location for satellite i

i

/kS = the required separation between satellites i and h

ih

(5.1)

(5.2)

(5.3)

(5.4)

(5.5)

(5.s)

Figure 16. The Primal Formulation for the Satellite Location Problem

with the Objective of Minimizing the Maxim_n Deviation and

for a Given Ordering.
78

satellites located to the west of their desired locations. Constraints

(5.4) ensure that the minimun required separations are met for all

pairs of satellites. Constraints (5.5) and (5.6) are non-negativity

constraints on the decision variables.

The dual linear programming formulation corresponding to the

primal formulation in Figure 16, is shown in Figure 17. Constraints

(5.8) correspond to the "y" variables in the primal and constraint

(5.9) corresponds to the "Z" variable in the primal. The constraint

matrix is still defined solely by orbit positions, all satellite

dependent parameters appearing only in the objective function.

Therefore, the implementation of the switching heuristic is exactly the

same as it was when the objective function was the minimization of

total deviation. The presentation of experimental results with this

objective function is deferred until Section 5.3.

5.2 Feasible arc constraints for the satellite location problem

The portion of the gecstationary orbit that is visible from every

test point in a service area is called the visible arc for that service

area. A satellite can be located only in the visible arc corresponding

to its service area. Further, satellite locations usually have to be

assigned so that a satellite is at least some specified minimum angle

of elevation above the horizon for all the test points in its service

area. The portion of the geostationary orbit within which the

satellite(s) of a service area can be positioned taking into account

I

I

I

i

I

I

I

I

I

I

I

I

I

I

I

i

I

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

i

79

subject to

where

n n

W V

Z = ___ du + ___d w j ij j ij

+

n-I n

j_ k_÷l_SihVjk

j-I n

u j +w j + k vkj -k= 1 jk

< 0 j=l,...n

n n

J J J

< 1

w < 0

jv > 0

jk-

(5.7)

(5.8)

(5.9)

(5.10)

(5.11)

(5.12)

n, di ' ZlSih are as defined in Figure 16

th

u : the dual variable corresponding to the j-- constraint in

j the set of primal constraints(5.2)

th

w : the dual variable corresponding to the j-- constraint in

j the set of primal constraints(5.3)

th

v = the dual variable corresponding to the jk-- constraint in

jk the set of primal constraints(5.4)

Figure 17. The Dual Formulation for the Satellite Location Problem

with the Objective of Minimizing the MaximumDeviation

for a Given Ordering
8O

these limitations and other requirements (if any) is called the

feasible arc for that service area. These constraints on the

assignment of satellite locations were specified as simple upper and

lower bounds on the decision variables correspondinE to assiEned

satellite locations in the formulations given in FiEures 2,4 and 5.

In the experiment comparinE the four solution methods,

constraints that would force satellites to be located within their

respective feasible arcs were not enforced. The objective function

considered in that experiment, the minimization of total deviation,

tends to place satellites within their feasible arcs, since the

specified desired location for each satellite is at or very near to the

center of the feasible arc for each satellite. The same is true when

the objective function is the minimization of maximL_ deviation.

However, with either objective, there is no Euarantee that all

satellites will be placed in their respective feasible arcs in any

solution obtained. Constraints that explicitly force satellites to be

placed in their specified feasible arcs are included in all the

experiments described in this chapter.

In the primal formulations (FiEures 12 and 16), irrespective of

the objective function, the feasible arc constraints are imposed

throuEh simple lower and upper bound constraints on the decision

variables correspondinE to satellite locations. The constraints to be

added to the primal linear progrsmm_nE formulations are indicated

below •

YJ l Li i:S(j);j:l,...n (5.13)

y_ _ H_ i:S(j);j=l,...n (5.14)

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

l

I
I

I

I

I

I

I

I

l

I

I

I

I

I

I

I

I

I

I

where

81

yj = the assigned location of orbit position j

S(j ) : the satellite in position j in the give ordering

n = the number of satellites

L i = the lower limit on the feasible arc for satellite i

Hi = the upper limit on the feasible arc for satellite i

The corresponding dual formulations after the addition of the

feasible arc constraints are given in Figures 18 and 19. The dual

formulation in Figure 18 corresponds to the objective function of

minimizing the total deviation, and the formulation in Figure 19 to the

objective function of minimizing the maximum deviation. The changes in

these two formulations, from their counterparts in which feasible arc

limits were not imposed (Figures 13 and 17 respectively), amount to the

-_ddition of two -^_- ^_v_ ...-_i .8/_. ^_ These "_" ._nd "q" variables

correspond to the lower and upper bound constraints, respectively, that

are placed on the decision variables in the primal formulations.

The effect that the addition of feasible arc limits has on the

switching heuristic is that feasible solutions to the problem may not

exist for any given ordering, while feasible solutions for any possible

orderinE always exist for the formulations without feasible arc

constraints. Infeasibility in the primal linear program corresponds to

unboundedness in the dual linear proErsm. To allow for dual

unboundedness, the implementation of the switching heuristic has to be

modified.

The most direct implementation of feasible are limits would be to

terminate the optimization of the dual problem when an indication of
82

MAXIMIZE

n n-1 n

j j j k 1 jk jk

n n

+ L.p J JJ J JJ

(5.15)

subj_t to

j-I

u+ _V j k kj

n

- Iv +P +q.

k:j+l jk j j

_< 0 j:l,...n (5.16)

-1 < u < 1

-- j --

v > 0

jk -

j:l,...n

j:l, ••.n-I ;k=j+l, ••.n

(5.17)

(5.18)

P. , -q. _> 0

J J

j:l,...n (5.19)

where

n, K , Q , u , v are as defined in Figure 13.

j jk j jk

L : lower limit of feasible arc for the satellite in position j

J

H : upper limit of feasible arc for the satellite in position j

J

= dual variable corresponding to constraint (5.13) i.e. the

Pj constraint on the lower limit of feasible arc in the primal

q. : dual variable corresponding to constraint (5.14) i .e. the

j constraint on the upper limit of feasible arc in the primal

Figure 18. The Dual Formulation for the Satellite Location Problem

with Feasible Arcs - The Objective Function is the

Minimization of Total Devia£ion

I

I

I

I

I

I

I

I

I

I

I

I

I

l

I

I

i

I
I

i

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

83

n n n n

J JJ J Jj J JJ J JJ

+

n-1 n

j/-=_.L_=j+l /As ih vjk

(5.20)

subject to

j_ n

u + w + p + q +_L_v - Lv < 0

j j j j k--I kj k=j+l j_ -

j:l,...n (5.21)

n n

_- y-

(5.22)

where

u , -w > 0 j=l,...n

J J -

v > 0

jk -

j:l,...n-l;k:j+l,...n

p. , -q. _> 0 j=l,...n

J J

(5.23)

(5.24)

(5.25)

n, d , ZlSih , u , w , v are as defined in Figure 17 i j j jk

L , H., p. , q. are as defined in Figure 18

J _ J J

Figure 19. The Dual Formulation for the Satellite Location Problem

with Feasible Arcs - The Objective Function is the

Minimization of Maximum Devlation
84

unboundedness is obtained, and discard the ordering corresponding to

the dual problem under consideration. This would be similar to the

termination of reoptimization based on the objective function value

which is described in Section 4.4.

In the linear programming code used, termination due to

unboundedness leaves the basis in an undefined state. As a result,

the basis corresponding to the previous feasible solution cannot be

regenerated. This difficulty is avoided by introducing artificial

upper and lower bounds on the "p" and "q" variables, respectively,

which were previously unbounded. Restricting the values that the "p"

and "q" variables can assume eliminates the possibility of the dual

problem being unbounded for any ordering of satellites. If the

artificial bounds on the "p" and "q" variables allow the variables a

range much larger than the entire feasible arc, then no feasible

solutions to the primal problem are eliminated from consideration.

This method of avoiding unboundedness in the dual is used in the

experiments described in this chapter. All orderings are dual feasible

and bounded, but some have very high objective function values (those

corresponding to infeasible primal solutions), and these are quickly

fathomed once a solution corresponding to a primal feasible solution is

found.

I

I

i

I

I

I

I

I

I

I

I

I

I

I

I

I

i

I
I

I

I

I

I

I

I

I

l

I

I

I

I

I

I

I

I

I

85

5.3 Experimental results for the satellite location problem with

different objective functions and feasible arc constraints.

For the seven scenarios described in Appendix C, the associated

satellite location problems with limits on the feasible arcs are solved

using the switching heuristic, first with the objective of minimizing

the total deviation and then with the objective of minimizing the

maximum deviation.

The effect of the subgroup size on the performance of the

switching heuristic is examined. As mentioned in Chapter 3, the

subgroup size is the number of satellites that are permuted at a time.

Subgroup sizes of 2,3,4, and 5 are considered as is increasing the

subgroup size by one, from 2 to 5, during the execution of the

algorithm. When the subEroup size is limited to a sLngie value, the

switching heuristic only considers subgroups of that size and

terminates when no improved solutions can be found. With the

increasing subgroup size option, if the heuristic cannot find an

improved solution with the current subgroup size, it increases the

subgroup size by one and continues. Termination occurs when the given

maximum subgroup size is reached and no improved solution can be found.

The results for the computer runs made with the objective function

of minimizing total deviation and with limits on feasible arcs are

presented in Table 2. The results for the runs with the objective

function of minimizing maximtm deviation and with limits on feasible

arcs are presented in Table 3. The layouts for the two tables are

identical. The name of the scenario and the number of satellites in it
TABLE 2. SWITCHING HEURISTIC RUNS ON THE SEVEN SCENARIOS WITH THE

OBJECTIVE OF MINIMIZING TOTAL DEVIATION AND WITH LIMITS

ON FEASIBLE AIK_.

SCENABIO SUB FINAL TOTAL # OF # OF TIME TO

86

I

i

I

I

I

(# SAT)

S .AMERICA

(13)

E.EUNOPE

(12)

W.EUNOPE

(12)

S .E.ASIA

(10)

N.AFRICA

(10)

2

3

4

5

INCR.

2

3

4

5

INCR.

2

3

4

5

INCR.

2

3

4

5

INCR.

2

3

4

5

INCR.

SOLUTION

VALUE

27.23

22.14

30.94

30.94

27.01

41.48

47.85

47.85

47.85

41.48

31.71

37.63

47.08

41.77

43.26

62.00

54.41

42.61

42.61

42.61

24.63

59.44

54.56

41.42

41.42

TIME

TAKEN

0.7

1.8

3.7

16.1

10.7

0.8

0.9

2.7

7.0

6.7

0.6

1.0

4.6

18.0

7.4

1.6

2.3

4.3

11.0

12.4

1.6

2.1

3.9

13.3

12.7

MAJOR

ITERS.

3

3

2

2

8

5

3

3

2

8

3

3

5

5

8

3

4

4

3

12

2

3

3

3

10

FEAS.

SOLNS.

13

9

12

14

13

0

0

6

6

1

0

7

7

12

16

0

7

6

14

I0

A FEAS.

SOLN.

1.9

8.1

2.5

0.1

0.I

0.I

0.1

0.1

1.3

4.2

1.4

0.2

0.3

0.4

0.4

0.2

0.4

1.4

0.3

I

I

I

I

I

I

I

I

i

I

I

I
I

!

i

i

I

TABT_ 2.

(contd. )

SCENARIO

SWITCHING HEURISTIC RUNS ON THE SEVEN SCENARIOS WITH THE

OBJECTIVE OF MINIMIZING TOTAL DEVIATION AND WITH LIMITS

ON FEASIBLE ARCS.

SUB FINAL TOTAL # OF # OF TIME TO

87

I

I

I

I

I

I

I

I

I

I

I

I

I

I

(# SAT)

Et_Ol_

(26)

GROUP

SIZE

2

3

4

5

INC_.

NCS AMER. : 2

3

(26) 4

5

INCR.

SOI/TFION

VALUE

TIME

TAKEN

239.10 3.7

193.00 9.0

200.29 43.1

160.96 89.5

204.58 81.7

59.29

5O.75

55.78

63.22

46.44

3.9

10.8

41.9

120.0

55.0

MAJOR

ITEKS.

6

5

7

3

14

FEAS.

SOLNS.

1

13

15

32

8

A FEAS.

SOLN.

27.4

30.5

6.9

1.7

2.7

7.1

32.9

1.7

,,

All times are in CPU seconds on an IBM 3081-D

t - termination due to run time limit of 2 minutes
TABLE3. SWITCHINGHEURISTICRUNSONTHES_ SCENARIOSWITHTHE

OBJECrlVEOFMINIMIZINGMAXIMUMDEVIATIONAND

WITHLIMITS ONFEASIBLEARCS.

SCENARIO SUB FINAL TOTAL # OF # OF TIMETO

88

I

I

I

I

I

(# SAT)

S .AMERICA

(13)

E.EUI_PE

(12)

W.EUIK)PE

(12)

S.E.ASIA

(10)

N.AFRICA

(10)

GROUP

SIZE

2

3

4

5

INCR.

2

3

4

5

INCR.

2

3

4

5

INCR.

2

3

4

5

INCR.

2

3

4

5

INCR.

SOLUTION

VALUE

5.00

5.52

5.52

4.90

4.68

8.14

8.51

7.98

7.23

7.23

11.13

10.16

7.57

7.41

7.41

13.48

12.96

12.78

12.78

12.78

4.35

11.07

11.07

10.19

11.07

TIME

TAKEN

1.1

2.0

7.0

18.3

9.5

1.3

1.4

3.0

6.1

5.1

1.4

1.4

2.7

9.6

18.2

1.7

1.9

2.7

7.5

7.2

1.7

2.2

3.4

9.9

8.3

MAJOR

ITER_.

3

3

3

2

8

5

3

3

2

9

3

3

3

3

10

2

2

2

2

6

2

2

2

2

6

FEAS.

SOLNS.

0

0

0

1

1

7

8

I0

13

ii

0

0

2

2

11

2

3

4

4

5

0

1

I

2

I

A FEAS.

SOLN.

ram9,7

3.1

0.2

0.2

0.2

0.2

0.2

umu

1.3

4.0

2.5

0.2

0.2

0.3

0.5

0.2

0.5

0.8

2.1

0.6

I

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

I

TART._. 3.

(contd.)

SCENARIO

SWITC}HNG HEURISTIC RUNS ON THE SEVEN SCENARIOS WITH THE

OBJECTIVE OF MINIMIZING MAXIMb_ DEVIATION AND

WITH LIMITS ON FEASIBLE ARCS.

SUB FINAL TOTAL # OF # OF TIME TO

89

I

I

I

I

I

I

I

I

I

I

I

I

I

(# SAT)

EUROPE

(26)

NCS AMER.

(26)

2

3

4

5

INCR.

2

3

4

5

INCR.

SOLUTION

VALUE

17.39

15.63

14.53

14.34

14.01

8.78

7.45

7.43

5.70

6.00

TIME

TAKEN

7.7

16.5

30.2

85.7

109.8

9.7

6.5

17.0

120.0

51.6

MAJOR

ITERS.

6

7

5

3

17

6

2

2

3

II

FEAS.

SOLNS.

1

2

5

21

6

A FEAS.

SOLN.

_mm

22.3

41.5

24.1

7.0

3.8

10.6

40.3

7.0

All times are in CPU seconds on an _ 3081-D

t - termination due to run time limit of 2 minutes

I
9O

are stated in the first column. The subgroup size is given in the

second columm. The final solution obtained, the time taken to reach

termination, and the number of major iterations performed, appear in

the third, fourth, and fifth columns, respectively. The nt,mber of

feasible solutions found and the time that elapsed before the first

feasible solution was found are shown in the sixth and seventh columns.

From Tables 2 and 3, it is clear that the switching heuristic with

increasing subgroup size and the heuristic with a fixed subgroup size

of 5, consistently outperform the alternatives with regard to solution

value. Out of the fourteen problems (seven each with minimization of

total deviation and minimization of maximum deviation), the switching

heuristic with increasing subgroup size found the best solution in ten

cases. The heuristic with fixed subgroup size of 5 found the best

solution in nine cases. The other three alternatives together could

find the best solution only three times. In some problems, two or more

of the five strategies found the best solution. The heuristic with

increasing subgroup size performs better than the heuristic with

subgroup size equal to 5 in terms of computation time, requiring less

CPU time for eleven of the fourteen problems.

In order to determine how close the solutions found by the

switching heuristic are to the optimal solution, an attempt was made to

solve all fourteen problems using the mixed integer programming method

(MIP). The results are presented in Tables 4 and 5. The MIP finds the

optimum solution for five out of the fourteen problems, the remaining

nine being terminated due to accuracy checks or limits on rum time.

For nine problems, the MIP provided feasible solutions. A comparison

I

I

I

I

I

I

I

I

I

l

l

I

I

I

I

I

I

I
I

I

I

I

I

I

I

l

I

I

I

I

I

I

I

I

I

I

I

91

TABLE 4. COMPARISON OF SWITCHING SOLUTIONS TO MIP SOLUTIONS

MINIMIZE TOTAL DEVIATION (WITH FEASIBLE ARCS)

M. I .P I SWITCHING '

PROBLEM ..................................... I................................. {..........................

OPTIMUM i TIME # OF I BEST METHOD TIME SOL. W/_TIME ',

(# SAT) SOLN. i NODESI SOLN. (K:) INCR. KI I

I............................................... !.......................................... _i................................................. i........................................................................................................... :..................................................................i

S.AMER

(13)

E. EUR

(12)

W. EI/R

(12)

SE.ASIA

(10)

N.AFRIC

(1o)

EUROPE

(26)

NCS AM.

(26)

27.01 I 121

@

43.87 160

t

41.77 300

41.61 207

41.42 197

t

--- 600

t

--- 600

I.................. I ........ Z

442 T 27.01

500

1500

1827

1460

41.48

41.77

42.61

41.42

160.96

50.44

INCR.

INCR.

INCR.

11 27.01

{ 1 41.48

18 43.26

i

i

! 4 42.61

13 41.42

!

' l

, 90 I 204.6

55 i 50.44

!

12

13

82

55

• i

--._............................ .L .................. ±.......................................... _...........................

NOTES :

@ - not proven optimum, termination due to accuracy checks

t - not proven optimum, termination due to time limit

All times in CPU seconds on an IBM 3081-D.

The MIP runs were made with REAL*16 (128 bits) arithmetic. All

switching runs were made with REAL$8 (64 bits) arithmetic. On

average REAL*16 is 3 times slower than REAL*8. (Accuracy check

problems necessitated the use of REAL*16 for the MIP runs.)
92

TABLE 5. COMPARISON OF SWITCHING SOLUTIONS TO MIP SOLUTIONS

MINIMIZE MAXIMUM DEVIATION (WITH FEASIBLE ARCS)

l M.I. P SWITCHING

PROBLEM! .............................. !.................. r..................................................................................

IOPTIMUM! TIM*El NODES BEST METHOD TIME SOL. W/ TIME

(# SAT) tSOLN. l SOLN. (K=) INCR. K

t .................................................................... ,..................................

S.AMER 4.68 I 252 1045 4.68 INCR. 9 4.68 9

(13) !

tl

E.EUR 7.08 I 300 1200 7.23 INCR. 5 7.23 5

(12) I

ti

iW.EUR 7.33 ! 300 1300 7.41 5 10 7.41 18

(12) I

I

SE.ASIA 12.78 I 269 1793 12.78 4 3 12.78 7

(10) I

e i

N.AFRIC --- i 9 -- 10.19 5 10 11.07 8

(10) t

ei

EUROPE --- I 325 -- 14.01 INCR. 110 14.01 110

(26) i

Q l

NCS AM. --- 1 62 -- 5.70 5 120 6.00 52

(26) I

1

..................... _...................................... I.......... ----J--.--..--..--.--_ ...........................................................................

NOTES :

@ - not proven optimum, termination due to accuracy checks

t - not proven optimum, termination due to time limit

All times in CPU seconds on an IBM 3081-D.

The MIP runs were made with REAL*16 (128 bits) arithmetic. All

switching runs were made with REAL*8 (64 bits) arithmetic. On

average REAL*16 is 3 times slower than REAL$8. (Accuracy check

problems necessitated the use of REAL*16 for the MIP runs.)

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
l

I

I

I

I

I

I

I

I

I

l

I

I

l

I

I

I

I

93

with the best solutions generated by the switching heuristic for these

nine problems shows that the switching solution is the same as the MIP

solution in five cases. The switching algorithm found an optimal

solution in four of these cases. In one case, the switching heuristic

finds a solution better than the prematurely terminated MIP solution.

For the remaining three cases, the solutions generated by the heuristic

are within 2.5% of those found by the MIP.

In Tables 4 and 5, the solutions obtained using the switching

heuristic with increasing suh_-oup size are indicated. For eight of

the nine problems for which feasible solutions have been found by MIP,

the switching solutions are the best solutions obtained by the

switching method.

These results indicate that the switching heuristic eonsistently

Drovides optimal or near optimal solutions for the satellite location

problems with limits on feasible arcs and for the objective functions

studied.

5.4 On using /k_ in place of /kS

In all the experiments discussed so far, /kS (the worst case

minimum required separation) has been used as the separation that is

required between pairs of satellites. The effect of using /k_ (the

minimum required separation based on the current location of the

satellites) instead of /kS is now examined.
94

In the implementation of this change with the switching heuristic,

/k_ matrices, spaced at specified intervals from the easternmost limit

to the westernmost limit of the feasible arcs, are used. In the

experiments, an interval spacing of I0" is used.

The minimum required separations are redefined at the beginning of

each iteration using the /k_ matrices. (An iteration consists of Steps

4 and 5 in the description of the heuristic in Section 3.4). The +

midpoint between the current prescribed satellite locations for each

pair of satellites is found. The maximum of the two /k0 values for

this pair of satellites that are nearest to the calculated midpoint

becomes the current minimum required separation for the pair. For

example, if satellites i and j are currently located at II ° and 14 o

respectively, the midpoint is at 12.5 °. Matrices for /k_ are available

at I0 ° and 200, since the matrices are available at I0" intervals. The

current minimua required separation is set to the maximtn of the two

/k_ values for satellites i and j in these two matrices. As the

iteration progresses and a new subgroup of satellites is considered,

the minimum required separations for all satellite pairs within the

subgroup are reset using the above procedure.

At the initial ordering, no prescribed satellite locations are

available. The /kS values are used for the minim_ required

separations, and the dual linear program is solved to optimality. With

the satellite locations obtained from the optimal solution, the minimum

required separation values are reset as described in the previous

paragraph. The linear program corresponding to the initial ordering is

solved again, this time with the revised separation values. The

I

l

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

l

I

I

l

I

I

I

I

l

I

I

l

I

I

optimal solution obtained is taken

switching heuristic.

This is only one possible implementation

switching heuristic. There are several

95

as the starting solution in the

of /_ matrices with the

other ways in which these

matrices could be used in place of /kS, for example, every time a

switch is made all minimt_ required separations could be reset. This

implementation offers the benefits of using the /k_ matrices with Only

a limited amount of time spent in resetting the minimum required

separations and in table lookups.

In the experiment to compare the effects of using /k_ in place of

/kS, seven test problems (see Appendix C) are used. These seven

scenarios are the same as those used in the previous experiments. Two

problems are solved for each scenario, one where the objective is the

minimization of the total deviation and the other with the objective of

minimizing of the maximum deviation. For all fourteen problems, limits

on feasible arcs are included. The switching heuristic with increasing

subgroup size as implemented in Chapter 4, together with the changes

described in this chapter, is applied to each of the fourteen problems

using /k_ matrices to generate the minimum required separaticms. The

solutions for the same set of problems in which /kS is used, are

already available from the previous experiment (See Tables 4 and 5).

The results for the seven problems with the objective functicm of

minimizing total deviation are shown in Table 6. For the seven

problems with the objective function of minimizing maximum deviation,

the results are presented in Table 7. The final solution, the time to

termination, and the number of major iterations performed are given for
96

TABLE 6. COMPARISON BETWEEN SWITCHING WITH/_d AND SWITCHING WITH/_S

Objective : Minimize total deviation

(with feasible arc restrictions)

I

l

I

I

SCENARIO

S .AMERICA

E.EUROPE

SWITCHING WITHZld

(INCR. K 2 TO 5)

SOLUTION : TIME

W.EUROPE

S.E.ASIA

N.AFRICA

EUROPE

NCS .AMER.

17.04 : 9

31.74 : 12

23.71

34.75

26.24

11

t

98.68

28.77

ITER.

8

13

7

10

SWITCHING WITH /kS

(INCR. K 2 TO 5)

SOLUTION

27.01

41.48

43.26

42.61

TIME

11

12

8 : 41.42 13

: :......

: 120 17 :

O

: 81 : 17

204.58

50.44

82

ITER.

8

8

8

12

10

14

55 : 9

WITH /_kS

BEST

SOLN.

KNOWN

0

27.01

41.48

41.77

o

41.61

O

41.42

160.96

50.44

I

I

I

I

I

I

I

I

All times are in CPU seconds on an IBM 3081-D

o - proven optimt_solution

t - terminated due to time limit

ITER = ntunber of major iterations in the Switching heuristic

I

I

I

I

I

I
l

I

I

I

97

TABLE 7. COMPARISON BETWEEN SNITCHING WITH /_ AND SWITCHING WITH /_S

Objective : Minimize maximum deviation

( with feasible arc restrictions )

I

I

I

I

I

I

I

i

SCENARIO SWITCHING WITH /k#

(INCR. K 2 TO5)

SOLUTION

S.AMERICA 3.00

E.EUROPE 5.71

W.EUROPE 6.12

S.E.ASIA 10.95

N.AFRICA : 11.35

EUROPE 10.98

NCS.AHER. 3.82

TIME : ITER.

......:......:

9 : 9

!

!

13 : 11

!

!

33 : 14

10 : 9

...... : ......

11 : 8

SWITCHING WITH /kS

(INCR. K 2 TO 5)

SOI]JTION : TIME

4.68

7.23

7.41

12.78

11.07

ITER.

9 8

5 9

18 10

7 6

I

8 : 6

WI_ _S

BEST

_.

KNOWN

0

4.68

7.08

7.33

O

12.78

10.19

I I

104 : 21 : 14.01

88 10 '

I 6.00

: II0 17

52 11

14.01

5.70

I

I

I

I

I

I

All times are in CI_ seconds on an IBM 3081-D

o - proven optimum solution

ITER - number of major iterations in the Switching heuristic
98

the computer runs made for both the /k_ and /kS situations. The last

col_mm contains the best solution kno_m for the problem when /iS is

used. This solution was generated either through mixed integer

programming or with the switching heuristic.

Using /k_ yields reductions of more than 16% in the objective

function value in every case, from the best solution with /kS, when the

objective is the minimization of total deviation. The smallest

percentage reduction is 16% (the S.E.ASIA scenario), and the largest is

43% (the NCS. AMER. scenario). When the objective is the minimization

of maximum deviation, the percentage reductions in objective function

value range from 14% to 36% in the six cases where improvements are

obtained. In one instance, the best solution using /kS is 10% better

than the solution obtained using /k_.

There is a tendency for runs made with /k0 to take more time and

more iterations than runs with /kS when the objective is the

minimization of maximun deviation. No obvious trend with regard to

time or number of iterations appears when the objective is minimization

of total deviation, although the two larger problems (26 satellites)

are more time consuming and require more iterations when /k0 is used.

The gains in the objective function values are significant enough when

/k0 is used in place of /kS, that increases in solution time and number

of iterations are of minor importance.

The conclusion drawn from this experiment is that it is definitely

preferable to use /k0 in place of /kS in satellite location problems.

When /k0 is used, the heuristic is more likely to find feasible

solutions. However, a feasible solution obtained using /kS values is

I

I

I

I

I

I

I

I

I

I

I

I

I

I

i

I

l

I
I

I

l

I

I

I

I

I

I

I

I

I

I

I

I

l

I

I

99

likely to have larger C/I margins than a feasible solution to the same

problem obtained when /k_ values are used. The use of /k_ in place of

/kS does not appreciably degrade the performance of the switching

heuristic with regard to computation time.

5.5 Application of the Switching heuristic to the Region 2 scenario

The experiments described in Sections 4.6, 5.3, and 5.4 were

conducted using scenarios which ranEed in size from I0 to 26 service

areas and satellites. In this section, the switching heuristic is

applied to a scenario which has 28 service areas and 59 satellites.

Several of the 28 service areas have more than one satellite. This

scenario was provided by. NASA Lewis Research Center. It is

representative of satellite synthesis problems for Region 2, the

nations in the western hemisphere. Satellite allotments in the Fixed

Satellite Service (FSS) for Region 2 is one of the major goals of the

World Administrative Radio Conference scheduled for mid 1988 (WARC'88).

The scenario for Region 2 is described in Appendix E. The names

of the 28 service areas, the number of satellites associated with each

service area, the desired locations and the limits on the feasible arcs

for service areas are given. The /kS matrix is also shown.

In this experiment, two versions of this scenario are considered.

In the first version (VER.I), all 25 satellites belonging to service

area USA have the same desired location, 96 o . The minim_n required

separation between two satellites belonging to USA is 2", irrespective
I00

of where the satellites are loca1_d. Hence, in any feasible solution,

at best the 25 USA satellites could be spaced at 2 ° intervals about the

desired location 96 0, ranging in position from 72 ° to 120 °. Therefore,

in the second version of the scenario (VER.2), the desired locations

for the 25 USA satellites are given desired locations ranging from 72o

to 120 ° at 2 ° intervals. The two versions of the scenario are the same

in all other respects.

In Table 8, the results of four computer runs made with this

scenario are presented. In each case+ the switching heuristic with

increasing subgroup size (2 to 5) was used. The objective function

throughout the experiment was the minimization of total deviation.

Limits on the feasible arcs for service areas were enforced in all four

cases. Two runs were made with each version of the scenario - the

first run being made with /__S and the second with /_.

The final solution values obtained in the runs made with VER. 1 are

not directly comparable with the values obtained with VER. 2, owing to

the differences in the desired locations for the satellites belonging

to the USA.

The only feasible solution that was found occurred when VER.2 was

used with /k_. The remaining three runs terminated with infeasible

solutions, although in every one of these three cases, only one or two

satellites were positioned outside their respective feasible arcs. The

combination of spacing the desired locations for satellites belonging

to the same service area and using /k_ instead of /kS improves the

performance of the switching heuristic considerably over the case where

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
i

I

i

I

i

TABLE 8,

VERSION

RESULTS OF RUNS WITH THE REGION 2 SCENARIO

/_IS FINAL TOTAL # OF SOLN. FIRST TIME TO

i01

!

I

I

i

!

OF

SCENARIO

VER. 1

VER. 1

VER.2

VER.2

OR

/_IS

:/As

! 1

! !

:ZA_:

l l

! l

759.59

792.91

488.19

404.19

TIME

TAKEN

1200

1200

710

1200

MAJOR

ITER.

26

44

NO

: NO

27 : NO

34 : YES

FEAS. FE_S.

SOLN.

..... _o

mo_Q Emm

u_ .....

|

430.32 335

I

I

I

I

I

I

I

I

All times are .in CIR/ seconds on an IBM 3081mD

Runs taking 1200 seconds were terminated by limits on run time
the same desired locations and /kS are used. Each of the

itself does not drsm_tically change the solution obtained.

102

factors by

I

I

I

I

I

l

I

l

I

I

I

I

I

I

I

I

I

I

I
I

I

!

I

I

i

I

I

!

I

I

I

I

I

I

I

l

I

CHAPTER VI

REfX3MMENDATIONS AND OONCLUSIONS

A major portion of this research has been focused on the

application of the switching heuristic to satellite location problems.

The objective functions that were used were the minimization of total

deviation and the minimization of maxim_ndeviation from given desired

locations. In an effort to indicate directions for future research

with the switching heuristic, other problems to which the switching

heuristic can be applied, with appropriate changes in its

implementation, are discussed in this chapter. Two applications are

r=1_+_ +_ Q_+=11_+_ q vs_t_ synthesisj _._i!e a third is _ociated with

the more general area of job sequencing and scheduling. This

manuscript concludes with a stm_ary of the research performed and the

contribution it makes to the fields of satellite system synthesis am_

Operations Research.

6.1 The allocation of arc segments to service areas

The problem concentrated on throughout this manuscript has been

the assignment of orbit locations to individual satellites. These

assigned locations can be said to be point assignments in the

103
104

geostationary orbit. An alternate synthesis strategy is the allocation

of a portion of the geostationary orbit, i .e. an arc segment, to every

service area in a given scenario. In this case, the administration of

each service area is at liberty to place as many satellites in as many

locations as it wishes, as long as all the satellites are located

within the arc segment allocated to that service area. It is up to

each individual administration to resolve interference problems between

its own satellites.

The allocation of arc segments differs from the assignment of

satellite locations in that arc segments are assigned to service areas

in the former case, while specific orbit locations are assigned to

satellites in the latter. In the allocation of arc segments the system

design has to allow for an administration placing a satellite anywhere

in its assigned arc. Hence, in the allocation procedure, interference

calculations have to be made based on the worst possible situation.

This corresponds to separating the nearest edges of two arc segments

allocated to two service areas by the minimun separation required

between satellites that belong to those service areas.

If, in the scenario to be examined, a large proportion of the

service areas have multiple satellites, then the number of decision

variables in the arc segment approach is likely to be less than the

number of decision variables in the point location approach. The term

"decision variables" is used here in a generic sense and not with

regard to any actual implementation. Another advantage of the arc

segmentation approach over the point location approach is that the

former gives much more freedom to the individual administrations in the

I

I

I

I

I

I

I

I

I

I

I

I

I

|

I

I

I

I

I
I

I

!

I

I

I

I

I

I

i

I

I

I

I

I

I

!

i

105

actual location of satellites, and in the addition of satellites at a

future date. The assignment of specific locations to satellites is a

more rigid strategy in that satellites cannot be added at a later date

without the re-evaluation of the entire initial plan.

It is possible that in real problems, involving all the national

administrations in one or more continents, solutions with the arc

segment allocation approach will contain a large n%snber of

infinitesimal arc lengths. If arc segment allocation problems are hard

to solve, the point location strategy might be used to determine the

feasiblity of a particular scenario.

A possible objective function for the arc segment allocation

problem is the maximization of the smallest arc segment assigned to any

service area. One set of constraints in the problem consists of the

l_m_÷o on feasible arcs, which const__ain the arc segment -_igned to a

service area to he within the feasible arc for that service area. The

other constraints that have to be satisfied are the minim%_ required

separations between satellites.

A primal formulation for the linear program corresponding to the

arc segment allocation problem described above is shown in Figure 20.

The formulation is for the situation when the ordering among the arc

segments is given (i.e., a formulation that can be used with the

switching heuristic). This formulation corresponds to the primal

formulation used when the ordering of the satellites was given (Figure

12). In this formulation, arc segments are ordered by their respective

midpoints.
106

MINIMIZE

subject to

- Z (6.1)

Y - Y - Z > j=l,...{n-I i .2) k j - /_Sih i:S(j, ,k:j_l_i_in (6

where

Y - 0.5 Z > L i=S(j); j=l,...n (6.3)

j - i

Y + 0,5 Z _ H i=S(j); j=l,...n (6.4)

j i

z ! o (6.5)

Y = the midpoint of the arc segment in position j in the

j ordering of arc segments

Z = the minimum arc segment length that is assigned

L : the lower limit of the feasible arc for the arc segment

i for service area i

H - the upper limit of the feasible arc for the arc segment

i for service area i

S(j) : the service area whose arc segment is currently in

position j

n = the number of service areas

: the minimum required seperationbetween satellites of /kSih service area i and servlce area h

Figure 20. The Primal Formulation of the Linear Program for the

Arc Segment Allocation Problem with a Given Ordering

of theArc Segments.

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
i

I

I

I

I

I

l

l

I

I

I

I

I

I

I

I

I

I

I07

The objective function (6.1) is the minimization of "-Z", thereby

maximizing "Z", the minimum arc segment. The primal is set up as a

minimization problem so that the dual is a maximization problem,

thereby retaining a similar structure to that of previously considered

dual formulations used with the switching heuristic.

Constraints (6.2) ensure that minimtn required separations are

met. In the formulation in Figure 20, a satellite is asst_ed to exist

at the mid-point of every arc segment. Satellites in the arc segments

i and h, in positions j and k respectively, are separated by a distance

equal to the sum of /_Slh and Z. Therefore, if satellites were

positioned at locations (Yj + 0.5Z) and (Yk - 0.SZ) in the arc segments

corresponding to i and h respectively, the minimum required separation

would still be satisfied. Appropriate /k_'s can be used in place of

/_,S's Cor qt_aints (_ _) and (6 4) er_ure ÷b_ _ assiF_ned ......

do not fall outside the limits on corresponding feasible arcs. If

/kS ih is equal to 0 in any constraint of type (6.2), the variable Z is

dropped from that constraint, the constraint then being defined by the

inequality (6.6).

Yk - Yj l 0 (6.6)

The solution obtained by solving this formulation assigns arc segments

of equal length (i .e. equal to Z) to all service areas.

The dual formulation for the problem is shown in Figure 21. The

constraint matrix refers only to the positions in an ordering. All

references to a particular arc segment and its satellite appear only in

the objective function. Therefore, the switching heuristic can be
108

MAXIMIZE

n-1 n n n

j=/_.[k=o_+l ZISihVjk + J L.pl j + j H.q.1J

(6.7)

subject to

X-

=_ v - j_v +p. + q. _< 0 k kj k= 1 jk j J

j=l,...n (6.8)

n-I n n n

X- _- X- Y-

-j--_ k:J_lVjk - 0.5j:IZ_ Pj + 0.5j=_ qj

< -1 (6.9)

v > 0

jk-

> 0 P. , -q. _

J J

j:l,...,n-l; k:j+l,...,n

j:l,...n

(6.10)

(6.11)

where

n, /kSih , Li , Hi are as defined in Figure 20

th

v = the dual variable corresl:gndi'ng to the jk-- constraint in

jk the constraint set (6.2) in the primal

th

p : the dual variable corresponding to the j-- constraint in

j the constraint set (6.3) in the primal

th

q. : the dual variable corresponding to the j-- constraint in

j the constraint set (6.4) in the primal

Figure 21. The Dual Formulation of the Linear Program for the

Arc Segment Allocation Problem with a Given Ordering

of the Arc Segments.

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
i

I

I

I

I

I

I

I

i

I

I

I

I

I

I

I

I

I

implemented, with some modification,

and 5.2.

109

as described in Sections 3.4, 4.4,

In making a switch in the ordering of arc segments, it might be

necessary to drop a v jk variable in constraint (6.9), if a constraint

of type (6.2) in the primal becomes one of type (6.6)after the switch.

If a constraint of type (6.6) in the primal becomes one of type (6.2)

after the switch, then a vjk variable has to be added in constraint

(6.9) in the dual. When a vjk variable is dropped from the dual

formulation, the basis might become infeasible and this condition has

to be allowed for in the heuristic.

This definition and implementation of the arc segmentation problem

is only one of many that might be possible. There is no empirical

evidence that the switching heuristic performs satisfactorily on this

fomulation of the are segmentation problem. The __i _u_=A purpose here is

to indicate problems relevant to satellite system synthesis that might

be solved using the switching heuristic.

6.2 The explicit allocation of frequency channels

The allocation of frequency channels to service areas, as part of

the system synthesis, has not been explicitly considered in the

solution methods considered so far. The solution techniques are based

on the asst_ption that either the full frequency spectrum is required

by all users, or that channel assignments are prespecified. If channel

assignments are prespecified, then these frequency allocations can be

I
II0

taken into account in the computation of the /kS and /k_ matrices for

that scenario. In some situations, these ass_nptions miEht not be

acceptable. Tentative methods by which frequency allocation can be

included in satellite system synthesis with the switchinE heuristic are

suEEested in this section.

One method, suEEested by Reilly [1986b], is to fix the frequency

channels, and apply the switchinE heuristic to determine the satellite

locations. Then keepinE the satellite locations fixed, the switchinE

heuristic can be used to make other frequency assiEnments that improve

the objective function value. When the heuristic terminates in the

latter phase, the whole procedure can be repeated. This method

requires the determination of the functional relationship between the

separation required in frequency (/kf) and the separation required in

orbit location (/kS) in order to achieve a desired protection ratio.

An alternate method might involve defininE a surrogate variable

that represents a particular orbit location and frequency combination,

and then formulatinE the location and frequency assiEnment problem in

terms of these surroEate variables. The switchinE heuristic or a

similar technique could be applied to the reformulated model in the

surroEate variables.

An initial attempt at defininE the relationship between /_f and

/kS for particular pairs of service areas has been made by Buyukudura

[1986].

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

iii

6.3 On the possible application of the switching heuristic to classes

of job scheduling problems.

The satellite location problem, as defined in Figure 2, is similar

to some categories of job scheduling problems. For example, the

scheduling of jobs with the objective of meeting given due dates as

closely as possible, with processing and setup times for each job, is

closely related to the satellite location problem where the objective

function is the minimization of maxim_a deviation. The due dates in

the scheduling problem correspond to the desired locations in the

satellite problem, the processing and setup times correspond to the

minimt_ required separations. The decision variables, the assigned

loeatio,_ in the satellite problem, are the job completion dates in the

scheduling problem. The processing and setup times required for a job

added to the date a job becomes available for processing gives the

earliest possible completion date for the job, and this corresponds to

the lower limit on the feasible arc for a satellite in the satellite

location problem. If tardiness is not permitted in the scheduling

problem, then the due date is the upper limit on the job completion

date, and this corresponds to the upper limit on the feasible arc in

the satellite location problem.

If the formulation in Figure 2 represented a job scheduling

problem as described above, then the variable X j would represent the

completion date of job j, dj would be the due date for job j, Ej the

earliest possible completion date for the job, Wj the due date added to

I
112

the maximum tardiness allowed. The /kS i_ would represent the sum of

processing and setup time for job j if it were scheduled after job i.

With this definition, /_Sij is not the same as /kS_i. However, when

the switching heuristic is used, the ordering is always specified

before any dual formulation is solved. Therefore, the /_S values to be

used are known. If the job scheduling problem is such that set up

times occur only between adjacent jobs (i .e. non-adjacent jobs do not

interfere with one another), then eliminating redundancies in the

separation matrix will result in a primal formulation with n-I

separation constraints and the corresponding dual variables will also

nt_nber n-l, n being the number of jobs.

The switching heuristic has not been applied to job scheduling

problems of the type described above. The intention here is to

indicate the applicability of the switching heuristic in a more general

context with the expectation that the heuristic will perform as well in

the area of job scheduling as it did in satellite system synthesis.

6.4. Conclusions

In this manuscript, the satellite location problem in satellite

system synthesis has been examined. Four solution techniques have been

considered as candidate solution methods for the problem. An

experimental study was carried out on a set of test problems with the

four methods. The empirical results indicated that the switching

heuristic consistently outperformed the other three methods.

Variations in the satellite location problem were explored and the

!

I

I

I

I

I

I

!

i

I

i

I

!

i

I

!

i

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

113

corresponding modifications required in the switching heuristic were

developed. Experimental results with these variations indicate that

the switching heuristic is well suited to these variations as well as

the original problem. Implementation of the switching heuristic on a

large real problem demonstrated that the heuristic can provide

acceptable solutions for such problems.

This research has been an intensive study of the satellite

location problem. The switching method developed, an interchange

heuristic coupled with an efficient implementation of linear

progrsmming duality, has provided an effective tool for satellite

system systhesis. The techniques that were developed can be applied in

other areas, notably in job scheduling and sequencing. Finally, it has

been demonstrated that complex problems do not always require complex

solution techniques ; a judicious combination of an appropriate

formulation of the problem and a simple heuristic can be very

effective.
APPENDIXA

A DEMONSTRATION THAT LAGRANGEAN MULTIPLIERS FOR THE OPTIMUM SOLUTION

TO THE BENDERS' MASTER PROBLEM MAY NOT EXIST

Consider a satellite location problem in which three satellites

are to be assigned locations. In the corresponding Benders' master

problem (Figure 7), we have three satellites (indexed by i's) and three

orbit positions (indexed by j 's). The constraints (3.23 ), (3.24 ) and

(3.25) in Figure 7 define a 3)[3 assignment problem. Assume that there

are three Benders ' constraints, e, f, and g, and that the coefficients

of the variables in these three constraints are as follows :

VARIABLES

X,1 X,2 X,_ Xz, X2_ Xz3 X_, X32 X33

OONSTRAINTS

e I00 0 0 0 1 0 0 0 1

f 99 1 I01 I01 99 1 1 I01 99

g 99 i01 1 1 99 i01 I01 1 99

The six poesible assignments (denoted by A*,...,A 6) for this

problem are defined below. The decision variables in parentheses are

set to I, and all the other decision variables are set to 0 in order to

obtain the assignments.

114

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

A 1 = ( X,, , X22

AZ = ( X21 , X32

A3 = ( X31 , X;,

A4 = ( X,; , X32

A s : ( X2, , X;s

A s : ( X31 , X22

X33 )

X,3 )

X,3 )

X23 )

X33 )

X,3 )

115

By evaluating each constraint with each possible assignments, we

get the following table. The solution to the master problem with each

assignment is the maximum of all the values in the column corresponding

to that assignment.

ASSIGNMENTS

A I A 2 A 3 A 4 A 5 A e

_4SA"P_%I_ e Iv_no 0 0 ._0 ,A 1 1

CONSTRAINT f 297 303 3 201 201 201

CONSTRAINT g 297 3 303 201 201 201

SOLN. VALUE IN 297 303 303 201 201 201

HASTERH_BLI_

The assignments A 4, A s, and A 0 provide alternate optimal solutions

to the master problem. If A s is to be an optimum solution to the

LaEranEean relaxation of the master problem (Figure i0), then the

solutions provided by all other assignments must not be anybetter than

the solution provided by A s. This condition is represented by the

following set of inequalities, (A.I) to (A.5).

102 L. + 297 Lf + 297 Ll _ L® + 201Lr + 201L. (A.I)
116

0 Le + 303 Lr + 3 Ll _ Le + 201Lr + 201L_ (A.2)

0 Le + 3 Lt + 303 Lg ! Le + 201Lf + 201Lt (A.3)

100 L, + 201Lr + 201Ll _ L, + 201L_ + 201Ll (A.4)

1 L, + 201Lr + 201Lt _ L, + 201Lr + 201Lt (A.5)

( Li = the Lagrangeanmultiplier corresponding to constraint i. )

Adding (A.2) and (A.3), we obtain

0 L, + 306 Lr + 306 Ll _ 2 L, + 402 Lr + 402 L_ (A.6)

The constraints on the LagranEean multipliers in the Lagrangean

relaxation are

L, + Lr + Lt = 1

L, , L, , LI >_ 0

(A.7)

(A.8)

Clearly the system of equations and inequalities denoted by (A.6),(A.7)

and (A.8) is inconsistent. Therefore, there does not exist a set of

Lagrangean multipliers for which the solution to the Lagrangean

relaxation is the same as the optimal solution to the master problem ,

A _. The above exercise can be repeated for the other optimal

assignments A 4 and A 6. For this example, there does not exist a set of

Lagrangean multipliers for which the solution to the Lagrangean

relaxation is an optimal solution to the master problem.

!

I

I

I

I

I

I

I

I

I

I

!

I

I

I

I

I

I

I
I

I

I

!

I

i

I

I

I

I

I

I

I

I

I

I

I

I

APP]_ID)_ B

IDENTIFICATION OF REIX/NDANT /kS VALUES

ONCE THE SATELLITE ORDERING IS SPECIFIED

Once an ordering of the satellites is specified in the satellite

location problem, the resulting problem is a linear proEram. Further, a

larEe number of the minimum required separation values (/_S) become

redundant. The removal of these redundant values from the problem

reduces its size considerably, thereby reducinE the computation time

required to solve the linear proEram. The reduction occurs in the

number of constraints in the primal problems (FiEures 8,12, and 16) and

in the number of variables in the dual problems (FiEures 9,13, and 17).

The method used to identify the redundant /kS values is described in

this appendix.

Define S i as the satellite in position i in the given orderinE.

The minimum required separation between satellites S i and S j is denoted

by /kS ij, and /_M denotes the maximum value amonE all the /kS ij. Let n

be the number of satellites in the problem under consideration.

Consider a satellite S j in position j. The /kS values that are

redundant between Sj and satellites in positions k (k=j+l,...n) need to

be determined.

Define

/kT(j+l) = /kSj,$÷, (S.l)

/kT(k) = max { /kT(h) + /kSia , /kS_k } j+ 1<._h<_k- 1 ;

k=j+Z,...n (B.2)

117
118

By defining /kT(k) as indicated in equations B.I and B.2, the pairwise

separations that are required between all the satellites Sj, Sj+,, ...,

Sk as well as the current ordering of satellites are used in

calculating the minimum separation that will occur between satellites

Sj and Sk in any solution that satisfies the minimum separation

requirements with this ordering. The three conditions for identifying

redundant /kS jk values for the current ordering are the following.

I. If /kSjk = 0 and k_ j+l then /kSjk is rt_lundant since no

minimum separation is required between satellites Sj and Sk. (If k =

j+l, then /kSjk is not redundant since the constraint corresponding to

this j,k pair has to be included in the formulation in order to ensure

that the given ordering is not violated).

2. If /kS_k < /kT(k) then /kSjk is redundant. For the current

ordering, in any solution that satisfies the minimum required

separations for all pairs of satellites between satellite S j and

satellite Sk, satellites S_ and S_ will be separated by at least

/kT(k). Hence /_SJk is redundant.

3. If /kT(k) > /_M then /_Sjh is redundant for h=k+l,...n. By

definition, /_T(h) >_ /kT(k) for h=k+l,...n. Since /_T(h) >_ /kT(k) >

/kM > /kSjh, by the second condition above, /_Sjh is redundant for

h=k+l, ...,n.

The above rules follow from the fact that if the sum of /kS ab and

/kSbc is greater than /kSac, then /kSa© is always enforced when the

satellites are in the order a,b,c. Therefore an explicit constraint on

the minimum required separation between satellites a and c is

unnecessary.

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

119

Application of this procedure prior to solving the linear program

results in a much smaller problem and correspondinEly reduced

computational time in the Benders' subproblem I/rose and also in the

switching technique.
APPENDIXC

ONAVOIDINGTHEREPETITION OF SAT]_LLITE ORDEHINC_

IN A MAJOR ITERATION

The procedure used to restrict any particular satellite ordering

to heine evaluated only once in a major iteration of the switching

heuristic is presented as a theorem in this appendix. The reduction of

the number of evaluations performed in each major iteration with this

procedure is calculated.

Let n = number of satellites and number of orbit positions

k = number of satellites in a subgroup

S(j) = the satellite in position

m = minor iteration

A minor iteration, m, consists of the evaluation of all satellite

orderings resulting from thepermutationof satellites in positions {

m, m+l,...,m+k-i }, the satellites in positions {l,...,m-l} and in

positions {m+k,...,n} remaining in their respective positions. A major

iteration consists of the set of minor iterations {l,2,...,n-k+l}.

Theorem C.l :

If in each minor iteration m (m=2,...,n-k+l), only those satellite

orderines are consideredwhere S(m+k-1) in minor iteration m-I is no__tt

in position m+k-l, then every satellite ordering considered in a major

120

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

I

|,

I

I

I

I

I

I

I

I

I

I

121

iteration is different from all the other orderinEs considered in that

major iteration.

Proof :

Consider a minor iteration m. The satellites S(I) ,..., S(m-l) ,

S(m+k) ,..., S(n) do not switch positions in this minor iteration.

Therefore, in minor iterations I to m for this major iteration, the

same satellite has been in position m+k for all the satellite orderings

examined. Let this satellite be Z. Now consider minor iteration m+1.

The satellites beinE switched in this minor iteration are those in

positions re+l,... ,m+k. Since all satellite orderir_s examined so far

have had Z in position re+k, any satellite ordering that does not have Z

in position m+k has not been evaluated in this major iteration. By

definition, all satellite orderings considered in this minor iteration,

re+l, do not have Z in position m+k. Therefore all satellite orderings

considered in minor iteration m+l are distinct from those considered

previously in this major iteration. Being permutations, they are

distinct among themselves. Extending the argument to all minor

iterations completes the proof.

Theorem C. 2 :

If the procedure indicated in Theorem C.l is used, then only

repetitions of orderings previously evaluated in the major iteration

are eliminated from consideration.

Proof :

Let Z be as defined in the proof for Theorem C.I. In iteration

re+l, the orderings that are eliminated from consideration using the

|
122

procedure of Theorem C. 1 are those with Z in position m+k. The proof

is accomplished by showing that all these orderings that are eliminated

have been previously considered in the current major iteration.

At iteration m+l consider an ordering with Z in position m+k.

Assume it has not been previously examined in this major iteration.

Let this satellite ordering be Q = S(1) ,..., S(m+k-l) , Z , S(m+k+l)

,..., S(n). By definition of the procedure, this ordering must have

been evaluated in minor iteration m, except if S(m+k-l) had been the

last satellite in the subgroup at the beginning of iteration m. A

r_cursion of the arglm_nt for iterations m-l,...,l shows that if Q has

not been considered previously, then some permutations of the

satellites in positions 1,...,k at the start of the major iteration

have not been examined at minor iteration i. This contradicts the

stated procedure which is that at the first minor iteration all

orderings which have permutations of satellites in positions I,... ,k

and other satellites fixed in position must be considered. Therefore

the assumption that Q has not been examined before is false, and the

proof is complete.

Calculation of the reduction in the number of evaluations when Theorem

I

I

I

I

I

I

I

i

I

I

I

i

!

I

C. 1 is implemented.

A. Prior to the implementation of Theorem C. 1

Number of evaluations per minor iteration = k! - 1

Total number of minor iterations = n - k + I

i

i

i

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

Number of evaluations per major iteration = (k!-l){n-k+l}

B. After the implementation of Theorem C. 1

5k_ber of evaluations eliminated per minor iteration : (k-l)!

Number of evaluations per minor iteration : k: - 1 - (k-l)!

N_nber of evaluations in minor iteration 1 = k! - I

Number of evaluations per major iteration

= (k:-l) + ( k: - I - (k-l)!)(n-k)

C. Reduction in the number of evaluations is (k-l)! (n-k)

123
APPENDIX D

THE SEVEN TEST SCENARIOS

The seven test scenarios that are used in the experiments in

Chapters 4 and 5 are described in this appendix. The scenarios were

_generated for service areas which are actual nations and for realistic

situations. The test points that define the service areas were taken

from an atlas, and chosen such that the polygon formed by joining the

test points covered the corresponding service area. The minimum

ellipses were calculated using the computer program developed by Akima

[1981]. The /kS matrices were obtained using the computer program

developed by Wang [1986]. The electrical system characteristics (e.g.,

antenna discrimination patterns, Earth station antenna gains, channel

bandwidth) used in the /kS calculations are those used by Wang for FSS

applications.

For each scenario the names of the countries in the scenario are

given along with a four character code for the name. The desired

location and the limits on the feasible arc for each satellite are

specified. These values are defined in degrees of longitude relative

to a stated longitude so that they are always nora-negative.

The worst case minimum required separation for every pair of

satellites is specified as an element of the /kS matrix. The

separation is given in degrees of longitude. The /kS matrix is

124

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
I

I

i

I

I

I

I

I

I

I

I

I

!

I

I

I

I

I

I

125

symmetric about the diagonal 8nd hence only elements above the diagonal

are stated.
126

SCENARIO 1 : S.AMERICA (13 SAT_.I.TTES - 12 SERVICE AREAS)

S/A NAME CODE DESIRED LOCATION LIMITS ON FEASIBLE ARC

AKIENTINA AEG1 I0.00 5.00 15.00

BOLIVIA BOLl 17.50 12.50 22.50

BRAZIL BRZ1 0.00 0.00 I0.00

CHILE CHL1 25.00 20.00 30.00

O0_IA CI_I 25.00 20.00 30.00

]_IJAIX)R ECDI 30.00 25.00 35. O0

GUYANA (_Y1 7.50 2.50 12.50

PARAfi_/AY PI_I 7.50 2.50 12 . 50

PERU PRUI 27.50 22.50 32.50

SURINAM AND

FRENCH _JIANA SFGI 5.00 0.00 i0.00

URtK?JAY URG1 7.50 2.50 12.50

VENEZUELA VENI 15.00 I0.00 20.00

BRAZIL BRZ2 15.00 I0.00 20.00

Desired locations and feasible arcs are defined relative to 60 ° W. lon.

Note : The service area BRAZIL has two satellites BRZI and BRZ2.

The two service areas SURINAM and FRENCH GUIANA share a

satellite SFGI.

THE /kS MATRIX :

A_I BOLl BP_ZI CHLI CIMI BCDI GUY1 P_I PRUI SFGI URGI VENI BRZ2

AI_l .... 4.33 4.92 4.66 0.54 0.47 0.49 4.41 1.41 0.47 4.55 0.51 4.92

BOLl 4.71 4.39 0.63 0.52 0.48 4.45 4.84 0.46 0.99 0.52 4.71

BRZ1 4.33 5.13 3.14 5.02 4.59 5.29 4.35 4.61 4.24 6.00

CHLI 0.53 0.48 0.48 3.97 4.34 0.44 4.13 0.52 4.33

CIM1 4.19 2.36 0.49 4.46 1.44 0.35 4.91 5.13

/_I)l 0.09 0.00 4.69 0.00 0.00 1.35 3.14

OJYI 0.00 0.51 4.57 0.00 4.72 5.02

PI_I 1.46 0.00 2.46 0.00 4.59

PRUI 0.44 0.45 1.45 5.29

SFGI 0.00 3.86 4.35

UI_I 0.00 4.61

VENI 4.24

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

127

SCENARIO 2 : E.EUROPE (12 SAT',_,T,TTES - 12 S__/ICE AREAS)

S/A NAME CODE DESIRED LOCATION LIMITS ON FEASIBLE ARC

FINLAND FIN1 24 •00 9.O0 39.00

BULGARIA BULl 25. O0 I0.O0 40.00

ROMANIA IK_I 25 .00 10.O0 40.00

GREECE GRC1 27.00 12.00 42.00

ALBANIA ALB1 30.00 15.00 45.00

POLAND POLl 30.00 15 . 00 45.00

HUNGARY HUN1 30.50 15.50 45.50

YIX]_LAVIA YUG1 31.00 16.00 46.00

_LOVAKIA CZH1 33.00 18 . O0 48.00

SWEDEN SWD1 33.00 18.00 48.00

AUSTRIA AtlS1 37.00 22.00 52.00

E._ E_I 38.00 23.00 53.00

Desired locations and feasible arcs are defined relative to 50 ° E.Ion.

THE /kS MATRIX :

FIN1 BULl ROM1 (RCI ALBI POLl HUN1 YUG1 CZHI SWD1 AUS1 EGRI

FIN1 .... 0.00 0.85 0.12 0.00 2.49 0.96 0.35 1.28 4.82 0.92 1.46

BULl 4.62 4.60 4.46 1.96 3.75 4.57 2.71 0.52 3.15 1.91

ROM1 3.38 3.63 3.84 4.60 4.43 4.11 1.25 4.12 3.18

GNC1 4.59 1.23 2.59 4.23 1.52 0.38 2.21 1.21

ALB1 1.29 2.44 4.69 1.53 0.22 2.73 1,26

POLl 4.53 3.47 4.55 3.89 3.92 4.64

HUN1 4.68 4.64 1.74 4.48 3.57

YUG1 4.11 1.19 4.62 3.30

CZH1 2.63 4.60 4.41

SWD1 1.76 3.95

AUS1 4.10
128

SCENARIO 3 : W.EUROPE (12 SATELLITES - 12 SERVICE ARFAS)

S/A NAME CODE DESIRED LOCATION LIMITS ON FEASIBLE ARC

ITALY ITLI 38.00 30.00 48.00

NORWAY NOR1 28.00 28.00 28.00

DENMARK DEN1 40.00 30.00 50.00

W.GERMANY W(]RI 41.00 31.00 51.00

SWITZERIAND SWZI 41.50 31.50 51.50

NTH1 45.00 35.00 55.00

BEfit-OH BLGI 45.50 35.50 55.50

FRANCE FRA1 47.00 37.00 57.00

UNITED KINGDOMUK_I 52.50 42.50 60.00

SPAIN SPN1 55.00 45.00 60.00

IRELAND IRL1 57.50 47.50 60.00

POR1 58.50 48.50 60.00

Desired locations and feasible arcs are defined relative to 50 ° E.lon.

THE ZIS MATRIX :

ITLI NOR1 DEN1 WGRI SWZI NTHI BLGI FRAI UK 1 SPN1 IRLI I_RI

ITL1 0.82 1.46 4.60 4.76 3.58 4.04 4.96 1.96 3.83 1.99 1.31

NOR1 3.86 2.95 0.98 2.15 1.32 1.00 3.05 0.39 0.40 0.00

DEN1 4.77 1.50 4.04 3.30 3.38 3.65 0.94 1.34 0.00

WGR1 4.66 4.64 4.51 4.65 3.77 2.20 2.37 1.19

SWZI 3.13 3.63 4.43 2.85 3.23 2.10 1.91

NTH1 4.46 4.67 4.57 1.84 2.93 1.25

BLG1 4.81 4.14 2.31 3.01 1.45

FRA1 4.38 4.48 3.98 3.03

UK 1 1.42 4.60 1.18

SPN1 1.29 4.45

IRL1 0.86

I

I

I

l

I

I

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

129

SCENARIO 4 : S.E.ASIA (I0 SATELLITES - I0 SERVICE AREAS)

S/A NAME CODE DESIRED I/3CATION LIMITS ON FEASIBLE

PHILIPPINES PHPI 8.00 0.00 23.00

TAIWAN 3WNI 9.00 0.00 24.00

INIX)NESIA IDNI 11.50 0.00 26.50

VIETNAM VIM1 24.00 9.00 30.00

CAMBODIA (_IB1 25.00 10.00 30.00

LAO6 I,AO1 26.00 11.00 30.00

I_tI,AYSIA MLY1 20.00 5.00 30.00

CHINA C'I-_I 25.00 10.00 30.00

THAILAND THL1 28.00 13.00 30.00

BUN_ B_I 30.00 15.00 30.00

Desired locations and feasible arcs are defined relative to 130 ° E.lon.

THE /kS MATRIX :

I:_-IPI TWNI IDNI VI_I QVIBI LAOI MLYI CHNI THLI Bl_l

PHPI

TWNI

IDNI

VTMI

CMBI

LAOI

MLYI

CHNI

THL1

.... 2.21 4.06 1.73 1.70 1.30 4.31 1.99 1.03 0.45

0.36 1.82 0.03 1.05 0.00 3.50 0.94 0.29

3.84 3.50 1.06 4.64 0.64 4.20 3.14

4.59 4.67 3.94 4.17 4.74 4.29

4.59 2.72 1.37 4.58 4.10

0.77 4.11 4.75 4.57

0.52 4.61 1.75

4.07 4.71

4.84

I
130

SCENARIO 5 : N.AFRICA (I0 SATELLITES - I0 SERVICE AREAS)

S/A NAME CODE DESIRED LOCATION LIMITS ON FEASIBLE

LIBYA LBYI 7.50 0. O0 22.50

NIGER NGR1 17.50 2.50 30.00

MALI MALl 29.00 14.00 30. O0

MDRI 30.00 15.00 30.00

MAURITANIA MAUl 30.00 25.00 30.00

SUDAN SUDI 0 •00 0.00 8.00

EGYPT I_fiPl O. O0 O. O0 5. O0

CHAD CHDI 6.00 0.00 21.00

TUNISIA TNSI 15.50 0.50 30.00

ALGERIA AI/]I 23.00 8.00 30.00

Desired locations and feasible arcs are defined relative to 30 ° E.lon.

THE /__S MATRD[ :

LBYI N(]_I MALl I_)RI MAUl SUDI EGPI C"rID1TNSl ALGI

LBYI

NGRI

MALl

IvKRI

MAUl

SUDI

EGP1

CHDI

TNSI

.... 4.71 1.43 1.10 0.55 4.66 4.56 4.67 4.99 4.88

4.93 0.89 2.41 1.57 1.38 4.79 0.67 4.58

4.67 4.88 0.50 0.47 1.56 1.16 4.60

5.04 0.39 0.34 0.42 2.23 5.08

0.46 0.39 0.47 0.94 4.42

4.27 4.81 0.45 0.55

3.50 1.37 1.32

1.21 3.27

4.62

I

I

I

I

I

I

I

I

I

I

I

I

I

I

l

I

I

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

131

SCENARIO 6 : EUROPE (26 SATELLITES - 26 SERVICE AREAS)

S/A NAME CODE DESIRED LOCATION LIMITS ON FEASIBLE ARC

LBSR USRI I0.00 0.00 18.00

FINLAND FIN1 24 •00 9.00 39.00

_IA BULl 25 . 00 10.00 40.00

ROMANIA IK_I 25.00 10.O0 40.00

GREECE (RCl 27 .00 12.00 42.00

ALBANIA ALB1 30 •O0 15. O0 45.00

POLAND POLl 30.00 15.O0 45.00

HUNC,ARY HUN1 30 . 50 15 . 50 45.50

_LAVIA YUG1 31 . 00 16 . 00 46.00

CZECIK_IEVAKIA CZH1 33.00 18.00 48.00

SWEDEN SWD1 33.00 18.00 48.00

AUSTRIA AUS1 37.00 22.00 52.00

E._ E_I 38.00 23.O0 53.00

ITALY ITL1 38.00 30.00 48.00

NORWAY NORI 28.00 28.O0 28.00

DENHARK DEN1 40.00 30. O0 50.00

W._ WGRI 41.00 31.00 51.00

SWITZERLAND SWZI 41.50 31.50 51.50

NEPHERtANDS NTH1 45 . 00 35 . 00 55.00

BELGIt_ BLG1 45 . 50 35.50 55 . 50

FRANCE FRA1 47.00 37.O0 57.00

UNITED KINGDOM UK 1 52 .50 42.50 60.00

SPAIN SPN1 55 . 00 45.00 60.00

IRELAND IRL1 57 •50 47 •50 60.00

PC_I 58.50 48.50 60. O0

ICEIAN ICL1 70 .00 55.O0 75.00

Desired locations and feasible arcs are defined relative to 50° E.lon.

THE /kS MATRIX :

USR1 FIN1 BULl RCIvII(_CI ALBI

ITLI NOR1 DEN1 WGRI SWZI NTH1

POLl HUN1 YUGI CZHI

BLG1 FRAI UK_I SPN1

SWDI AUSI EZRI

IRLI PORI ICLI

USR1 .... 4.50 3.73 4.89 3.04 1.50 4.56 4.92 3.45 4.86 4.43 3.65 3.70

1.37 4.51 3.57 2.91 1.22 1.96 1.32 0.55 0.54 0.48 0.37 0.42 0.00

FIN1 0.00 0.85 0.12 0.00 2.49 0.96 0.35 1.28 4.82 0.92 1.46

0.43 4.39 2.00 1.23 0.00 0.41 0.32 0.45 0.50 0.25 0.00 0.00 0.00

BULl 4.62 4.60 4.46 1.96 3.75 4.57 2.71 0.52 3.15 1.91

3.77 0.00 1.09 2.16 2.10 1.52 1.39 1.21 0.00 0.39 0.00 0.00 0.00

ROHI 3.38 3.63 3.84 4.60 4.43 4.11 1.25 4.12 3.18

3.09 0.53 2.18 3.17 2.16 2.40 2.03 1.34 0.36 0.47 0.00 0.00 0.00

I
132

USRI FINI BULl IK_MI GRCI ALBI POLl HUNI YUGI CZHI SW'DI AUSI EfiRI

ITL1 NOR1 DEN1 WGR1 SWZ1 NTH1 BLG1 FRA1 UK1 SPN1 IRL1 I_R1 ICL1

GRC1 4.59 1.23 2.59 4.23 1.52 0.38 2.21 1.21

3.95 0.12 0.38 1.33 2.32 1.11 1.22 1.27 0.27 0.51 0.00 0.00 0.00

ALB1 1.29 2.44 4.69 1.53 0.22 2.73 1.26

4.67 0.00 0.00 1.98 2.83 1.34 1.56 1.54 0.24 1.06 0.00 0.00 0.00

POLl 4.53 3.47 4.55 3.89 3.92 4.64

3.45 2.28 4.45 4.34 2.92 3.46 2.77 2.99 1.41 1.20 0.45 0.00 0.00

HUN1 4.68 4.64 1.74 4.48 3.57

4.02 0.90 2.34 3.85 2.98 3.07 3.11 2.95 1.09 1.71 0.25 0.00 0.00

YUG1 4.11 1.19 4.62 3.30

4.53 0.52 1.33 4,25 4.19 3.19 3.56 3.55 1.33 0.82 1.02 0.00 0.00

CZH1 2.63 4.60 4.41

4.29 1.33 3.05 4.52 3.73 4.19 3.44 3.75 1.83 1.99 1.04 0.21 0.00

SWDI 1.76 3.95

1.20 4.59 4.61 3.89 1.35 2.18 1.53 1.39 1.64 0.51 0.37 0.17 0.00

AUSI 4. I0

4.86 1.24 2.21 4.72 4.46 3.48 3.65 4.20 2.07 2.66 1.52 0.62 0.00

EfiRI

3.09 2.58 4.65 4.65 3.34 4.46 3.80 4.11 2.73 1,38 1.29 0.82 0.00

ITLI

.... 0.82 1.46 4.60 4.76 3.58 4.04 4.96 1.96 3.83 1.99 1.31 0.27

NOR1

3.86 2.95 0.98 2.15 1.32 1.00 3.05 0.39 0.40 0.00 0.00

DEN1

4.77 1.50 4.04 3.30 3.38 3.65 0.94 1.34 0.00 0.00

WGRI

4.66 4,64 4.51 4.65 3.77 2.20 2.37 1.19 0.19

SWZI

3.13 3.63 4.43 2.85 3.23 2.10 1.91 0.00

NTHI

4.46 4.67 4.57 1.84 2.93 1.25 0.00

BILl1

4.81 4.14 2.31 3.01 1.45 0.00

FRAI

4.38 4.48 3.98 3.03 0.72

U KI

1.42 4.60 1.18 2.97

SPNI

1.29 4.45 0.32

IRLI

0.86 2.05

1:'£_1

0.00

I

I

I

I

I

i

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

133

SCENARIO 7 : NCS AMERICA (26 SATELLITES - 26 SERVICE AREAS)

S/A NAME CODE DESIRED LOCATION LIMITS ON FEASIBLE ARC

USA USA1 46. O0 31 . O0 50. O0

MEXICO HEXI 48. O0 33.00 50.00

CANADA CAN1 50. O0 38. O0 50.00

SURINAM &

FRENCH GUIANA SPGI 4.50 0.00 19.50

CARIBBEAN CRBI 0.00 0 .00 15.00

BRAZIL BRZ1 4.00 0.00 19.00

GUYANA GUY1 9.00 0.00 24 .00

PARAGUAY PRG1 8 .00 0.00 23.00

_AY URG1 5.50 0.00 20.50

ARGENTINA ARG1 13.50 0.00 28.50

VEN1 16.50 1.50 31.50

BOLIVIA BOL 1 13.00 0. O0 28. O0

CHILE CHL1 21.00 6.00 36.00

COLGblBIA CLM1 24.50 9.50 39.50

PERU PRU1 25.00 10. O0 40. O0

ECUADOR ECD1 28.00 13.00 43.00

CUBA CUB1 29.50 14.50 44.50

COSTA RICA CTR1 34. O0 19.00 49.00

NICARA(IIA NCGI 35 •00 20.00 50.00

HONIX]RAS HNDI 36.00 21.00 50.00

BELIZE BLZI 38.50 23.50 50.00

EL SALVAIX_ SLVI 39. O0 24 •00 50.00

GUATI_IALA GTM1 40. O0 25.00 50.00

HAITI HTI I 23.50 8.50 38.50

JAMAICA JMCl 27 •00 12 •00 42.00

PANAMA PbR1 30.00 15 .00 45.00

Desired locations and feasible arcs are defined relative to 50 ° W.lon.

THE /kS MATRIX :

USA1 MEX1 CAN1 SFG1 CRB1 BRZ1 (_JY1 PRG1 URG1 ARG1 V_I BOLl CHL1

CLM1 PRU1 ECD1 CUB1 CTR1 NCG1 HND1 BLZ1 SLV1 GTM1 HTI1 JMC1 PNR1

USA1 4.39 4.77 0.47 4.64 0.65 0.48 0.47 0.42 0.53 0.51 0.51 0.53

0.53 0.53 0.49 3.75 0.43 0.46 0.47 0.98 0.38 0.77 0.43 0.39 0.46

HEXI 0.55 0.43 3.91 0.62 0.47 0.00 0.00 0.00 0.54 0.35 0.43

3.49 0.53 0.49 4.23 1.86 3.79 4.04 4.20 3.88 4.40 2.08 3.32 0.94

CAN1 0.33 0.52 0.59 0.36 0.35 0.30 0.42 0.41 0.41 0.41

0.50 0.44 0.37 0.51 0.32 0.38 0.44 0.38 0.24 0.47 0.44 0.40 0.36
SFG1

CRY1

BRZ1

fiUY1

PRfil

URGI

ARGI

VENI

134

USA1 HEXI CAN1 SFG1 CRB1 BRZ1 GUY1 Pi:_l URG1 ANGI VENI BOLl CHL1

CI_I PRUI I_CDI CUB1 C'I_I NCG1 HND1 BLZ1 SLVl GTH1 HTT1 JHC1 l:NR1

1.07 4.35 4.57 0.00 0.00 0.47 3.86 0.46 0.44

1.44 0.44 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00

1.70 2.71 0.00 0.00 0.49 4.30 0.44 0.52

4.11 0.53 0.46 4.77 1.15 2.96 2.95 2.20 1.07 1.42 4.43 4.57 1.41

5.02 4.59 4.61 4.92 4.24 4.71 4.33

5.13 5.29 3.14 0.48 0.43 0.46 0.47 0.39 0.37 0.46 0.42 0.37 1.06

0.00 0.00 0.49 4.72 0.48 0.48

2.36 0.51 0.09 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00

2.46 4.41 0.00 4.45 3.97

0.49 1.46 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00

4.55 0.00 0.99 4.13

0.35 0.45 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00

0.51 4.33 4.66

0.54 1.41 0.47 0.00 0.37 0.34 0.29 0.00 0.00 0.08 0.00 0.00 0.41

0.52 0.52

4.91 1.45 1.35 0.49 1.86 1.38 0.95 0.37 0.68 0.41 1.07 1.09 3.31

BOLl 4.39

0.63 4.84 0.52 0.00 0.21 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.34

CHL1

0.52 4.41 0.48 0.45 0.41 0.46 0.42 0.36 0.31 0.40 0.41 0.37 0.43

CI_I

PRU1

4.46 4.19 1.52 3.56 4.83 3.60 1.84 2.94 2.45 1.87 2.74 4.45

I_CD1

4.69 0.48 0.43 0.46 0.45 0.39 0.37 0.44 0.40 0.34 0.44

CUB1

0.00 0.42 0.38 0.00 0.00 0.00 0.00 0.00 0.00 0.97

CTR1

0.00 1.27 1.82 2.21 0.95 1.79 4.43 3.56 0.00

NCG1

4.55 2.67 1.25 2.53 2.13 0.00 0.51 4.56

HND1

4.38 3.12 3.79 3.39 1.36 2.28 3.46

BLZ1

4.41 4.50 4.25 1.52 2.33 1.54

SLVl

3.10 4.56 1.14 1.64 0.74

G'I_I

4.70 0.80 1.26 1.42

H'rll

0.85 1.68 1.29

3.90 0.00

0.00

Jl_l

IIIIIIIIIIIIIIIIIII
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

APPENDIX E

THE REGION 2 SC_%_%IO

The introductory paragraphs of Appendix D apply here also, with

the following exception. It has been assumed that, in order to

accomodate 25 U.S.A satellites, the U.S.A. Earth station antenna

diameters have been increased so as to allow 2e satellite separations

of these satellites without exceeding the single-entry interference

threshold. However, the /kS and /k_ calculations involving U.S.A. and

other administrations are made with Wang's parameters, i.e., 4.5 m

(dia.) Earth station antennas with a half power beam width of 1.17

degrees. With respect to interference between the U.S .A. and other

administrations, the calculation is therefore overly conservative.

In the /kS matrix, for service areas with more than one

satellite,the minimum required separation to avoid self interference is

given as the diagonal element of the matrix. _

135
SCENARIO : REGION 2

S/ANAME CODE

USA USA1

MEXICO MEXI

CANADA CAN1

SURINAM &

FRENCH GUIANA SFGI

CARIBBEAN CRB1

BRAZIL BHZI

GUYANA _JY1

PARAGUAY PRG1

URUGUAY URG1

ARGENTINA ARG1

VENEZUEIA VEN1

BOLIVIA BOL 1

CHILE CHLI

CO_IA CIMl

PE_J PRUI

ECUADOR ECDI

CUBA CUB1

COSTA RICA CTRI

NICARAGUA NCGI

HONDURAS HNDI

BELIZE BLZI

EL SALVADOR SLVI

GUATH_AIA GTM1

HAITI HTII

JAMAICA JHCI

PANAMA PNRI

BAHAMAS BAH1

TRINIDAD TRDI

Desired locations

136

(59 SATELLITES - 28 SERVICE AREAS)

# OF DESIRED LIMITS ON FEASIBLE ARC

SATS. LOCATION

25 96.00 62.00 130.00

3 102.00 50.00 154.00

3 103.00 88.00 118.00

2 54.00 0.00 122.00

I 73.00 16.00 130.00

3 55.00 4.00 106.00

1 56.00 0.00 122.00

1 58.00 0.00 122.00

1 56.00 0.00 120.00

1 68.00 14.00 122.00

1 68.00 14.00 122.00

1 62.00 0.00 126.00

1 69.00 14.00 124.00

1 69.00 14.00 124.00

1 74.00 10.00 138.00

1 78.00 10.00 146.00

1 80.00 16.00 144.00

1 84.00 16.00 152.00

1 85.00 18.00 152.00

1 86.00 20.00 152.00

1 89.00 20.00 158.00

1 89.00 20.00 158.00

1 90.00 22.00 158.00

1 73.00 6.00 140.00

1 78.00 10.00 146.00

1 80.00 12.00 148.00

1 76.00 0.00 152.00

1 70.00 0.00 140.00

and feasible arcs are defined relative to 0 •lon.

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
i

I

I

I

I

!

I

I

I

I

I

I

I

I

I

!

I

I

137

THE /__S _LAT21X :

USA1HEXI

CI_IPRUI

BAHITRDI

CAN1 SFGI CRBI BRZI GUY1 PRGI URGI ARG1 VEN1 BOLl CHL1

ECD1 CUB1 CTR1 NCGI HND1 BLZ1 SLVl G'_I HTI1 JHCI P_I

USA1

MEXI

CAN1

SFG1

CRB1

BRZI

(_Yl

PRGI

trill

ARG1

VEN1

2.00 4.39 4.77 0.47 4.64 0.65 0.48 0.47 0.42 0.53 0.51 0.51 0.53

0.53 0.53 0.49 3.75 0.43 0.46 0.47 0.98 0.38 0.77 0.43 0.39 0.46

3.78 0.36

.... 4.13 0.55 0.43 3.91 0.62 0.47 0.00 0.00 0.00 0.54 0.35 0.43

3.49 0.53 0.49 4.23 1.86 3.79 4.04 4.20 3.88 4.40 2.08 3.32 0.,94

4.35 0.36

0.50 0.44

0.40 0.14

1.44 0.44

0.00 1.18

4.11 0.53

4.32 4.90

5.13 5.29

0.37 1.30

2.36 0.51

0.00 2.65

4.17 0.33 0.52 0.59 0.36 0.35 0.30 0.42 0.41 0.41 0.41

0.37 0.51 0.32 0.38 0.44 0.38 0.24 0.47 0.44 0.40 0.36

4.25 1.07 4.35 4.57 0.00 0.00 0.47 3.86 0.46 0.44

0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00

1.70 2.71 0.00 0.00 0.49 4.30 0.44 0.52

0.46 4.77 1.15 2.96 2.95 2.20 1.07 1.42 4.43 4.57 1.41

3.91 5.02 4.59 4.61 4.92 4.24 4.71 4.33

3.14 0.48 0.43 0.46 0.47 0.39 0.37 0.46 0.42 0.37 1.06

0.00 0.00 0.49 4.72 0.48 0.48

0.09 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00

2.46 4.41 0.00 4.45 3.97

0.49 1.46 0.00 0.00 0.00

0.00 0.00

0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00

4.55

0.35 0.45 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00

0.00 0.00

0.00 0.99 4.13

0.00 0.00 0.00

0.51 4.33 4.66

0.54 1.41 0.47 0.00 0.37 0.34 0.29 0.00 0.00 0.08 0.00 0.00 0.41

0.00 0.36

0.52 0.52

4.91 1.45 1.35 0.49 1.86 1.38 0.95 0.37 0.68 0.41 1.07 1.09 3.31

0.53 4.88

4.39

0.63 4.84 0.52 0.00 0.21 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.34

0.00 0.00

0.52 4.41 0.48 0.45 0.41 0.46 0.42 0.36 0.31 0.40 0.41 0.37 0.43

0.20 0.34

.... 4.46 4.19 1.52 3.56 4.83 3.60 1.84 2.94 2.45 1.87 2.74 4.45

0.49 1.41

4.69 0.48 0.43 0.46 0.45 0.39 0.37 0.44 0.40 0.34 0.44

0.32 0.34

BOLl

CHLI

PRUI
ECD1

CUB1

CTRI

NC_I

HND1

BLZ1

SLVI

G'/_I

HTI1

JMC1

PNR1

BAH1

138

USA1 HEXI CAN1 SFGI CRBI BRZI GUY1 PRGI Ul_l AI_I VENI BOLl CHLI

CI.bllPRU1 ECD1 CUB1 CTR1 NCGI HNDI BLZ1 SLV1 GIlql HTII JFEI PNRI

BAH1 TRD1

0.00 0.16

0.00 0.42 0.38 0.00 0.00 0.00 0.00 0.00 0.00 0.97

4.40 0.00

0.00 1.27 1.82 2.21 0.95 1.79 4.43 3.56 0.00

0.31 1.23

4.55 2.67 1.25 2.53 2.13 0.00 0.51 4.56

0.99 0.79

4.38 3.12 3.79 3.39 1.36 2.28 3.46

1.52 0.00

4.41 4.50 4.25 1.52 2.33 1.54

2.87 0.00

3.10 4.56 1.14 1.64 0.74

0.70 0.00

4.70 0.80 1.26 1.42

0.85 1.68 1.29

1.73 0.00

3.90 0.00

3.45 0.00

0.00

2.45 0.00

0.00 2.30

.... 0.00

IIIIIIIIIIIIIIIIII
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

LIST OF REFERENCES

AKIMA, H. [1981]

"A Method for Determining the Minimum Elliptical Beam of a

Satellite Antenna." NTIA Report 81-88, U.S. Department of Commerce.

BAYBARS, I. [1982]

"Optimal Assignment of Broadcasting Frequencies."

Res. 9, pp 257-263.

Eur. J. Opns.

BAZARAA,M.S., and J.J.JARVIS. [1977]

Linear Programmin_ and Network Flows.

York.

John Wiley and Sons, New

BENDERS,J.F. [1962]

"Partitioning ___eures for solving mixed variables proErmmminE

problems." Ntm_er. Math. 4, pp 238-252.

BENICH(NJ,M., J.M.GAUTHIER, G.HENTGES, and G.RIBIERE. [1977]

"The Efficient Solution of Large Scale LP Problems - Some

Algorithmic Techniques and Computational Results." Math. Program. 13,

pp 280-322.

BURKHARD,E., and U.DERIGS. [1980]

"Assignment and Matching Problems - Solutions with FORTRAN

programs." Lecture Notes in Econcmics and Mathematics Series, Springer

VerlaE.

BUYUK[DURA,M, [1986]

Private Communication.

CAMERON,H. [1977]

"The Solution of the Graph Coloring Problem as a Set Covering

Problem." IEEE Trans. Electromagnetic Compatibility 19, No.3.

CASSIDY,P. , and H.BENNEIT. [1972]

"TRAMP - A Multi-depot Vehicle SchedulinE System."

Quart. 23, pp 151-163.

Opnl. Res.

CH(X/INAHD,G. , and M.VACHON. [1981]

"A Synthesis Procedure of a plan by computer using an assignment

method and inductive selection." ITU/CITEL/DOC-Canada, Preparatory

Seminar for 1983 RARC, Ottawa, Canada.

139

I
140

CHRISTENSEN, J. [1981]

"BSS CAPS - A System Description." ITU/CITEL/DOC - Canada,

Preparatory Seminar for 1983 RARC, Ottawa, Canada.

CLARKE,A.C. [1945]

Private document, May" 1945. Reprinted in SpacefliEht Vol.10, No.3,

pp 85-86.

EILON,S., C.WATSON-GANDY, and N.CHRISTOFIDES.

Distribution Management: Mathematical

Analysis. Hafner PublishinE Co., New York.

[1971]

Modelling and Practical

FEDERGRUEN,A., and P.ZIPKIN. [1984]

"ACombinedVehicle Routine and

Opns. Res. 32, No.5, pp 1019-1037.

Inventory Allocation Problem."

FISHER,M.L. [1981]

"The La_rsnEian Relaxation Method for Solvine Integer Programmine

Problems." MEmt. Sci. 27, pp 1-18.

GARFINKEL,R.S., and G.L._USER. [1972]

Integer Progrsmmine. John Wiley & Sons, New York. pp 108-130.

GEOFFRION,A.M., and G.W.GRAVES [1974]

"Multicommodity Distribution System

Deoomposition." MEmt. Sci. 20, pp 822-844.

DesiEn by Benders '

GONSALVEZ,D.J.A. [1983]

"Computational Evaluation of State of the Art Techniques for Mixed

Integer ProEramming." M.8. Thesis, Dept. of Industrial and Systems

EnEineerine, The Ohio State University, Columbus, Ohio, 43210.

HELD,M. , and R.M.KARP. [1971]

"The travelinE salesman problem and mini,u, spannine trees - part

II". Math. Program. I, pp 6-25.

HELD,M., P.WOLFE, and H.P.CROWD_R. [1974]

"Validation of SubEradient Optimization".

62-88.

Math. Program. 6, pp

IGNIZIO,J. [1984]

"A Generalized Goal Programmine Approach

Interference, Multicriteria N * 1Scheduline Problem."

pp 316-322.

to the Minimal

IIE Trans. 16,

ITO,Y., T.MIZUNO, and T.MURATANI. [1979]

"Effective Utilization of Geostationary Orbit through

Optimization." IEEE Trans. on Communications, Vol C0M-27, No. I0, pp

1551-1558.

LASDON,L.S. [1970]

I

I

I

I

I

I

I

I

i

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

141

Optimization Theory for Large Systems. Macmillan Publishing Co.,

Inc. New York.

LEVIS,C.A., C.H.MARTIN, D.J.GONSALVEZ, and C.W.WANG. [1983a]

"Engineering Calculations for Commumications Satellite Systems

Planning." Interim Report 713533-3, The ElectroScience Laboratory, The

Ohio State University, Columbus, Ohio 43212, on Grant No. NAG 3-159 for

NASA/Lewis Research Center, 21000 Broo_k Road, Clevelsr_i, Ohio

44135.

LEVIS,C.A., C.H.MARTIN, C.W.WANG, and D.J.GONSALVEZ. [1983b]

"Engineering Calculations for Communications Satellite Systems

Planning." First Summary Report 713533-2, The ElectroScience

Laboratory, The Ohio State University, Columbus, Ohio 43212, on Grant

No. NAG 3-159 for NASA/Lewis Research Center, 21000 Broo_k Road,

Cleveland, Ohio 44135.

LIN,S. [1965]

"Computer Solutions of the Traveling Salesman Problem."

Systems Technical Journal 44, pp 2245-2269.

Bell

LIN,S., and B.W.KERNIGHAN. [1973]

"An Effective Heuristic Algorithm for the Traveling Salesman

Problem." Opns. Res. 21, pp 498-516.

MARTIN,C.H. [1979]

"PROFOR - A Product Form of the Inverse Implementation of the

Revised Simplex Method for Linear ProgrmmminE." Dept. of Industrial

and Systems EnEineering, The Ohio State University, Columbus, Ohio,

43210.

MARTIN,C.H. and D.J.A.GONSALVEZ [1981]

"ENUMOODE - An Enumeration Code for Mixed Integer Programming."

Dept. of Industrial and Systems EnEineering, The Ohio State University,

Col_nbus, Ohio, 43210.

MATHUR,K., H.M.SALKIN, K.NISHIMURA, and S.MORITO. [1985]

"Applications of Integer Programming in Radio Frequency

Management". MEmt. Sci. V.31, No.7, pp 829-839.

MOUNT-CAMPBELL,C.A., C.H.REILLY, and D.J.GONSALVEZ. [1986]

"A Mixed, 0-I Integer Linear programming Formulation of the FSS

Synthesis Problem using Minimum Required Pair-wise Separations".

Working Paper, Dept. of Industrial and Systems Engineering, The Ohio

State University, Col_nbus, Ohio 43210.

MIZUIKI,T., Y.ITO, and T._K/RATANI. [1984]

"Optimization of Frequency Assignment." presented at the

International Conference on Communications, Amsterdam. May 1984.

NEDZELA,M., and J.SIDNEY. [1981]

!
142

"A Synthesis Algorithm for

ITU/CITEL/DOC-Canada, Preparatory

Canada.

Broadcasting Satellite Service."

Seminar for 1983 RARC, Ottawa,

CRBIT-II. [1984]

"The Orbit Spacing Minimizer - User's Manual."

DenwaCo.,Ltd., Tokyo, Japan.

Kokusai Denshin

_,H.R., T.M.SULLIVAN, and F.S.ZUSMAN. [1986]

"Optimization Techniques Applied to Spectrum Management for

Communications Satellites." A Collection of Technical Papers, AIAA

Eleventh Communication Satellite Systems Conference, San Diego,

California, March 1986, pp 199-210.

POLJAK,B.T. [1967]

"A General Method for Solving Extremt, n Problems".

Doklady, Vol. 8, pp 593-597.

Soviet Math.

EEILLY,C.H., C.A.MOUNT-CAMPBELL, D.J.GONSALVEZ, C.H.MARTIN, C.A.LEVIS,

and C.W.WANG. [1986]

"Broadcasting Satellite Service Synthesis Using Gradient and

Cyclic Coordinate Search Procdeures." A Collection of Technical

Pa_rs, AIAA Eleventh Communication Satellite Systems Conference, San

Diego, California, March 1986, pp 237-245.

REILLY,C.H. [1986b]

Private Communication.

REITER,S., and G.SHERMAN. [1965]

"Discrete Optimizing." J. Soc. Indust. Appl. Math., Vol. 13, No.

3, pp 864-889.

SHAPIRO,J.F. [1979]

"A Survey of Lagrangian Techniques for Discrete Optimization".

Ann. Discrete Math. Vol 5, pp 113-138.

SHERALI,H., and W.ADAM_. [1984]

"A Decomposition Algorithm for a discrete location allocation

problem." Opns. Res. 32, No.4, pp 878-900.

SIMMONS,D.M. [1975]

Nonlinear Programming for Operations

Hall,Inc., Englewood Cliffs, N.J. Chapter 5.

Research. PrenticeS(XJPV. [1983]

Spectrum Orbit Utilization

Silversprings, Maryland.

Program Version 5. ORI Inc.,

WANG,C. [1986]

"Optimization of Orbital Assignment and Specification of Service

Areas in Satellite Communications." Ph.D dissertation. Dept. of

i

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I
I

I

I

I

I

I

I

I

I

I

I

I

1

I

I

I

I

I

143

Electrical Engineering, The Ohio State University, Columbus, Ohio,

43210.

WARCOP,.B-85 [1985]

WARC on the Use of the Geostationary-Satellite Orbit and the

Planning of Space Services Utilizing It. Report to the Second Session

of the Conference. ITU, Geneva, August/September 1985.

WREN,A., and A.HOLLIDAY. [1972]

"Computer Scheduling of Vehicles from One or More Depots to a

Ntmlber of Delivery Points." Opnl. Res. Quart. 23, pp 333-344.

Y_,Y., and C.A.LEVIS. [1985]

"Calculation of allowable orbital spacings for the fixed satellite

service." Technical Report 716548-1, The ElectroScience Laboratory,

The Ohio State University, Columbus, Ohio 43212, on Grant No. NAG 3-

159, for NASA/Lewis Research Center, 21000 Brookpark Road, Cleveland,

Ohio 44135.

ZOF///qER,J.A. [1973]

"Frequency Assignment Games and Strategies."

Electromagnetic Compatibility, Vol. _C-15, pp 191-197.

IEEE Trans. on

ZOELLNER,J.A, and C.L.BEALL. [1977]

"A breakthrough in spectrzn conserving frequency assignment

technology." IEEE Trans. on Electromagnetic Compatibility, Vol. EMC19, pp 313-319.

!