Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Page 8
Page 9
Page 10
Page 11
Page 12

S-94-12

• ?

SIMON FRASER UNIVERSITY

Office of the Vice-President, Academic

MEMORANDUM

To: ?

Senate

From: ?

J.M. Munro, Chair, Senate Committee on Academic Planning

Subject: ?

Institute for Applied Algorithms and Optimization Research

Date: ?

January 18, 1994

At its meeting on January 12, 1994, the Senate Committee on Academic Planning

recommended the establishment of the Institute for Applied Algorithms and

Optimization Research.

Motion:

"That Senate approve and recommend to the Board of Governors the

establishment of the Institute for Applied Algorithms and Optimization

Research and the granting of a Charter to the Institute under the terms of

Policy R.40.01."

A^ VAAJ^o 

ie

SIMON FRASER UNIVERSITY

OFFICE OF THE VICE-PRESIDENT, RESEARCH

MEMORANDUM

To: Alison Watt

From: Bruce P. Clayman

Secretary, Senate Committee

John

M. Munro

on Academic Planning (SCAP)

Re: Institute for Applied Algorithms and Date: ?

January 12 1994

Optimization Research

Attached is a proposal from Dr. Ron Marteniuk, Dean, Faculty of

Applied Sciences, to establish an Institute for Applied Algorithms and

Optimization Research.

• ?

The Governing Committee for Centres and Institutes recommends that

the Institute be granted approval by SCAP. Once approved by SCAP, the

proposal is to be forwarded to Senate, followed by submission to the Board of

Governors.

Governing Committee:

Bruce P. Clayman

Vice-President, Research

(Acting)

JoWn M. Munro

Vice-President, Academic

MEMORANDUM ?

SCAP 94-2

SIMON FRASER UNIVERSITY

FACULTY OF APPLIED SCIENCES

DATE:

December 20, 1993

TO: ?

Bruce Clayman, Vice-President Research, and Jock Munro, Vice-President Academic

University's Governing Committee for Centres

FROM:

Ron Marteniuk, Dean, Faculty of Applied Sciences

R E: ?

Proposal to Establish an Institute for Applied Algorithms and Optimization Research

I am very pleased to submit on behalf of fifteen faculty a proposal for the establishment of an Institute

for Applied Algorithms and Optimization Research. I have read the proposal and am in full support of

it. In essence, I highly recommend it to you for your approval.

Ron Marteniuk, Dean

Faculty of Applied Sciences

RMJ1c

Enclosure

cc: J. Curry, Associate Director, University/Industry Liaison Office

Shapiro, Dean, Faculty of Business Administration

C. Irwin, Dean, Faculty of Science

T. Calvert, Director, Research and Computing, Faculty of Applied Sciences

A. Liestman, Director, School of Computing Science

K. Heinrich, Chair, Department of Mathematics and Statistics

Founding Members:

B. Aispach, Department of Mathematics and Statistics

B. Bhattacharya, School of Computing Science

J. Borwein, Department of Mathematics and Statistics

L. Goddyn, Department of Mathematics and Statistics

A. Gupta, School of Computing Science

L. Hafer, School of Computing Science

K. Heinrich, Department of Mathematics and Statistics

P. Hell, School of Computing Science and Department of Mathematics and Statistics

C. Jones, Faculty of Business Administration

R. Krishnamurti, School of Computing Science

A.L. Liestman, School of Computing Science

E. Love, Faculty of Business Administration

J.G. Peters, School of Computing Science

T.C. Shermer, School of Computing Science

A. Warburton, Faculty of Business Administration

P_j

Simon Fraser University

From:

Faculty of Applied Sciences

School of Computing Science

Please consider the attached proposal for an "Institute for Applied Algorithms and Optimization Re-

search" as a Schedule A Centre under University policy R 40.01. If additional information is required, please

Proposal for an Institute for Applied Algorithms and Optimization Research

Background Information

Much of the basic research within computing science is done by "theorists" who study

algorithms and their complexity as well as the mathematics underlying these algorithms.

Although much of this work is basic science, the results obtained in this area have extremely

important implications to practitioners. Research in theoretical computing science produces

results that are both positive and negative. The positive results point the way to efficient so-

lutions of problems while the negative results indicate that problems are difficult /impossible

to solve efficiently. In spite of the fact that both types of results have significant implications

for industry, these results are largely unknown or misunderstood by practitioners in the field.

A primary goal of this proposal is to foster increased awareness of these results by industrial

practitioners.

The members of the proposed Institute are faculty members from SFU's School of Com-

puting Science, School of Business Administration, and Department of Mathematics and

Statistics. Their research interests span a broad range of topics. The major areas of investi-

gation at this time include optimization, operations research, computational geometry, par-

allel algorithms, distributed algorithms, scheduling, design theory, integer programming, and

graph algorithms. Some of the current projects have application in the areas of scheduling

of industrial processes, geographical information systems, communication networks, robot

motion planning, and VLSI layout.

One particular subgroup, the

Optimization Group,

was recently formed to focus on the

development of algorithms for optimization problems. The interests of this subgroup have

converged on the solution of resource constrained scheduling problems and their applications

to industrial environments. This group

has obtained a fellowship from the B.C. Advanced

Systems Institute to support research in this area. We believe that this indicates that

there is a need for this type of technology transfer in British Columbia. The Institute

of Applied Algorithms and Optimization Research is intended to meet these needs and

to provide British Columbia and Canada with a strong center of research and technology

transfer in this strategically important area.

The Institute is intended to stimulate, encourage, and enhance research and technol-

ogy transfer in the areas of Applied Algorithms and Optimization by providing a focus and

resource base for collaborative and multidisciplinary research. The Institute will be a Sched-

ule A Centre with an Administrative Officer, an elected Director, and an Advisory Board as

discussed in more detail below.

An important objective of the Institute is to expand and promote applied algorithms and

optimization technology through collaboration with others. Institute members work with

other academic researchers and graduate students to create new technology. The Institute

will seek methods to foster two-way communication between Institute members and industry

thereby transferring academic knowledge to industry and bringing practical problems into the

academic realm. Simon Fraser University has expertise in the area of Applied Algorithms and

Optimization that is unique in British Columbia and rare in Canada. This institute should

provide a vehicle for disseminating known results and stimulating new work on relevant

problems.

The Market

The Institute for Applied Algorithms and Optimization Research will fill an important

need for business in British Columbia; our greatest challenge lies in making industry cog-

nizant of that need. Theoretical computer scientists and Applied Mathematicians

work

on the solutions of problems encountered every day in industry. However, as academics, we

tend to work on abstract versions of these problems stated in general terms.

Consider the problems of scheduling a fleet of trucks to service a set of customers dis-

tributed over the lower mainland; designing digital hardware to implement a particular al-

gorithm; scheduling required maintenance for a fleet of airplanes. Superficially, these might

seem very different problems. In fact, they are all resource-constrained scheduling problems,

and algorithms developed for one problem often contain techniques applicable to the others.

The difficulty is in recognizing the resemblance and having the skill to adapt an algorithm

from one domain to the specific requirements of another. It is here that collaboration be-

tween an expert for the specific problem and an expert in algorithm design and application

can be very fruitful.

Consider the problem of balancing the time required for each assembly path in a compli-

cated assembly line. An efficient algorithm to calculate the optimal answer for some cases

can be found in "A Polynomial Algorithm for Balancing Acyclic Data Flow Graphs", in the

November 1992 issue of IEEE Computer, but that isn't immediately apparent from either

the title or the journal in which it appears.

An interface between the theorist and the practitioner is necessary in order to identify

and perhaps translate relevant theories that may help solve the real problem. The Institute,

hopefully, will serve to fill this role. The proposed Institute would be a cooperative effort to

establish where a specific industrial problem fits in the somewhat abstract classification that

orders the world of algorithm design, ana thento identify, modify, or invent algorithms that

can solve the problem. The collaboration enables the problem expert and the algorithms

expert to surmount the barriers of specialist jargon, each providing the skill required to

interpret their discipline to the other.

Within the Optimization group, we have focussed on solutions to resource-constrained

scheduling problems that use both exact and heuristic algorithms to provide efficiency and

flexibility. Exact algorithms provide optimal or near-optimal answers for the purpose of

planning, where a running time of a few hours to as much as a few days is acceptable to

3 ?

obtain an answer that makes the best use of available resources. Heuristic algorithms can

provide reasonably good answers quickly, so that the optimal answer can be adapted to

the inevitable but unpredictable events that were not included in the ideal plan (such as

machinery breakdown or employee illness).

4 ?

Objectives of the Institute

Consistent with the goals and objectives of Simon Fraser University, the particular ob-

jectives of the Institute are as follows:

To stimulate, encourage, and enhance applied algorithms and optimization research and

development, by providing a focus and resource base for such collaborative research.

To encourage research collaborations within the Institute and with other researchers

across Canada and around the world.

To promote the development of highly trained personnel with expertise in applied

algorithms and optimization through the undergraduate and graduate programs of the

participating units and through student involvement with Institute projects.

To promote the dissemination of knowledge in the broader community through short

courses and seminars in cooperation with Continuing Education and through the pro-

vision of consulting services.

To provide an appropriate computing environment for pursuing research and technol-

ogy transfer in this area.

To provide a vehicle for technology transfer from the university-based researchers of

the Institute to industry.

To provide mechanisms for industrial problems to be communicated to the researchers

of the Institute.

To foster closer ties with industry.

Organizational Structure of the Institute

The Institute will be a Schedule A Centre as described in R 40.01.

Administrative Officer

The Administrative Officer will be the Dean of Applied Sciences.

Director

The Director of the Institute will be a member of the Institute and an employee

of Simon Fraser University. Each candidate for the position of Director must be nominated

F -

by a member of the Institute. Following an election, the successful candidate's name is then

recommended to the Dean of Applied Sciences for appointment.

The term of the Director will be for three years, renewable.

The Director approves all contracts to be undertaken in the name of the Institute, in

conjunction with the Administrative Officer.

The Director shall submit an annual report on all Institute activities, and a financial

statement showing all revenues and expenditures; for the twelve months ending March 31 of

each year, no later than June 30 of each year.

The Director will call meetings of the membership to discuss policy and direction of the

Institute and any other concerns of general import. Such meetings will be called at least

twice a year.

The Director will call meetings of the Advisory Board periodically.

Membership:

Membership shall be by application to the Director, and a two-thirds ma-

jority vote of the membership, subject to appeal (for Simon Fraser University personnel only)

to the Administrative Officer, whose decision shall be final.

•

Candidates for membership should have been involved in ongoing active collaboration?

with Institute members prior to application for membership.

Membership shall be for a three year term, renewable at the discretion of the Director.

Any member may withdraw from the Institute by delivering a written letter of resignation

to the Director of the Institute.

Associate Membership:

Associate membership shall be by application to the Director,

and a simple majority vote of the membership.

Candidates for associate membership should have been involved in ongoing active collab-

oration-with Institute members prior to-application for associate membership.

Associate membership shall be for a three year term, renewable at the discretion of the

Director.

Any associate member may withdraw from the Institute by delivering a written letter of

resignation to the Director of the Institute.

Advisory Board:

An Advisory Board representing a cross section of academic and industry

5 ?

personnel plus representation from the university administration and government, will be

6 ?

assembled to provide guidance to the Institute.

The primary task of the Advisory Board is to help the Institute evolve to best serve the

changing needs of the academic and industrial communities.

All Advisory Board meetings are open, and Institute members are encouraged to attend.

Advisory Board membership shall consist of the Administrative Officer, the Director of

the Institute, two corporate members, two external researchers, and such others as may be

deemed capable of making an exceptional contribution to the activities of the Board.

Invitations for membership are issued at the sole discretion of the Director of the Institute,

except for the Administrative Officer and the Director.

Membership is for a three (3) year renewable term, except for the designated personnel.

The Advisory Board bears no legal responsibility for the actions of the Institute, and

exercises no direct control over the actions of the Director, Institute members, or staff.

Institute Membership

The initial members of the Institute are listed below:

Department of Mathematics and Statistics

School of Computing Science

Department of Mathematics and Statistics

School of Computing Science

Department of Mathematics and Statistics

School of Computing Science and

Department of Mathematics and Statistics

School of Business Administration

School of Computing Science

School of Rusiness Administration

School of Computing Science

School of Business Administration

Institute Affiliations

Since collaboration is a primary goal of the Institute, affiliations with other institutions

will be sought, where such affiliation brings contact with exceptional research. This partic-

ularly holds true outside North America, where frequent casual contact is less likely.

ID -

Budget of the Institute

The Institute requires an initial budget only for publicity costs, since research activities

utilize existing facilities, personnel, and funding. However, as the Institute grows, several

objectives require funding over and above existing levels. These include exchange of per-

sonnel with other institutions, possible establishment of a research chair for the Director,

maintenance of equipment, and purchase of new capital equipment.

Start-up funding from the Faculty of Applied Sciences will be sought to cover the initial

costs associated with organizing the Institute. All subsequent funding for the Institute, which

is incremental to existing levels of support, should come from sources outside Simon Fraser

University, excepting the normal internal applications for funding to which all personnel,

groups of personnel, and institutes are entitled to apply.

/1.