\documentclass[12pt]{article}
\usepackage{graphicx,latexsym,color}

\textwidth=6.5in \textheight=8.5in \oddsidemargin=0in
\evensidemargin=\oddsidemargin \topmargin=0in

\newcommand{\question}[1]{\medskip \noindent {\bf \color{blue} #1} \medskip}
\newcommand{\category}[1]{\noindent {\bf \color{black} #1}}
\newcommand{\IPM}{\category{Interior Point Methods:  }}
\newcommand{\SDO}{\category{Semi-definite Optimization:  }}
\newcommand{\Fast}{\category{Fast Approximation Algorithms:  }}
\newcommand{\VLSI}{\category{VLSI Circuit Design:  }}
\newcommand{\Power}{\category{Power Market Management:  }}
\newcommand{\DC}{\category{Digital Communications:  }}
\newcommand{\DM}{\category{Data Mining:  }}

\newenvironment{tightenumerate}{\begin{list}{--~}{
  \topsep=0.3ex \itemsep=0.3ex \labelsep=1em \parsep=0em
  \listparindent=0em \itemindent=0em
  \settowidth{\labelwidth}{--~} \leftmargin=3.5em
}}{\end{list}}

\begin{document}
\pagestyle{myheadings} \markboth{T. Terlaky - H.P.O. and App.: 
Titles and Non-Academic Partners}{T.  Terlaky - HPO and App.: 
Titles and Non-Academic Partners}

\title{High Performance Optimization: \\ Theory, Algorithm Design 
and Engineering Applications} \maketitle

\section{Title and Website}

\noindent {\bf Project Title:} High Performance Optimization:
Theory, Algorithm Design and Engineering Applications

\noindent {\bf Short Title:} HPO and App. \medskip

\noindent {\bf Project Website:}  {\tt 
http://orion.math.uwaterloo.ca/$\sim$hwolkowi/henry/ \\ $\mbox{}$
\hspace{47mm} reports/mitacs.d/project\underline{~}website/}


\section{Non-Academic Partners}

\noindent{\bf Organization Name:} Bell Canada

\noindent{\bf Primary Contact:} Anwar Haque

\noindent{\bf Mailing Address:} 110 King St. West F2, Hamilton, 
ON, L8P 4S6

\noindent{\bf Phone Number:} 905-977-5629

\noindent{\bf Fax Number:} NA

\noindent{\bf E-mail Address:} anwar.haque@bell.ca

\noindent{\bf Web Page:} {\tt 
http://www.bce.ca/en/community/innovation/universityresearch }

\bigskip

\noindent{\bf Organization Name:} IBM T.J. Watson Research Centre

\noindent{\bf Primary Contact:} Dr. Andrew Conn

\noindent{\bf Mailing Address:} P.O. Box 218, Yorktown Heights, 
NY 10598, USA

\noindent{\bf Phone Number:} 914-945-1589

\noindent{\bf Fax Number:}  914-945-3434

\noindent{\bf E-mail Address:} arconn@watson.ibm.com 
 
\noindent{\bf Web Page:} {\tt http://www.ibm.com/us/}

\newpage
\pagestyle{myheadings} \markboth{T. Terlaky - H.P.O. and App.: 
Science}{T.  Terlaky - HPO and App.: Science}
\section{Science (maximum 10 pages)}

The major goal of this project is to advance the theory and 
implementation of Optimization Algorithms, while exploring and 
improving applications in Engineering and Design. \medskip

\question{a) Summary of the state of knowledge in the field}

In 1984, an influential paper by Karmarkar sparked the ``interior 
point revolution.''  Since then the fields of interior point 
methods ({\bf IPM}s) and semi-definite optimization ({\bf SDO}) 
have matured in both theory and practice, allowing for the rapid 
computation of solutions to problems which were previously 
considered unapproachable.

In the last decade it was generally believed that Nesterov and 
Nemirovski's seminal work on self-concordant functions was the 
bedrock of all polynomial IPMs, and there was little hope in 
improving complexity results that favor small-update methods. 
Small-update methods decrease the barrier parameter very slowly, 
resulting in a theoretical complexity of  $O(\sqrt{n} \log 
\frac{n}{\epsilon})$ Newton iteration.  Unfortunately, in 
practice these methods are too slow to be of much value. 
Conversely, large-update methods (which decrease the barrier 
parameter quickly) have the poor theoretical complexity of 
$O({n}\log\frac{n}{\epsilon})$ Newton iterations, but converge 
rapidly in practice.

Recently, Peng, Roos and Terlaky \cite{PRT00c} introduced a new 
class of search directions and improved the complexity of 
large-update IPMs.  This new paradigm of IPMs is based on the 
concept of self-regular functions.  The complexity of 
large-update large-neighborhood IPMs was brought down to 
$O(\sqrt{n} \log{n} \log \frac{n}{\epsilon})$ Newton iterations, 
for a particular choice of parameters. This significantly narrows 
the gap between the theory and practice of IPMs. An excellent 
overview on this new paradigm of self regularity, and its use in 
developing primal dual interior point methods for LO and SDO can 
be found in the monograph \cite{PRT02-book}.

\medskip

A broad and powerful class of problems for which IPMs work, is 
studied in the field of semi-definite optimization.  This field's 
appeal is that it encompasses not only classical linear and 
quadratic programs, but also many problems that cannot be 
formulated in these manners (such as the maximum eigenvalue 
problem).  Although the theory of optimality for SDO has been 
established some years ago (see for example the book by 
Wolkowicz, Vandenberghe and Saigal \cite{SVW-book}), important 
theory continues to flourish in the field.  In the past decade, 
research on robust optimization has shown that a robust quadratic 
program can be structured as a semi-definite program.  
Influential papers by BenTal and Nemirovski are amoung the 
forefront of this research.

Algorithmically, there are several successful SDO packages freely 
available online.  One such program is SeDuMi, which has recently 
been taken over by a strong research group at McMaster 
University.  These packages have resulted in a vast increase in 
the size of SDO problems which can currently be solved.

\medskip

Despite the recent improvements in IPMs and SDO, there is still a 
large collection of problems for which the many efficient 
algorithms for mathematical programming are inappropriate.  For 
example, many combinatorial optimization problems (such as 
``packing'' and ``covering'' problems) can be formulated as 
mathematical programs.  When converting these problems to 
mathematical programs, the number of variables grows 
exponentially in the input size of the problem.  Thus even 
efficient exact solution algorithms will stall.  As a result the 
question of designing fast algorithms for computing ``near 
optimal'' solutions has arisen.   For such algorithms, the 
resulting near optimal solution should be provably close to 
optimum, and the algorithm must complete within polynomial time 
in the problem size and accuracy tolerance.  Such algorithms are 
called Fast Approximation Algorithms ({\bf FAA}s).  The worst 
case ratio of the near optimal value to the real optimal value is 
called the approximation ratio.

Published works in this field started appearing in the early 
1990s, and the first book on the subject was published by 
Bienstock in 2002.  As FAAs are such a new field of research, new 
application and new FAA are constantly being discovered, and 
previously developed FAAs are rapidly being refined.  For example 
in \cite{STVZ05a}, the first FAA which solves the generalized 
fractional packing problem with only approximate block solvers 
and a coordination complexity that is polynomial in the input size
was published.  The paper also presents an FAA for the integer 
packing problem, with a better complexity than that of previous 
FAAs for this problem.  

\medskip

The new revolutions in IPMs, SDO, and FAAs are making a huge 
impact on many areas of engineering and design.  This project 
proposes to focus on four such areas: Very Large Scale 
Integration, Data Mining, Digital Communication, and Power Market 
Management.

\medskip


The problem of Very Large Scale Integration ({\bf VLSI}) chip 
design, is a prime example of a problem where traditional exact 
solution algorithms are becoming impractical.  As modern 
integrated circuits increase in size, complexity and 
functionality, the combinatorial optimization problems of 
partitioning the chip into modules, placement of the modules, and 
routing wires to the modules are becoming increasingly complex.  
Due to the explosive growth in the technology for manufacturing 
integrated circuits,  modern chips contain millions of 
transistors.  In the past, techniques such as simulated 
annealing, tabu search, and interior-point-based heuristics have 
been used to solve the aforementioned problems, but they are 
often computationally expensive and tend to become trapped in 
local minima.

Recently, semi-definite relaxation techniques and FAAs have been 
employed to solve the VLSI problem.  In \cite{Wol04} the 
semi-definite relaxation approach to chip design is explored, 
while in \cite{TVZ05} the first FAA for minimizing total wire 
length and number of vias is given.

The next step in the VLSI is to consider multi-layer chip design. 
The beginning of systematic research on this topic via 
mathematical programming can be found in \cite{STVZ05b}.

\medskip 

Data Mining is a newly emerging multidisciplinary field that 
interacts with mathematical programming, statistics and computer 
science.  Two of the major tasks in data mining, data 
classification and data clustering, can both be viewed as 
optimization problems.  The process of constructing a classifier 
from a training data set can be interpreted as minimizing the 
total misclassification errors in the training data set, while 
the data clustering, whenever a similarity measurement is fixed, 
is often cast as a global optimization problem.  

Through an elegant combination of the theory and tools of 
mathematical optimization the highly successful support vector 
machines were developed (see the 2000 book by Christianini and 
Shawe-Taylor for example).  These have been recognized as one of 
the most efficient approaches for solving data classification 
problems, and have opened up several new challenges in the 
scenario of multi-class classification.  

In contrast, until recently has there been very few 
optimization-based approaches for the clustering problem. One of 
the difficulties in developing optimization methods for 
clustering is that the optimization problem derived from 
clustering is typically highly nonlinear and nonconvex with 
discrete constraints.   Recently, it has been observed that many 
variants of clustering problems can be embedded into a unified 
framework, called ``0-1 semi-definite programming'' 
\cite{Peng05}.  This new framework allows the use of SDO theory 
and tools, which in turn is rapidly opening up new avenues for 
cluster analysis.
  
\medskip 

New techniques resulting from large communication demands have 
resulted in the development of several new problems in digital 
communications.  One example is multicasting, where several users 
connected to the same source for simultaneous transmission of the 
same data packets, gives rise to a large scale optimization 
problem when many groups of users and sources coexist in a large 
scale communication network with bounded network resource.  
Another example is the creation of ad-hoc wireless networks, 
where multi-hop transmissions are used to transmit data, leads to 
the problem of minimizing energy expenditure while maintain 
signal quality.

Most previous results for the multicasting problem have focused 
on the case of a single user group with a single source, but 
recently researchers have begun the study of the multicasting 
problem under the assumption of multiple user groups.   In 
\cite{TVZ05}, the first FAA results for minimizing the total cost 
were published.  In \cite{LZ05} an FAA for minimizing the maximum 
edge congestion was tested in realistic simulations.  A second 
approach (and FAA) for multiple group multicasting was developed 
in \cite{STVZ05a}.

Another recent result in digital communications is the 
development of a new FAA for ad-hoc wireless networks which 
reaches the theoretical lower bound for the range assignment 
problem \cite{CYZ05}.  

\medskip

The deregulation and privatization of electricity markets to make 
them more competitive, has led to the need for new analysis and 
operating tools that properly dispatch supply and demand powers 
at optimal prices while guaranteeing adequate system security 
levels.

The system operator plans on amounts of generation from each 
generator by solving a constrained linear program that minimizes 
the cost of meeting demand, subject to constraints that include 
stability of the overall power network.  Data for the linear 
program include offer prices and quantities from the generating 
companies, a forecast of energy demand, and a technical 
description of the transmission network.  The constraints also 
include a linear approximation of the nonlinear equations that 
describe the physical flow of power in the transmission network.  
Replacement of the approximation by the accurate nonlinear 
expressions would improve decision making, but solution times 
would be too slow for practical implementation.  Recent advances 
in algorithms for solving linear and nonlinear programs, along 
with new modelling techniques which demand a greater stability in 
the resulting solution are beginning to show a profound 
effect on how power market management can be performed.

\medskip

In order to make the remainder of this project proposal easier to 
read, we shall subdivide the remaining sections into the 
categories: {\it Interior Point Methods, Semi-definite 
Optimization, Fast Approximation Algorithms, Very Large Scale 
Integration, Power Market Management, Data Mining,} and {\it 
Digital Communication.}

\question{b) Summary of project's main achievements since last 
Project CV}

\IPM In the last few years we continued to explore the new 
opportunities offered by the new paradigm of self-regular 
proximity functions.  We made notable advances in various areas:
\begin{tightenumerate}
\item[Self-regular Infeasible Interior Point Methods:] The use of 
specific self-regular functions improved the worst case 
complexity of infeasible IPMs.  Theoretical and computational 
results were presented.  \cite{STZ02} \cite{SPT05}

\item[Novel predictor-corrector IPMs:]  Novel variant of 
predictor-corrector IMPs were developed and analyzed.  These are
providing a better understanding of current practical variants.  
New strategies and safe-guards were introduced in Mehrotra's 
algorithms, resulting in theoretical asymptotic superlinear and 
quadratic convergence of the new IPMs as well as some encouraging 
numerical results. \cite{SPT05}

\item[Limitations of path-following IPMs:] A class of examples 
was constructed to show that the central path can be bent along 
the edges of the Klee-Minty cube such that it visits an 
arbitrarily small neighborhood of all the vertices of the cube in 
the same order the simplex method does. This shows that the worst 
case complexity of central path following interior point methods 
cannot be improved further. \cite{DNPT04} \cite{DNT04}

\item[IPMs based sensitivity analysis:] IPMs forced us to rethink 
the basic questions and tools of sensitivity and parametric 
analysis. The concepts of optimal partition, strictly and 
maximally complementary solutions allowed us to define new 
sensitivity intervals based on invariant support and constraint 
sets \cite{GHMT05a} \cite{GHMT05b} and generalize some of the 
results for quadratic optimization \cite{GHRT05}. 

\item[Software and Computational Testing:] McIPM software 
development progressed in the creation of both feasible 
self-regular-IPM software \cite{PTZZ04} and infeasible IPM 
software \cite{PTZZ05}.

\item[Preprocessing:] Sophisticated sampling techniques and 
set-covering paradigm have been used to develop theory for 
producing minimal representations of the feasible region. Testing 
has begun on convex quadratic constraints and SPO.
\end{tightenumerate}

\SDO In the last few years we made notable advances in the 
following areas:
\begin{tightenumerate}
\item[The S-Lemma:] The S-Lemma (or S-procedure) is a fundamental 
tool in control theory. The comprehensive survey paper 
\cite{PT04}, not only surveys the various facets of the S-Lemma 
with respect to control theory and SDO relaxations, but also 
developed many new connections between various areas of 
mathematics and statistics.

\item[Algorithmic Robustness:] One major difficulty of SDO 
algorithms is that the implementations suffer from roundoff error 
due to instability of the search directions.  Studying this 
yielded new theoretical results and more robust versions of SDO 
algorithms. \cite{GLWW04} \cite{RSW02} \cite{TW05} \cite{Wol04}

\item[Applications:]  MRI pulse design was modelled in a 
nonlinear SDO setting, allowing for the application of a custom 
designed sequential SDO algorithm.  Encouraging computational 
results were found.  \cite{ASTZ04} \cite{ATW02} \\ Euclidean 
distance matrices were used to solve problems in molecular 
conformation and protein folding.  \cite{aLW05} 
    
\item[SDO Software and Developement:]In 2004 the AdvOL group at 
McMaster took over the development of the celebrated SeDuMi 
package. Since then notable performance improvements (ten times 
faster on many problems) have been achieved.  Furthermore, a 
parallel version on shared memory machines has been developed.  
This software is used by hundreds of academic researchers 
worldwide and the web-site, http://sedumi.mcmaster.ca, has 
attracted over 60000 visitors.
\end{tightenumerate}

\Fast  This exciting new line of research has recently been added 
to our project.  Nonetheless, we have already made significant 
contributions to:
\begin{tightenumerate}
\item[Packing Problems:]  New FAAs for fractional and integer 
packing problems were developed. \cite{STVZ05a}

\item[Routing Problems:]  A new FAA for multicast networks was 
developed. \cite{TVZ05} \\ Two new FAAs for VLSI routing problems 
were developed. \cite{STVZ05b} \cite{TVZ05} \\  An FAA for 
minimizing maximum edge congestion was implemented and tested. 
\cite{LZ05}
\end{tightenumerate}  

\VLSI In the last few years we created improvements modelling 
technique which have allowed the application of several new 
algorithms for solving VLSI problems.  Improvements in IPMs and 
new FAAs have allowed us to solve large routing and placement 
problem that occur in VLSI design.
\begin{tightenumerate}
\item[Improved Modelling Techniques:]   A new convex optimization 
model for module placement showed significant improvement over 
previously used techniques.  The model forces modules away from 
each other, thereby reducing module overlap.  Test results beat 
the best previously known procedures by three to eight percent. 
\cite{KVV04} \cite{AV05}

\item[New Algorithms:] Two new FAAs for the wire routing 
subproblem were developed. \cite{STVZ05b} \cite{TVZ05}

\item[Improved Theory:]  New lower bounds for some module 
placement problems were developed.  Both row placement chips and 
fixed-outline system-on-chip placement problems were considered. 
These lower bounds provide new measures of how far from 
optimality computed placements lie. \cite{AKV05} \cite{ATV05}
\end{tightenumerate}

\Power Power market management is a newly added line of research 
for this proposal, so the group itself has no documented 
contributions to the area.  However, three new members that are 
joining our research team (Ca{\~n}izares, Fuller, and 
Bhattacharya) have well established research careers in power 
market management (see for example \cite{BBD-book} \cite{Ful05} 
\cite{WF05} \cite{AB05} \cite{MCI05} \cite{Can-book}).   In the 
past few months, several meetings with Ca{\~n}izares, Fuller, and 
Bhattacharya have begun to show that the algorithms and 
techniques used in VLSI could be adapted to solve the models that 
arise in power markets.  

\DM  In the past few years we have studied the connections 
between Data Mining and SDO as well as developed several new 
algorithms for classical Data Mining Problems.
\begin{tightenumerate}
\item[Developed Connections to SDO:]  Established the equivalence 
of K-means clustering and 0-1 semi-definite programming.  This 
provides a unified framework for many clustering problems and 
opens new avenues for cluster analysis. For example, the 0-1 
semi-definite program can be relaxed to linear programming, for 
which there exist polynomial time algorithms.  \cite{PX05b}

\item[New Algorithms:] Investigated the theoretical properties of 
the continuous optimization model for the classical K-means 
clustering and proposed a cutting plane method for solving the 
underlying problem.  \cite{PX05a} \\
Developed 2-approximation algorithms for K-means clustering, 
balanced clustering and normalized-cut clustering. For the 
special case of bi-clustering (which is still NP-hard), our 
algorithm has the best-known complexity of $O(n \log n)$. 
\cite{Peng05} \cite{PW05}
\end{tightenumerate}

\DC Studying multicast networks and ad-hoc wireless networks has 
lead to the development and testing of several FAAs:
\begin{tightenumerate}
\item[Multicast Networks:]  An FAA for minimizing total cost of 
the routing tress was developed.  Worst case approximation ratios 
were calculated and proven, which marks the first result of this 
kind in multicast networks. \cite{TVZ05}  \\ A second FAA for 
maximizing the weighted sum of successfully routed users was 
given. \cite{STVZ05a}

\item[Ad-hoc Wireless Networks:] The range assignment problem was 
studied.  An FAA was developed whose approximation ratio equals 
the theoretical best approximation ratio for the problem.  
\cite{CYZ05}
\end{tightenumerate}

\question{c) Statement of project objectives} 

The overall objective of this research is to advance the theory, 
algorithms and applications of High Performance Optimization 
algorithms in order to solve large-scale problems arising in 
engineering applications.  To accomplish these objectives the 
project will focus on IPMs, SDO, FAAs, and their applications to 
VLSI, power market management, data mining, and digital 
communications.  Through fundamental theory, algorithm 
development, and modelling of engineering problems we are 
determined to pursue our research towards the development of 
highly efficient software tools not only for our own benefit, but 
for the benefit of the entire optimization community.

Some specific research objectives for each category follow.

\IPM \begin{tightenumerate} 
 \item Develop new feasible and infeasible IPMs.
\item Generalize the latest IPMs to second order conic 
optimization and SDO.
 \item Develop high performance IPM software making use of new 
 preprocessing methods.
\item Test and benchmark this software.
 \item Make McIPM freely available online.
\end{tightenumerate}

\SDO\begin{tightenumerate} 
 \item Extend the robust algorithm for linear programming 
 (\cite{GLWW04}) to SDO (both in theory and application).
 \item Implement and test the extended algorithm, with emphasis on 
 robustness.
 \item Apply Euclidean distance matrices to solve molecular 
 conformation problems and more generalized sensor detection problems.
\end{tightenumerate}

\Fast\begin{tightenumerate}
 \item Study FAAs for more structured mathematical programs.
\item Improve previously designed FAA's time complexity, as well 
as design new FAAs.
 \item Implement and test novel FAAs.
\end{tightenumerate}

\VLSI\begin{tightenumerate}
 \item Study VLSI circuit design problems that arise in multi-layer chip design.
\item Develop better models for routing in VLSI circuits.
 \item Advance graph, hypergraph and netlist partitioning 
 techniques.
\item Implement and test global VLSI circuit design software.
\end{tightenumerate}

\Power\begin{tightenumerate}
 \item Examine how recent advances in variational inequality 
 problems may be applicable to power markets.
\item Develop a likely structure of a reactive power market and 
payoff mechanism.
 \item Create methodologies to circumvent possible market power 
 problems arising from participants ``gaming the market'' based on the 
 system operating conditions.
\item Continue the development of methodologies and analysis 
tools based on creating more stable power output supply.
 \item Test these methodologies on realistic systems and compare 
 them to the dispatch and market clearing techniques 
 currently in use.
\end{tightenumerate}

\DM\begin{tightenumerate} 
 \item Develop novel optimization models for classical clustering 
problems and design new efficient approximation algorithms for 
the new models. 
 \item  Develop novel models and techniques to deal with various 
constrained clustering problems to incorporate prior knowledge.
 \item Develop new models and techniques 
based on robust optimization for target tracking problems, noisy 
data problems and multi-class classification problems. 
\end{tightenumerate}

\DC\begin{tightenumerate} 
 \item Develop better models for the routing problem in multicast 
communication networks. 
 \item Improve the theory behind ad-hoc wireless networks.
\item Implement and test new algorithms to design more efficient 
heuristics. 
 \item Create effective software packages.
\end{tightenumerate}


\question{d) Methodology}

The study of high performance optimization and its applications 
will require people with strong backgrounds in a variety of 
mathematical, computer science and engineering disciplines.  It 
will require these people to take particular care in developing 
clear and correct proofs of new theory and algorithms.  New 
algorithms must be implemented and tested on real engineering 
problems.  These engineering problems must be modelled carefully 
to insure accurate conclusions.

\IPM  A strong background in Linear Algebra, Numerical Analysis, 
and Linear Programming are key to this area.  Future focus will 
examine how to reduce the effort required in calculating the 
Newton steps in IPMs, how to deal with round-off errors 
appropriately, and how preprocessing can aid in IPMs.

\SDO  A strong background in Variational Analysis, Duality Theory 
and Conic Programming will be used for this research.  When 
creating new theory and software, special attention will be paid 
to both the robustness of the problems studied and the algorithms 
developed.

\Fast  A strong background in Duality Theory and Combinatorial 
Optimization is very useful in this category.  When designing an 
FAAs special focus will be placed on making sure the algorithm's 
speed scales with the size of the input problem, and not with the 
size of the corresponding mathematical program.  Research will 
also be focus on ensuring that the algorithm is guaranteed to 
yield near optimal solutions.

\VLSI A strong background in Electrical Engineering, 
Combinatorial Optimization, and IPMs is needed to advance 
knowledge in this field.  A new focus on the theoretical 
development and practical implementation of FAAs, as well as 
improved SDO relaxation techniques will be used to advance 
knowledge in VLSI design.

\Power  A strong background in Power Systems and Linear 
Programming is very helpful in researching Power Market 
Management.  While researching this field special attention will 
be given to market structure, power system stability, and 
developing tools and techniques which are applicable to real 
power systems.

\DM  A strong background in statistics, machine learning, 
mathematical modelling, mathematical programming and data base 
system management is needed to research in data mining. Future 
research will focus on developing novel data mining models from 
an optimization perspective, and design efficient techniques for 
these new models.

\DC A strong background in Graph Theory is essential to study 
Digital Communications.  Knowledge of Electrical Engineering and 
FAAs is also key to advancing knowledge in the field.  Future 
focus will be on optical network design and routing problems for 
wireless networks.

\question{e) Description of subprojects}

As mentioned in Section (a), this project can be broken into the 
subgroups {\it Interior Point Methods, Semi-definite 
Optimization, Fast Approximation Algorithms, Very Large Scale 
Integration, Power Market Management, Data Mining,} and {\it 
Digital Communication.}  

\IPM  The study of IPMs focuses on improving the theory behind 
the IPM and designing new algorithms based on the IPM.

\SDO  Research in SDO examines theory and algorithms of SDO.   
This includes new methods of modelling problems as semi-definite 
programs, and implementing new theory and algorithms on problems 
modelled in SDO form.

\Fast  Study into FAAs creates new algorithms which are 
polynomial time in the size of the input problem, and guaranteed 
to give near optimal solutions with a known approximation ratio.

\VLSI  Work of VLSI design focuses on improving algorithms to 
solve the partitioning, placement, and routing subproblems of 
chip design.

\Power  Research into Power Market Management creates new models 
of power system planning and control and new algorithms which 
solve these models to give a stable system while minimizing the 
cost of meeting demand.

\DM  New techniques in Data Mining uses theory and tools from 
optimization to solve the classification and clustering problems.

\DC  New algorithms in digital communications are using FAAs to 
find rapid and near optimal solutions to optical network design 
and ad-hoc wireless network problems.

\question{f) Significance of results obtained}

With the development of new optimization tools and algorithms, 
problems which were once considered out of reach are now 
approachable by modern solvers.  The result has been a renewed 
interest in modelling and solving problems via High Performance 
Optimization.  With new problem models come new challenges to 
overcome and new theory to develop.  Challenges may be in the 
form of problem size, generating a need for better IPMs and FAAs, 
or in problem style, forcing the creation of broader SDO theory. 
As these challenges are encoutered they have immediate 
applications in engineering and design problems.  Some of the 
recent impact for each subgroup of this proposal follows.

\IPM  In IPMs we have made significant impact in:
\begin{tightenumerate}
\item[New Theory:]  The new examples of \cite{DNPT04} and 
\cite{DNT04} show the theoretical worst case complexity of the 
central path following IPMs cannot be improved.  This closes one 
line of research allowing better focus on more promising 
directions.  
\\  The new sensitivity analysis of \cite{GHMT05a} \cite{GHMT05b} 
and \cite{GHRT05} has opened up new ideas which may lead to 
promising new algorithms or theory.

\item[New Methods:] The new self-regular infeasible IPMs of 
\cite{STZ02} \cite{SPT05} have improved the worst case complexity 
of infeasible IPMs, and shown great numerical promise. 
\\ New approaches to predictor-corrector IPMs have resulted in 
novel algorithms with great potential \cite{SPT05}.
\end{tightenumerate}

\SDO In SDO we have made significant impact in: 
\begin{tightenumerate}
\item[Robustness Theory:]  A growing emphasis on robust 
algorithms in the industrial sector, has recently prompted 
significant research into the area.  The new studies into round 
off error from \cite{GLWW04} \cite{RSW02} \cite{TW05} 
\cite{Wol04} have resulted in several new robust SDO algorithms.

\item[New Models:]  New modelling techniques have allowed SDO to 
be used in MRI design, molecular conformation and protein folding 
\cite{ASTZ04} \cite{ATW02} \cite{aLW05}.   This further developed 
the analysis of sequential SDO for nonlinear SDOs.  The model and 
techniques developed also appear appropriate to model and create 
powerful solution techniques for network stability and efficiency 
of electricity networks.

\item[Improved Software:]  With the taking over of SeDuMi at the 
AdvOL of McMaster, the celebrated SDO package has become 
revitalized in the Optimization community.  New techniques have 
vastly increased SeDuMi's speed (as much as ten times faster on 
many problems).  The software is available free online at 
http://sedumi.mcmaster.ca, where it has been downloaded by almost 
1000 users worldwide.
\end{tightenumerate}

\Fast In FAAs have made significant impact in:
\begin{tightenumerate}
\item[New Algorithms:]  The new FAAs for packing problems, VLSI 
design, and digital communications have sparked great interest in 
the field of Fast Approximation Algorithm design.
\end{tightenumerate}

\VLSI  In VLSI design we have made significant impact in:
\begin{tightenumerate}
\item[Modelling Techniques:]  The new modelling techniques of 
\cite{KVV04} and \cite{AV05} resulted in new simulated test 
results which beat the previously best known techniques 
by three to eight percent.

\item[New Methods:]  The two new FAAs developed in \cite{STVZ05b} 
and \cite{TVZ05} have sparked an entirely new approach to solving 
the VLSI routing problem.
\end{tightenumerate}

\Power  Since the Power Market Management group is just joining 
us, it would be unfair to claim we have made any significant 
impact in this area to date.

\DM  In Data Mining we have made significant impact in:
\begin{tightenumerate}
\item[New models:] The novel 0-1 semi-definite programming models 
developed in \cite{PX05a}, \cite{PX05b} and \cite{PW05} provide a 
unified framework for various clustering problems and opens many 
new avenues for attacking these problems. 

\item[New techniques:] New efficient approximation algorithms 
based on principal component analysis have been developed.  These 
allow us to deal with large-scale data base.
\end{tightenumerate}

\DC In Digital Communications we have made significant impact in:
\begin{tightenumerate}
\item[New Methods:]  The new FAAs for multicast networks 
\cite{TVZ05} \cite{STVZ05a} and ad-hoc wireless networks 
\cite{CYZ05} have created new approaches to solving digital 
communication problems.
\end{tightenumerate}
\newpage

\pagestyle{myheadings} \markboth{T. Terlaky - H.P.O. and App.: 
Personnel Developement}{T.  Terlaky - HPO and App.: Personnel 
Developement} 
\section{Development of Highly Qualified Personnel}

Our project's commitment to the training of highly qualified 
personnel can be seen in our highly successful graduate programs 
and our strong conference and seminar series.

Recently, we have seen a spectacular growth in the training of 
graduate students.  In the last two years, between the three 
schools currently involved in the project, we have awarded over 
20 Masters and Doctorate degrees.  We have also been host to 
numerous post-doctorial fellows and visitors.   Currently we are 
training more than 25 graduate students, and hosting 7 
post-doctorial fellows and visitors.  

Our success in training graduate students can be seen in the 
various prizes they have received.  These include: the ``MITACS' 
Best Student Paper'' (won by M. Salahi in 2005), first prize at 
the ``MITACS student poster competition'' (won by S. Stoyan in 
2004), the ``Canadian Operational Research Society Best Student 
Paper'' (won by O. Romanko in 2004), and the ``WindSOR/SWORD best 
graduate presentation'' (won by Z. Zheng in 2004).

Further commitment to personnel training is expressed in the 
recently opened ``Electricity Market Simulation and Optimization 
Laboratory'' ({\bf EMSOL}) at Waterloo and the soon to be opened 
``McMaster School for Computational Engineering and Science'' 
({\bf MSCES}).  These will provide a new range of opportunities 
for training highly qualified personnel in optimization and its 
applications to computational research. 

Our training of highly qualified personnel is further enhanced by 
our ongoing seminar series.  Both McMaster and Waterloo host 
weekly seminars that broaden understanding of Optimization and 
its applications.  McMaster also hosts a weekly student seminar, 
which provides the perfect platform for new students to train 
their public speaking skills.  Each month the ``Industrial 
Optimization Seminar Series'' at the Fields Institute invites a 
member of the professional community to speak on how Optimization 
is applied in their field, and a distinguished professor to speak 
on the cutting edge of optimization research in that field.

In addition to continuing all of these seminars, we also plan to 
begin two new seminar series;  a series of seminars in 
electricity markets and optimization will be hosted in the EMSOL, 
while the MSCES will invite a series of high-profile guest 
speakers.  We anticipate the opportunities arising from the 
creations of the MSCES and the EMSOL, will bring an expansion of 
the number of internships with industrial partners.

In addition to seminars, we will continue to host the annual 
conference ``Modelling and Optimization: Theory and 
Algorithms,''  that moves between the three project Universities 
(McMaster from 2001 to 2004, Windsor in 2005, Waterloo in 2006, 
and McMaster in 2007).  We will also continue organizing special 
research workshops such as the ``Large Scale Nonlinear and 
Semidefinite Programming Workshop'' (Waterloo, 2004), the 
``McMaster Optimization Day'' (McMaster, 2004), the ``Workshop on 
Mathematical Programming in Data Mining and Machine Learning'' 
(McMaster, 2005), and the ``Franco-Canadian Workshop on 
Combinatorial Algorithms'' (McMaster, 2005).  Future special 
events include the ``Workshop on Optimization in Engineering'' at 
the Banff International Research Station in 2006, and the 
triennial ``International Conference on Continuous Optimization'' 
at McMaster in 2007.   The latter will offer a summer school on 
Computational Optimization.  

\newpage
\pagestyle{myheadings} \markboth{T. Terlaky - H.P.O. and App.: 
Networking and Knowledge Exchange}{T.  Terlaky - HPO and App.: 
Networking and Knowledge Exchange} 
\section{Networking}

We intend to continue a number of networking activities that have 
been carried out regularly in recent years.   These include the 
weekly ``Advanced Optimization Seminar Series'' at McMaster and 
the ``Industrial Optimization Seminar Series'' at the Fields 
Institute.  In the past, both of these seminar series have 
successfully brought high-profile individuals from both the 
academic and industrial sectors to speak and network with the 
project members.

The universities involved in this project shall also continue to 
host the annual conference ``Modelling and Optimization: Theory 
and Algorithms,'' (Waterloo in 2006, and McMaster in 2007) and to 
organize special focus research workshops such as the ``Workshop 
on Optimization in Engineering'' at the Banff International 
Research Station in 2006, and the triennial ``International 
Conference on Continuous Optimization'' at McMaster in 2007.   
These conferences and workshops attract faculty members from 
various engineering and science departments from all the 
collaborating institutions and beyond, thus providing excellent 
networking opportunities.

The faculty affiliated with this project have played a key role 
in the creation of the ``McMaster School for Computational 
Engineering and Science'' ({\bf MSCES}), which we anticipate will 
attract many industrial research projects.   To encourage this we 
plan to initiation a new series of high-profile guest speakers at 
the MSCES, which will further provide networking opportunities.  

Our future plans also include a new series of seminar speakers in 
electricity markets and optimization, which shall be hosted at 
the new ``Electricity Market Simulation and Optimization 
Laboratory'' at Waterloo.


\section{Knowledge Exchange and Technology Transfer}

\noindent{\it Patents, and Licenses:} None \medskip

\noindent{\it Copyrights:}  All published works are copyrighted 
by the journal that publishes them. \medskip

\noindent{\it Software packages:}  Both the McIPM and SeDuMi 
optimization packages have undergone major revision and 
improvement over the last few years.  

The McIPM software now has both feasible self-regular-IPM and 
infeasible IPM software.  These advances will become available, 
free, online in the near future. 

The 2004 acquisition of the SeDuMi program by the AdvOL group at 
McMaster breathed new life into the package. Since then, new 
techniques have improved SeDuMi's speed by as much as ten times 
on many problems.  The improved software has been made available 
online at the new webpage http://sedumi.mcmaster.ca, which has 
received over 60,000 visitors.  The latest version, released in 
June of 2005, has already been downloaded over 900 times.  The 
webpage also hosts an active forum, where over 200 topics and 
responses have been posted since its creation in October 2004.

\newpage
\pagestyle{myheadings} \markboth{T. Terlaky - H.P.O. and App.: 
Addition Info}{T.  Terlaky - HPO and App.: 
Addition Info} 

\section{Additional Information}

One of the primary goals of this project is to increase 
collaboration and create new opportunities for collaboration 
between the institutes involved in the project.  In this regard 
we have been very successful.

Through the joint organization and hosting of several seminar 
series and conferences, the bonds between McMaster, Windsor and 
Waterloo have been strengthened.  This has resulted in new 
research directions, and new opportunities to extend the theory, 
algorithms and applications of high performance optimization.

The networks created through this project have resulted in many 
joint research projects across departments and between 
universities. Some papers resulting from these projects include
includes \cite{AW05} (Waterloo and Windsor), \cite{STVZ05b} 
(McMaster and Waterloo), \cite{STZ02} (McMaster and Windsor), 
\cite{TVZ05} (McMaster and Waterloo),  and \cite{ATV05} (across 
two departments in Waterloo).

The new connections this project has built between McMaster, 
Windsor and Waterloo, has also resulted in the ability to jointly 
host post-doctorial fellows and other visitors.  The connections 
this project has developed also resulted in Vannelli taking his 
recent sabbatical year at McMaster in order to further increase 
collaboration between the schools.

In the future, we expect this collaboration to increase with the 
addition of the new members in electricity markets.

To allow for the creation of the two new seminar series, the 
continuation of pervious seminar and conference series, and to 
create a strong base for collaboration with our new members, 
{\bf we are requesting an increase in the base funding to \$ 
220,000 per year, plus a yearly allocation of \$ 30,000 in 
internship funds.}

\newpage
\pagestyle{myheadings} \markboth{T. Terlaky - H.P.O. and App.: 
Suggested Referees}{T.  Terlaky - HPO and App.: Suggested 
Referees} 

\section{Suggested Referees}
Alphabetical by last name, we suggest:
\begin{enumerate}
\item[1.] Jean-Louis Goffin, \\ Faculty of Management, \\McGill 
University, \\ Montreal, Canada. \\ phone: 514-398-4003 \\ 
e-mail: goffin@management.mcgill.ca

\item[2.] Florian Jarre,\\ Lehrstuhl f\"{u}r Mathematische 
Optimierung, \\ Universit\"{a}t D\"{u}sseldorf,\\ D\"{u}sseldorf, 
Germany. \\ phone: 49 211 - 81 - 131 91 \\ e-mail:      
jarre@opt.uni-duesseldorf.de

\item[3.] Arkadi Nemirovski,\\ School of Industrial and Systems 
Engineering,\\ Georgia Institute of Technology, \\ Atlanta, USA. 
\\ phone: 404-385-0769 \\ e-mail: arkadi.nemirovski@isye.gatech.edu

\item[4.] Florian Potra, \\Department of Mathematics and 
Statistics,\\ University of Maryland, Baltimore County, \\ 
Baltimore, USA. \\ phone:  410-455-2429 \\ e-mail: 
potra@math.umbc.edu

\item[5.] Robert Vanderbei, \\ Operations Research and Financial 
Engineering, \\ Princeton University, \\ Princeton, USA. \\ 
phone: 609-258-2345 \\ e-mail: rvdb@princeton.edu

\item[6.] Lieven Vandenberghe, \\Electrical Engineering 
Department,\\ University of California Los Angeles, \\ Los 
Angeles, USA. \\ phone: 310-206-1259 \\ e-mail:  
vandenbe@ee.ucla.edu
\end{enumerate}


\newpage
\pagestyle{myheadings} \markboth{T. Terlaky - H.P.O. and App.: 
References}{T.  Terlaky - HPO and App.: References}
%---------------BIBLIOGRAPHY---------------
\bibliographystyle{alpha}
\bibliography{MITACS}
\end{document}
