HOME    »    PROGRAMS/ACTIVITIES    »    Annual Thematic Program
Fall 2002
IMA Workshop 2
Computational Methods for Large Scale Integer Programs
October 14-19, 2002


Optimization, September 2002 - June 2003

Organizers:

William J. Cook
School of Industrial and Systems Engineering
Georgia Institute of Technology
wcook@isye.gatech.edu
http://www.isye.gatech.edu/~wcook/

Michel Gendreau
Centre de Recherche sur les transports
Université de Montréal
michelg@crt.umontreal.ca
http://www.iro.umontreal.ca/~gendreau/

George L. Nemhauser
School of Industrial and Systems Engineering
Georgia Institute of Technology
george.nemhauser@isye.gatech.edu

Martin W.P. Savelsbergh
School of Industrial and Systems Engineering
Georgia Institute of Technology

martin.savelsbergh@isye.gatech.edu
http://www.isye.gatech.edu/~mwps/

IMA PUBLIC LECTURE
The Traveling Salesman Problem
William J. Cook
October 16, 7:00 pm,
Moos Tower, Room 2-650
University of Minnesota, East Bank

http://www.ima.umn.edu/public-lecture/tsp/index.html
http://www.math.princeton.edu/tsp/
Poster:   pdf    
jpeg
Talk 58 mins. RealVideo(SureStream)|RealAudio(SureStream)

In the past decade there have been significant theoretical and computational advances in the field of integer programming. As a result there has been a greatly increased use of integer programming software in industry. However, the need to solve even larger and more complex problems continues to grow. In this workshop, we will bring together experts in various areas of integer programming and its applications. Theoretical and methodological topics included in the workshop are approximation algorithms for large scale linear programs, stochastic integer programming, branch-and-cut and branch-and-price, algebraic and combinatorial methods, decomposition, constraint programming and parallel implementation. Application areas include supply chain design and management, telecommunications, manufacturing, transportation, scheduling, and finance. The workshop will be of interest to mathematicians and operations researchers working in discrete and combinatorial optimization, computational scientists working in parallel computing, search, and constraint programming. Goals of the workshop include building a research agenda for the next decade, defining new areas of application, and stimulating cooperation among the different disciplines that contribute to the field.

WORKSHOP SCHEDULE

Monday Tuesday Saturday
MONDAY, OCTOBER 14
All talks are in Lecture Hall EE/CS 3-180 unless otherwise noted.
8:30 am Coffee and Registration

Reception Room EE/CS 3-176

9:15 am Douglas N. Arnold, Scot Adams, and Organizers Welcome and Introduction
9:30-10:20 am Daniel Bienstock
Columbia University

Subset Algebra Lifting

Slides:    pdf

10:20-10:30 am Coffee Break Reception Room EE/CS 3-176
10:30-11:20 am Dimitris Bertsimas
MIT

Robust Discrete, Dynamic Optimization and Network Flows

Slides:    pdf    ps

11:20-1:30 pm
Lunch Break
1:30-2:20 pm David Applegate
AT&T
Solving Random Euclidean TSPs
2:20- 2:30 pm Coffee Break Reception Room EE/CS 3-176
2:30-3:00 pm
SECOND CHANCES, i.e., speakers of the day respond to further questions, suggestions, re-frame their main points, look toward future directions.
3:00 pm IMA Tea/Reception
A variety of appetizers and beverages will be served.
IMA East, 400 Lind Hall
TUESDAY, OCTOBER 15
All talks are in Lecture Hall EE/CS 3-180 unless otherwise noted.
9:00- 9:30 am Coffee Reception Room EE/CS 3-176
9:30-10:20 am Karen Aardal
Georgia Institute of Technology

Lattice Basis Reduction and Integer Programming

Papers:    journal.pdf   journal.ps    ut6n.pdf    ut6n.ps

References:
K. Aardal, R. Weismantel, and L.A. Wolsey. Non-standard approaches to integer programming. Discrete Applied Mathematics 123, 2002, 5-74.

K. Aardal and A.K. Lenstra. Hard equality constrained integer knapsacks Preprint 1256, Department of Mathematics, Utrecht University, 2002, (submitted). Preliminary version appeared in: W.J. Cook and A.S. Schulz (eds.), Integer Programming and Combinatorial Optimization: 9th International IPCO Conference, Lecture Notes in Computer Science vol. 2337, Springer-Verlag, 2002, pp 350-366.

10:20-10:30 am Coffee Break Reception Room EE/CS 3-176
10:30-11:20 am Rekha R. Thomas
University of Washington, Seattle
The Structure of Group Relaxations
11:20- 1:30 pm
Lunch Break
1:30-2:20 pm William R. Pulleyblank
IBM Research
Caratheodory's Theorem, Cutting Planes, and Parallel Computers
2:20-2:30 pm Coffee Break Reception Room EE/CS 3-176
2:30-3:20 pm Pascal Van Hentenryck
Brown University
Local Search Programming
3:20-3:30 pm Coffee Break Reception Room EE/CS 3-176
3:30-4:00 pm
SECOND CHANCES, i.e., speakers of the day respond to further questions, suggestions, re-frame their main points, look toward future directions.
4:00 pm Coffee Break Reception Room EE/CS 3-176
WEDNESDAY, OCTOBER 16
All talks are in Lecture Hall EE/CS 3-180 unless otherwise noted.
9:00-9:30 am Coffee Reception Room EE/CS 3-176
9:30-10:20 am Ismael Regis de Farias Jr.
Carnegie Mellon University
Semi-Continuous Cuts for Mixed-Integer Programming
10:20-10:30 am Coffee Break Reception Room EE/CS 3-176
10:30-11:20 am Alexander Martin
TU Darmstadt

Mixed Integer Models for the Optimization of Gas Networks

Slides:    pdf

11:20- 1:30 pm
Lunch Break
1:30- 2:20 pm Zonghao Gu
ILOG, Inc.

One Size Fits All? Computational Tradeoffs in a Commercial Mixed Integer Programming Solver

Slides:   html    pdf    ppt

2:20-2:30 pm Coffee Break Reception Room EE/CS 3-176
2:30-3:20 pm
PANEL DISCUSSION: Robert Bixby, Sebastian Ceria, Ellis Johnson, George Nemhauser, William R. Pulleyblank
3:20-3:30 pm Coffee Break Reception Room EE/CS 3-176
3:30 4:00 pm SECOND CHANCES, i.e., speakers of the day respond to further questions, suggestions, re-frame their main points, look toward future directions.
4:00 pm Coffee Break Reception Room EE/CS 3-176
7:00 PM
IMA PUBLIC LECTURE
The Traveling Salesman Problem
William J. Cook
Moos Tower, Room 2-650
University of Minnesota, East Bank

http://www.ima.umn.edu/public-lecture/tsp/index.html
http://www.math.princeton.edu/tsp/
Poster:   
pdf    jpeg
Talk 58 mins. RealVideo(SureStream)|RealAudio(SureStream)
THURSDAY, OCTOBER 17
All talks are in Lecture Hall EE/CS 3-180 unless otherwise noted.
9:00-9:30 am Coffee Reception Room EE/CS 3-176
9:30-10:20 am Robert Weismantel
University of Magdeburg
Column Operations for Mixed Integer Programs
10:20-10:30 am Coffee Break Reception Room EE/CS 3-176
10:30-11:20 am Ellis Johnson
Georgia Tech

Cyclic Group and Knapsack Facets

Slides:   html    pdf    ppt

11:20-1:30 pm
Lunch Break
1:30-2:20 pm Francisco Barahona
IBM T.J. Watson Research Center

Network Reinforcement

Paper:    pdf

2:20-2:30 pm Coffee Break Reception Room EE/CS 3-176
2:30-3:00 pm
SECOND CHANCES, i.e., speakers of the day respond to further questions, suggestions, re-frame their main points, look toward future directions.
3:00 pm Coffee Break Reception Room EE/CS 3-176
6:00 pm Workshop Dinner Loring Pasta Bar
Dinkytown
327 14th Avenue S.E.
612-378-4849
FRIDAY, OCTOBER 18
All talks are in Lecture Hall EE/CS 3-180 unless otherwise noted.
9:00-9:30 am Coffee Reception Room EE/CS 3-176
9:30-10:20 am

Jacques Desrosiers
Ecole des Hautes Etudes Commerciales

Jean-Philippe Vial
University of Geneva

Stabilized Column Generation Based on Primal and Dual Strategies
Slides:   html    pdf    ppt

Solving Lagrangian Relaxations with a Proximal Analytic Center Cutting Plane Method
Slides:    pdf
10:20-10:30 am Coffee Break Reception Room EE/CS 3-176
10:30-11:20 am Ralph E. Gomory
Sloan Foundation
T-Space and Cutting Planes
11:20- 1:30 pm
Lunch Break
1:30-2:20 pm Vasek Chvatal
Rutgers University
TSP Cuts that Do Not Follow the Template Paradigm
2:20-2:30 pm Coffee Break Reception Room EE/CS 3-176
2:30-3:00 pm
SECOND CHANCES, i.e., speakers of the day respond to further questions, suggestions, re-frame their main points, look toward future directions.
3:00 pm Coffee Break Reception Room EE/CS 3-176
SATURDAY, OCTOBER 19
All talks are in Lecture Hall EE/CS 3-180 unless otherwise noted.
(Centre de Recherche(s) - Column Generation Methods)
9:00-9:30 am Coffee Reception Room EE/CS 3-176
9:30-10:20 am François Vanderbeck
Université Bordeaux 1

Dantzig-Wolfe Decomposition for MIP

Slides:    pdf

10:20-10:30 am Coffee Break Reception Room EE/CS 3-176
10:30-11:20 am Michel Gendreau
Université de Montréal

A Column Generation Approach for Vehicle Routing with Time Windows and Split Deliveries?

Slides

11:20-11:30 am Coffee Break Reception Room EE/CS 3-176
11:30-12:20 pm Jean-Louis Goffin
McGill University
Analytic Centers Cutting Plane Methods and Mixed Integer Programming, with Extensions to Semi-definite Cuts
12:20-12:30 pm Coffee Break Reception Room EE/CS 3-176
12:30-1:00 pm
SECOND CHANCES, i.e., speakers of the day respond to further questions, suggestions, re-frame their main points, look toward future directions.
Monday Tuesday Saturday

LIST OF CONFIRMED PARTICIPANTS

As of 10/21/2002
Name Department Affiliation
Karen Aardal Industrial and Systems Engineering Georgia Institute of Technology
Scot Adams Institute for Mathematics & Applications IMA
Shabbir Ahmed Industrial & Systems Engineering Georgia Institute of Technology
Beth Allen Economics University of Minnesota
David Applegate   AT&T Labs-Research
Doug N. Arnold Institute for Mathematics and it's Application Institute for Mathematics and its Applications
Don Aronson   Institute for Mathematics
Assist Alper Atamturk Industrial Eng. and Oper. Research University of California at Berkeley
Egon Balas Graduate Industrial Administration Carnegie Mellon University
Francisco Barahona   IBM T.J. Watson Research Center
Dimitris Bertsimas Sloan Management MIT
Daniel Bienstock IEOR Columbia University
Robert E. Bixby   ILOG, Inc.
Olga Brezhneva   Institute for Mathematics and its Applictions
David B. Brown Electrical Engineering and Computer Sciences MIT
Sebastian Ceria Graduate Business Columbia University
Vasek Chvatal Computer Science Rutgers University
William Cook Industrial and Systems Engineering Georgia Tech
Collette Coullard Engineering and Management Northwestern University
Bob Crone   Seagate
Georgios Dalakouras Mathematics Worcester Polytechnic Institute
Milind Dawande Management University of Texas at Dallas
Ismael de Farias, Jr. Graduate Industrial Administration Carnegie Mellon University
Jacques Desrosiers Management Sciences Ecole des Hautes Etudes Commerciales
Lisa Evans IMA Institute for Mathematics & Applications
Michel Gendreau Centre de Recherche sur les transports Universite de Montreal
Jean-Louis Goffin Faculty of Management McGill University
Ralph E. Gomory   Alfred P. Sloan Foundation
Balaji Gopalakrishnan   Institute for Mathematics and its Applictions
Zonghao Gu   ILOG
Oktay Gunluk Mathematical Sciences IBM T.J. Watson Research Center
David L. Jensen Mathematical Sciences IBM Corporation
Ellis Johnson Industrial & Systems Engineering Georgia Institute of Technology
Lili Ju   Minneapolis VA Medical Center
Ben Justin UMTYMP University of Minnesota
Herve Kerivin IMA Institute for Mathematics and its Application
Laszlo Ladanyi Mathematical Sciences IBM T.J. Watson Research Center
Maher Lahmar Industrial Engineering University of Minnesota
Robin Lougee-Heimer Mathematical Sciences IBM T.J. Watson Research Center
Youssef Ltaief Mechanical Engineering University of Minnesota
Francois Margot Mathematics University of Kentucky
Alexander Martin Fachbereich Mathematik, AG 7 Darmstadt University of Technology
Willard Miller Mathematics University of Minnesota
Denis Naddef Laboratoire Informatique it Distribution INSIMAG - antenne de Montbonnot
Richard Nau Mathematics & Computer Science Carleton College
George L. Nemhauser Industrial and Systems Engineering Georgia Institute of Technology
Peh Ng Institute fpr Mathematics & Applications IMA
Samuel Patterson Mathematics and Computer Science Carleton College
Bill Pulleyblank   IBM T.J. Watson Research Center
Maurice Queyranne Faculty of Commerce & Business Administration University of British Columbia
Vic Reiner Mathematics University of Minnesota
Ed Rothberg   ILOG, Inc.
Fadil Santosa Institute for Mathematics and it's Application University of Minnesota
Martin Savelsbergh Industrial and Systems Engineering Georgia Institute of Technology
M. Nuri Sendil Industrial Eng. & Mgmt. Sciences Northwestern University
Melvyn Sim   MIT
Tamon Stephen IMA Institute for Mathematics and its Applications
Dharmashankar Subramanian   Honeywell Labs
Vladimir Sverak Mathematics University of Minnesota
Kosmo D. Tatalias   Army High Performance Computing Research Ctr
Rekha R. Thomas Mathematics University of Washington
Leslie Earl Trotter, Jr. Operations Research & Industrial Engineering Cornell University
Eduardo Uchoa Engenharia de Producao Universidade Federal Fluminense
Pascal Van Hentenryck Computer Science Brown University
Francois Vanderbeck Mathematiques Appliquees Bordeaux Universite de Bordeaux 1
Igor Vasil'ev Centro di Ricerca in Matematica Pura e Applicata Università degli Studi di Salerno
Jean-Philippe Vial International Symposium on Mathematical Programing University of Geneva
Jing Wang   Institute for Mathematics and its Applictions
Robert Weismantel Mathematics / IMO Otto-von-Guericke-University of Magdeburg
Dan Zhang Mechanical & Ind. Engineering University of Minnesota
Connect With Us:
Go