Xref: utzoo ont.events:1422 uw.talks:113 uw.cs.grad:100
Path: utzoo!utgpu!watserv1!watcgl!rmvale
From: rmvale@watcgl.waterloo.edu (Ruth Vale)
Newsgroups: ont.events,uw.talks,uw.cs.grad
Subject: ICR Colloquium
Keywords: interior point algorithm polynomial time
Message-ID: <12869@watcgl.waterloo.edu>
Date: 8 Jan 90 15:45:35 GMT
Distribution: ont
Organization: U of Waterloo, Ontario
Lines: 38

ICR Colloquium

Practical Applications of Interior Point Algorithms

Dr. Anthony Vannelli
Department of Electrical & Computer Engineering
University of Waterloo

Wednesday, January 10, 1990 at 3:30 p.m.

Davis Centre 1302

Abstract

Since the introduction of Narendra Karmarkar's polynomial time
algorithm for solving linear programming problems in 1984, research 
in the mathematical optimization community has developed interior
point variants to solve quadratic programming and combinatorial
optimization problems.  In this talk we outline our own research
efforts to use an interior point algorithm to solve engineering-
related optimization problems that arise in such diverse areas as
water resource management, oil refinery multi-period planning
problems and VLSI circuit layout problems.  Our research on using
a dual affine scaling interior point algorithm has led to promising
resultsi in the outlined engineering areas.

A developed and flexible algorithm is described for solving these
large scale optimization problems.  In particular the effective management 
of the key projection step which is the bottleneck step in any interior
point code is described.  We indicate how to exploit the structure
of the underlying engineering design problem to minimize the
difficulties caused by the projection step.  Numerical results
are described which show that our interior point algorithm is 5-20 times
faster than the SIMPLEX code (MINOS) for solving these problems. 
Moreover, the algorithm becomes faster than the Simplex algorithm as
the problem size increases.

Everyone is welcome.  Refreshments served.