\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}