umn logo IMA home |  Contact IMA 
IMA Web

IMA Tutorial

Algebraic Algorithms in Optimization

January 12-13, 2007
Organizers:
Niels Lauritzen Matematisk Institut, Aarhus Universitet
Rekha R. Thomas Mathematics, University of Washington

Schedule Participants Program Application Feedback
IMA Live Streaming and Webcasting Maps
Abstracts and Talk Materials Dining Guide
Photo Gallery

Description:

In the past fifteen years, methods from algebra and algebraic geometry have been used in optimization to design algorithms and understand the structure of optimization problems. These techniques include basis reduction, the theory of Groebner bases, rational generating functions, nonnegativity of real polynomials and further methods from real algebraic geometry. This tutorial will be roughly divided into two parts---the first focussing on algebraic methods in discrete optimization and the second on methods from algebra and real algebraic geometry in semi-definite programming and polynomial optimization.

The tutorial will provide an introduction to these methods and will be aimed at non-specialists. The activities will consist of introductory lectures followed by hands-on computational sessions using state-of-the-art software packages in these fields.

Schedule
Friday, January 12
8:00a-8:30a Coffee and Registration   EE/CS 3-176
8:30a-8:40a Welcome and opening remarks Douglas N. Arnold (University of Minnesota) EE/CS 3-180
8:40a-9:30a Gröebner basis methods in integer programming (Lecture Part I) Edwin O'Shea (University of Kentucky) EE/CS 3-180
9:30a-10:00a Coffee   EE/CS 3-176
10:00a-10:50a Hands on exercises assisted by Tristram Bogart (Tutorial Part I) Edwin O'Shea (University of Kentucky) Lind Hall 400
11:00a-11:50a Gröebner basis methods in integer programming (Lecture Part II) Edwin O'Shea (University of Kentucky) EE/CS 3-180
11:50a-1:30p Lunch    
1:30p-2:20p Hands on exercises assisted by Tristram Bogart (Tutorial Part II) Edwin O'Shea (University of Kentucky) Lind Hall 400
2:20p-2:40p Coffee   EE/CS 3-176
2:40p-3:30p Optimization over polynomials with moment matrices and sums of squares

Remarks: (Due to visa problems Monique Laurent was not be able to attend the tutorial. Jean Bernard Lasserre substituted for Monique Laurent.)

Jean Bernard Lasserre (Centre National de la Recherche Scientifique (CNRS)) EE/CS 3-180
3:30p-3:50p Coffee   EE/CS 3-176
3:50p-4:40p Optimization over polynomials with moment matrices and sums of squares(continued) Jean Bernard Lasserre (Centre National de la Recherche Scientifique (CNRS)) EE/CS 3-180
Saturday, January 13
8:30a-9:00a Coffee   EE/CS 3-176
9:00a-9:50a Optimization over polynomials with moment matrices and sums of squares(continued) Jean Bernard Lasserre (Centre National de la Recherche Scientifique (CNRS)) EE/CS 3-180
9:50a-10:20a Coffee   EE/CS 3-176
10:20a-11:10a Demonstration of software Hartwig Bosse (Center for Mathematics and Computer Science (CWI)) EE/CS 3-180
11:20a-12:10p Generating functions for integer optimization (part I) Jesus Antonio De Loera (University of California) EE/CS 3-180
12:10p-1:30p Lunch    
1:30p-2:20p Generating functions for integer optimization (part I)-continued Jesus Antonio De Loera (University of California) EE/CS 3-180
2:20p-2:50p Coffee   EE/CS 3-176
3:00p-3:50p Generating functions for integer optimization (part II) Jesus Antonio De Loera (University of California) EE/CS 3-180
4:00p-5:00p Demo and introduction to LattE Jesus Antonio De Loera (University of California) EE/CS 3-180

LIST OF CONFIRMED PARTICIPANTS

Name Department Affiliation
Cheonghee Ahn Department of Mathematics Yonsei University
Elizabeth S. Allman Department of Mathematics and Statistics University of Alaska
Douglas N. Arnold Institute for Mathematics and its Applications University of Minnesota Twin Cities
Donald G. Aronson Institute for Mathematics and its Applications University of Minnesota Twin Cities
Daniel J. Bates Institute for Mathematics and its Applications University of Minnesota Twin Cities
Víctor Blanco Izquierdo Department of Statistics and Operational Research University of Sevilla
Cristiano Bocci Department of Mathematics Università di Milano
Tristram Bogart Department of Mathematics University of Washington
Hartwig Bosse PNA1 (Algorithms, Combinatorics and Optimization) Center for Mathematics and Computer Science (CWI)
Enrico Carlini Dipartimento di Matematica Politecnico di Torino
Hi Jun Choe Department of Mathematics Yonsei University
Ionut Ciocan-Fontanine Institute for Mathematics and its Applications University of Minnesota Twin Cities
Jesus Antonio De Loera Department of Mathematics University of California
Xuan Vinh Doan Operations Research Center Massachusetts Institute of Technology
Kenneth R. Driessel Department of Mathematics Iowa State University
Mathias Drton Department of Statistics University of Chicago
Lingling Fan   Midwest ISO
Makan Fardad Department of Electrical and Computer Engineering University of Minnesota Twin Cities
Stephen E. Fienberg Department of Statistics Carnegie-Mellon University
Ioannis Fotiou Automatic Control Laboratory Eidgenössische TH Zürich-Hönggerberg
Jason E. Gower Institute for Mathematics and its Applications University of Minnesota Twin Cities
Gloria Haro Ortega Institute for Mathematics and its Applications University of Minnesota Twin Cities
Milena Hering Institute for Mathematics and its Applications University of Minnesota Twin Cities
Serkan Hosten Department of Mathematics San Francisco State University
Benjamin J. Howard Institute for Mathematics and its Applications University of Minnesota Twin Cities
Evelyne Hubert Project CAFE Institut National de Recherche en Informatique Automatique (INRIA)
Farhad Jafari Department of Mathematics University of Wyoming
Amin Jafarian Department of Electrical and Computer Engineering University of Texas
Anders Nedergaard Jensen Institut for Matematiske Fag Aarhus University
Steve Kaliszewski Department of Mathematics and Statistics Arizona State University
Edward D. Kim Department of Mathematics University of California
Si-Jo Kim Department of Chemicial Engineering Andong National University
Henry C. King Department of Mathematics University of Maryland
Song-Hwa Kwon Institute for Mathematics and its Applications University of Minnesota Twin Cities
Jean Bernard Lasserre LAAS Centre National de la Recherche Scientifique (CNRS)
Niels Lauritzen Institut for Matematiske Fag Aarhus University
Anton Leykin Institute for Mathematics and its Applications University of Minnesota Twin Cities
Hstau Y Liao Institute for Mathematics and its Applications University of Minnesota Twin Cities
Gennady Lyubeznik School of Mathematics University of Minnesota Twin Cities
Hannah Markwig Institute for Mathematics and its Applications University of Minnesota Twin Cities
Thomas Markwig Department of Mathematics Universität Kaiserslautern
Lisa A. Miller Department of Mechanical Engineering University of Minnesota Twin Cities
Richard B. Moeckel School of Mathematics University of Minnesota Twin Cities
Kristen Nairn   St. John's University
Jiawang Nie Institute of Mathematics and its Application University of Minnesota Twin Cities
Edwin O'Shea Department of Mathematics University of Kentucky
Mihai Putinar Department of Mathematics University of California
Bharath Rangarajan Department of Mechanical Engineering University of Minnesota Twin Cities
Victor Reiner School of Mathematics University of Minnesota Twin Cities
John A. Rhodes Department of Mathematics and Statistics University of Alaska
Jakayla Robbins Department of Mathematics University of Kentucky
Joel Roberts School of Mathematics University of Minnesota Twin Cities
Philipp Rostalski Automatic Control Laboratory Eidgenössische TH Zürich-Hönggerberg
Bjarke Hammersholt Roune Department of Mathematics Aarhus University
Christopher Ryan Sauder School of Business University of British Columbia
Arnd Scheel Institute for Mathematics and its Applications University of Minnesota Twin Cities
Parikshit Shah Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology
Chehrzad Shakiban Institute of Mathematics and its Application University of Minnesota Twin Cities
Steven Sperber School of Mathematics University of Minnesota Twin Cities
Dumitru Stamate School of Mathematics University of Minnesota Twin Cities
Rekha R. Thomas Department of Mathematics University of Washington
Carl Toews Institute for Mathematics and its Applications University of Minnesota Twin Cities
John Voight Institute for Mathematics and its Applications University of Minnesota Twin Cities
Tiyu Wang Department of Mathematics University of California
Gregory Emmanuel Yawson Department of Engineering Technology Lawrence Technological University
Josephine Yu Department of Mathematics University of California
Hongchao Zhang Institute for Mathematics and its Applications University of Minnesota Twin Cities
Lihong Zhi Mathematics Mechanization Research Center Chinese Academy of Sciences