Web: http://www.ima.umn.edu | Email: ima-staff@ima.umn.edu | Telephone: (612) 624-6066 | Fax: (612) 626-7370
This month's talks available at http://www.ima.umn.edu/newsletters

IMA Newsletter #345

July 2005

News and Notes

IMA renewal recommended

We are delighted to announce that the Division of Mathematical Sciences of the National Science Foundation, the primary funding source for the IMA, has recommended the renewal of the IMA for the period 2005–2010 with a substantial increase in funding. Our thanks to everyone who helped the IMA with the renewal proposal, site visit, and other crucial steps in the renewal process.

Check back next month for more details!

Feedback in rhyme

Participant feedback plays a crucial role in IMA assessment, documenting the impact of our programs and guiding future program planning. We benefit from visitors' praise, criticism, suggestions, queries, and poetry.

I'm here at the IMA,
Attending a workshop today.
      In Room 3-180,
      The topics are weighty,
For that is the IMA way.

                  —Martin Eiger, participant in the IMA Summer Program "Wireless Communications"

IMA Events

IMA Workshop

Mixed Integer Programming

July 25-29, 2005

Organizers: Alper Atamturk (University of California - Berkeley), Daniel Bienstock (Columbia University), Sanjeeb Dash (IBM Corporation), Adam Letchford (Lancaster University), Jeff Linderoth (Lehigh University)


Mixed-integer programming (MIP) has entered a fourth, and critical, phase. The initial phase of development, beginning in the 1950's, identified some core methodological and modeling techniques, and discovered the inherent complexity of combinatorial problems. The second phase (late '60s through mid '80s) embarked on a primarily methodological path, which paralleled, in a smaller scale, that taken by the Theoretical Computer Science community. The third phase (1990's) used the methodological developments of the prior decades to obtain software implementations far superior to any available before.

We are now in the fourth phase, which recognizes the (often stunning) implementational successes recorded in the last ten years, while also acknowledging the fact that much more methodological work is needed. In this phase, building bridges to other areas of mathematics is an important component. Nevertheless, MIP now constitutes a unique computational science: it attempts to routinely solve problems that are fundamentally intractable and that arise from many applications, and it does so by blending mathematics, ever more sophisticated implementations, and innovative modeling.

This meeting will bring together many of the leading researchers in both the theoretical and computational aspects of MIP to highlight recent advances, foster interaction and collaboration, and to discuss how to expand the role of MIP in several potential high-impact application areas, such as network design for the Power Grid, computational biology, medical treatment planning, and cryptography.


Friday, July 1

Last day of the IMA Summer Program "Wireless Communications"
8:30a-9:00aCoffeeEE/CS 3-176 SP6.22-7.1.05
9:00a-10:00aOptimization of IEEE 802.11 DCF based on Bayesian estimation of the number of competing terminals Xiaodong Wang (Columbia University)EE/CS 3-180 SP6.22-7.1.05
10:00a-10:30aCoffeeEE/CS 3-176 SP6.22-7.1.05
10:30a-11:30aEnergy efficiency in multiple-access wireless networks: Nash equilibria in power control games Vincent Poor (Princeton University)EE/CS 3-180 SP6.22-7.1.05
11:30a-12:00pSecond Chances and Concluding RemarksEE/CS 3-180 SP6.22-7.1.05

Monday, July 25

Start of the IMA Hot Topics Workshop "Mixed Integer Programming"
9:30a-10:15a Coffee and registrationEE/CS 3-176 W7.25-29.05
10:15a-10:30aIntroduction and welcomeEE/CS 3-180 W7.25-29.05
10:30a-11:15aTBAEgon Balas (Carnegie Mellon University)EE/CS 3-180 W7.25-29.05
11:15a-12:00pA special case of the integer single node flow set with upper boundsMiguel Constantino (Universidade de Lisboa)EE/CS 3-180 W7.25-29.05
12:00p-2:30pLunch W7.25-29.05
2:30p-3:15pBranch-and-cut for cardinality constrained optimizationIsmael de Farias (State University of New York - Buffalo)EE/CS 3-180 W7.25-29.05
3:15p-4:00pBranching in branch-and-price algorithmsFrancois Vanderbeck (Universite de Bordeaux 1)EE/CS 3-180 W7.25-29.05
4:00p-5:00pReception and poster sessionLind Hall 409 W7.25-29.05

Tuesday, July 26

9:00a-9:30aCoffeeEE/CS 3-176 W7.25-29.05
9:30a-10:15aFaster separation of 1-wheel inequalities for stable set polytopesSven de Vries (Technische Universität München)EE/CS 3-180 W7.25-29.05
10:15a-11:00aSplit cuts and the stable set polytope of quasi-line graphsFriedrich Eisenbrand (Max-Planck-Institut fuer Informatik)EE/CS 3-180 W7.25-29.05
11:00a-2:00pLunch W7.25-29.05
2:00p-2:45pTwo-step MIR inequalities for mixed-integer setsOktay Gunluk (IBM Corporation)EE/CS 3-180 W7.25-29.05
2:45p-3:30pA basic mixed integer set: the mixing set and its applicationsLaurence Wolsey (Universite Catholique de Louvain)EE/CS 3-180 W7.25-29.05
3:30p-4:30p CoffeeEE/CS 3-176 W7.25-29.05
4:00p-5:00pRoundtable discussionDimitris Bertsimas (Massachusetts Institute of Technology)
Daniel Bienstock (Columbia University)
Adam Letchford (Lancaster University)
George L. Nemhauser (Georgia Institute of Technology)
Robert Weismantel (Otto-von-Guericke-University of Magdeburg)
EE/CS 3-180 W7.25-29.05

Wednesday, July 27

9:00a-9:30a CoffeeEE/CS 3-176 W7.25-29.05
9:30a-10:15aSymmetry in integer programmingFrancois Margot (Carnegie Mellon University)EE/CS 3-180 W7.25-29.05
10:15a-11:00aThe Dial-a-Flight-ProblemMartin Savelsbergh (Georgia Institute of Technology)EE/CS 3-180 W7.25-29.05
11:00a-2:00pLunch W7.25-29.05
2:00p-2:45pApplying discrete optimization to robust power grid problemsDaniel Bienstock (Columbia University)EE/CS 3-180 W7.25-29.05
2:45p-3:30pSolving mixed integer programs arising in statistical data editingJuan-Jose Salazar-Gonzalez (Universidad de La Laguna)EE/CS 3-180 W7.25-29.05
3:30p-4:00pCoffeeEE/CS 3-176 W7.25-29.05
4:00p-4:45pRobust branch-and-cut-and-price for the capacitated minimum spanning tree problemEduardo Uchoa (Universidade Federal Fluminense)EE/CS 3-180 W7.25-29.05
4:45p-5:30pSecond ChancesEE/CS 3-180 W7.25-29.05

Thursday, July 28

9:00a-9:30aCoffeeEE/CS 3-176 W7.25-29.05
9:30a-10:15aStrengthening the formulation of mixed integer programs with an example in production schedulingKent Andersen (Carnegie Mellon University)EE/CS 3-180 W7.25-29.05
10:15a-11:00aConstraint branching and disjunctive cuts for mixed integer programsMichael Perregaard (Dash Associates)EE/CS 3-180 W7.25-29.05
11:00a-2:00pLunch W7.25-29.05
2:00p-2:45pHeuristic integer (and mixed integer) linear programmingAndrea Lodi (DEIS, University of Bologna)EE/CS 3-180 W7.25-29.05
2:45p-3:30pIt's a beautiful day in the neighborhood—Local search in mixed integer programmingEd Rothberg (ILOG, Inc.)EE/CS 3-180 W7.25-29.05
3:30p-4:00pCoffeeEE/CS 3-176 W7.25-29.05
4:00p-4:45pColumn basis reduction, decomposable knapsack and cascade problemsGabor Pataki (University of North Carolina)EE/CS 3-180 W7.25-29.05
4:45p-5:30p Second ChancesEE/CS 3-180 W7.25-29.05

Friday, July 29

8:30a-9:00aCoffeeEE/CS 3-176 W7.25-29.05
9:00a-8:45pOn generalized branching methods for mixed integer programmingSanjay Mehrotra (Northwestern University)EE/CS 3-180 W7.25-29.05
9:45a-10:30aMixed integer polynomial programmingRobert Weismantel (Otto-von-Guericke-University of Magdeburg)EE/CS 3-180 W7.25-29.05
10:30a-10:45aCoffeeEE/CS 3-176 W7.25-29.05
10:45a-11:30aIntegerprogramming, duality and superadditive functionsJean Bernard Lasserre (LAAS-CNRS)EE/CS 3-180 W7.25-29.05
11:30a-12:00pLast ChancesEE/CS 3-180 W7.25-29.05
Kent Andersen (Carnegie Mellon University) Strengthening the formulation of mixed integer programs with an example in production scheduling
Abstract: Joint work with Yves Pochet.

We consider the following question: Is it possible to replace a constraint of a MIP formulation with a new and tighter inequality? We show that, if there is a valid inequality, which dominates a constraint of the formulation, then there is a coefficient in the formulation that can be strengthened. We also show that an algorithm, which is based on strengthening one coefficient at a time, stops after a finite number of strengthening steps. We give examples for which the difference between the quality of the original formulation and a resulting strengthened formulation is relatively large: on some problems, the effect of modifying the coefficients in the original formulation is larger than the effect of adding a large number of cutting planes (in terms of amount of integrality gap closed). For instance, on one MIPLIB instance, all of the integrality gap is closed by strengthening the coefficients in the initial formulation while optimizing over the first Chvatal closure only closes 61% of the integrality gap. We also solve another "hard" instance to optimality by strengthening coefficients in every round of a cutting plane algorithm based on mixed integer Gomory cuts and split cuts. The same cutting plane algorithm was unable to solve this instance without including the strengthening step. The instance was only recently solved with an approach based on the first Chvatal closure.

We finish by demonstrating how coefficient strengthening can be used to design a model for a production scheduling problem. First, an initial formulation of a small problem is produced, and the coefficients in this formulation are strengthened with expensive techniques. The resulting formulation is then evaluated by tracing the logic of each strengthened coefficient. The result is a new understanding of how to build a tight formulation of the problem. We believe this suggests that it might be of interest to construct a tool for strengthening coefficients.

Dimitris Bertsimas (Massachusetts Institute of Technology),
Daniel Bienstock (Columbia University),
Adam Letchford (Lancaster University),
George L. Nemhauser (Georgia Institute of Technology),
Robert Weismantel (Otto-von-Guericke-University of Magdeburg)
Roundtable discussion
1. Funding issues
      Is IP research still fundable?
      Differences between US and Europe
2. Raising IP's profile
      Does the profile need to be raised? If so, how?     
      New application areas?
3. Cultivating a research community
      How to increase collaboration
      Differences between US and Europe
4. IP research directions—What are "the next big ideas?"
5. IP education
6. The next conference?
      Does this conference have its own niche? (IPCO/MPS/etc.)
Daniel Bienstock (Columbia University) Applying discrete optimization to robust power grid problems
Abstract: During the past decade several major power blackouts affected North America, Europe and South America. It is quite likely (in fact, expected) that more serious events will take place in the future, with potentially very damaging consequences to economies and public health. Rather than being the result of particular economic or operational factors, the blackouts can be seen as caused by the inherent complexity entailed by modern transmission networks, which comprise thousands of nodes and links and span very large geographical areas.

In this talk we will describe ongoing work on solving a number of optimization models related to the design, maintenance and operation of electrical power transmission networks. This is joint work with Sara Mattia (Rome).

Miguel Constantino (Universidade de Lisboa) A special case of the integer single node flow set with upper bounds
Abstract: In this talk we discuss the polyhedral structure of the convex hull of the integer single node flow set with two possible values for the upper bounds on the arc flows. These mixed integer sets may arise as substructure of more complex mixed integer sets that model the feasible solutions of real application problems such as network design, location and lotsizing. We give a complete description of this special integer single node flow polyhedron based on the generalization of the description of the integer single node flow polyhedron with two arcs. All the coefficients of the facet-defining inequalities can be computed in polynomial time adapting a known algorithm from Hirschberg and Wong (1976) for the two integer knapsack problem. We report on computational experience. Joint work with Agostinho Agra.
Friedrich Eisenbrand (Max-Planck-Institut fuer Informatik) Split cuts and the stable set polytope of quasi-line graphs
Abstract: Edmonds showed in 1965 that the convex hull of all matchings of a graph can be obtained by applying one round of Gomory-Chv'atal cutting planes to the fractional matching polytope. More precisely, he showed that this convex hull can be described by non-negativity, degree and odd-set constraints.

15 years later, Minty and Sbihi showed that a maximum-cardinality stable set in a claw-free graph can be computed in polynomial time, thereby generalizing Edmonds' algorithm for maximum cardinality matching. Since then, it is a long standing open problem to find an explicit description of the stable set polytope of claw-free graphs.

In this talk we show that the convex hull of stable sets of quasi-line graphs is obtainable by applying one round of split cuts. The class of quasi-line graphs is a proper superclass of line graphs and a proper subclass of claw-free graphs for which it is known that not all facets have 0/1 normal vectors. The necessary split-cuts are a generalization of Edmonds' odd-set inequalities, called clique family inequalities.

Joint work with G. Oriolo, P. Ventura and G. Stauffer.

Oktay Gunluk (IBM Corporation) Two-step MIR inequalities for mixed-integer sets
Abstract: In the first part of the talk, we use facets of simple mixed-integer sets with three variables to derive a parametric family of valid inequalities for general mixed-integer sets. We call these inequalities "two-step MIR inequalities" as they can be derived by applying the simple mixed-integer rounding (MIR) principle of Wolsey (1998) twice.

In the second part, we study the shooting experiment of Gomory which computationally identifies "important" facets of the cyclic group polyhedra. This idea has recently been re-considered by Evans (2002) and Gomory, Johnson and Evans (2003). We present computational results that suggest that MIR and two-step MIR inequalities are important.

In the last part of the talk, we present computational experience with general mixed-integer programs. Joint work with Sanjeeb Dash at IBM Research.

Jean Bernard Lasserre (LAAS-CNRS) Integerprogramming, duality and superadditive functions
Abstract: We consider the general integer program P: max {c'x : Ax=b; x nonnegative integer} which has a well-known abstract dual optimization problem stated in terms of superadditive functions. Using a linear program equivalent to P, introduced recently, we show that its dual can be interpreted as a simplified and more tractable form of the abstract dual, and identifies a subclass of superadditive functions, sufficient to consider in the abstract dual. This class of superadditive functions is also used to characterize the integer hull of the convex polytope {x : Ax=b; x nonnegative}.
Andrea Lodi (DEIS, University of Bologna) Heuristic integer (and mixed integer) linear programming
Abstract: In recent years a lot of work has been devoted to general-purpose methods for finding good heuristic solutions to Integer and Mixed Integer Linear Programs (MIPs). Some of these methods are now successfully integrated in commercial and non commercial MIP solvers. We review these results, compare some of the techniques, discuss advantages and drawbacks and we try to give a flavor of what has still to be done in the area.
Francois Margot (Carnegie Mellon University) Symmetry in integer programming
Abstract: This talk is an overview of techniques used to handle problems with symmetries. For problems modeled as integer linear programs (ILP), three essentially different and mutually exclusive approaches have been used: Reformulations, symmetry-breaking inequalities, and isomorphism pruning.

Reformulation is mostly used to handle problems where the symmetries come from the set of all permutations of a set of objects, inducing a permutation group on the variables. Some (or most) symmetries are removed from the formulations and additional branching strategies become available. The price to pay is that the reformulation has an exponential number of variables that must be handled by column generation techniques.

Adding symmetry breaking inequalities is probably the most natural way to try to handle symmetries. Several papers report strong improvements when using the best possible symmetry breaking set of inequalities. Methods for deriving such sets have been devised, but little is known about finding the most efficient set.

Isomorphism pruning is based on the theory of isomorphism-free backtracking procedure for enumeration problems. When coupled with a Branch-and-Cut algorithm, additional options for generating isomorphism-related cuts and setting variables are available. Improvements of several orders of magnitude for running time and enumeration tree size have been observed on highly symmetric 0-1 problems. Extensions of the techniques to ILP with variables bounded to a small set and to ILP corresponding to coloring problems are also available.

Sanjay Mehrotra (Northwestern University) On generalized branching methods for mixed integer programming
Abstract: We present a restructuring of the computations in Lenstra's methods for solving mixed integer linear programs. A concept of Adjoint lattices is introduced and used for this purpose. This allows us to develop branching on hyperplane algorithms in the space of original variables, without requiring any dimension reduction for pure or mixed integer programs. Reduced lattice basis are also computed in the space of original variables. Based on these results we give a new natural heuristic way of generating branching hyperplanes, and discuss its relationship with recent reformulation techniques of Aardal and Lenstra. We show that the reduced basis available at the root node has useful information on the branching hyperplanes for the generalized branch-and-bound tree. Our development allows us to give algorithms for mixed convex integer programs with properties similar to those for the mixed integer linear programs. Implementation of this algorithm in a prototype software system "IMPACT" is described. Computational results are presented on difficult knapsack and market split problems using this approach.
Gabor Pataki (University of North Carolina) Column basis reduction, decomposable knapsack and cascade problems
Abstract: We propose a very simple preconditioning method for integer programming feasibility problems: applying basis reduction to the constraint matrix, to make its columns shorter in euclidean norm, and more orthogonal. Our approach— termed column basis reduction, and abbreviated as CBR— simplifies and generalizes the reformulation technique proposed for equality constrained IPs by Aardal, Hurkens, Lenstra and others.

We describe a family of IP instances, called decomposable knapsack problems, that generalize the ones proposed by Jeroslow, Chvatal and Todd, Avis, Aardal and Lenstra, and Wolsey. We prove that 1) they need an exponential number of nodes to solve, when branch-and-bound branching on individual variables is applied; 2) after the application of column basis reduction, a constant number of nodes suffice.

A subclass of decomposable knapsack problems is called cascade problems. They were created to illustrate the surprising fact, that in hard IPs a "thin" direction is sometimes not the best to branch on. Besides having this structure, the cascade problems —despite having only one dense constraint—are as difficult for commercial MIP solvers, as the well-known marketshare problems.

Our computational study shows that most difficult IPs recently used to test nontraditional IP algorithms—subset sum, strongly correlated knapsack problems, the marketshare problems, and our cascade problems—become easy for a commercial IP solver after our preconditioning is applied. Joint work with Bala Krishnamoorthy at Washington State University.

Michael Perregaard (Dash Associates) Constraint branching and disjunctive cuts for mixed integer programs
Abstract: Several disjunctive cuts for mixed integer programs are (directly or indirectly) based on imposing a simple disjunction where a single fractional variable is required to be rounded either up or down to its nearest integer value. Two well-known cut families based on such a disjunction is Gomory's mixed integer cut and the lift-and-project cuts from the 1990s. Both cut classes involves strengthening by considering the integrality of other variables. This strengthening can be interpreted as a modification of the underlying simple disjunction. Later research into disjunctive cuts have taken this idea of strengthening the underlying disjunction even further.

The most common method for solving a mixed integer program is by branch-and-bound. Almost all such available codes branch on a single variable at a time. For general mixed integer programs, where the integer variables are allowed a wider range than simple 0-1 variables, such a simple branching scheme can often lead to an explosion in the number of nodes the code has to search. In this talk I examine the feasibility of applying the ideas for strengthening cuts to the simple branching disjunctions for the purpose of creating better mixed integer branches. Results from computational tests on a variety of public benchmark problems, using an implementation based on the Xpress-MP solver, will be used to demonstrate the effects of such strengthened branches.

Vincent Poor (Princeton University) Energy efficiency in multiple-access wireless networks: Nash equilibria in power control games
Abstract: The energy efficiency (measured in bits-per-Joule) of multiple-access wireless data networks is considered via the behavior of Nash equilibria in non-cooperative power control games. Particular issues considered include the effects of multiuser detection and multiple antennas on energy efficiency, energy efficient carrier loading in multi-carrier CDMA systems, and the effects of delay constraints on energy efficiency. Some open problems of interest are also discussed.
Ed Rothberg (ILOG, Inc.) It's a beautiful day in the neighborhood—Local search in mixed integer programming
Abstract: Mixed integer programming and local search have experienced only a few chance meetings over the past 20 years, despite a clear overlap in the problem classes to which they are applied. This situation has changed recently, with notions from local search being successfully applied in the solution of a fairly broad class of MIP models. This talk will consider several approaches to integrating the technologies, presenting computational results for these approaches on a set of practical problems.
Juan-Jose Salazar-Gonzalez (Universidad de La Laguna) Solving mixed integer programs arising in statistical data editing
Abstract: National Statistical Agencies needs automatic tools for detecting errors in records not satisfying a set of consistency rules. The topic is known as Statistical Data Editing, and a very interesting Optimization Problem is the so-called Error Localization Problem. It concerns finding the minimum number of fields in an invalid record such that by modifying these values the new record satisfies all the rules. It is an NP-hard problem because the "Minimum Weight Solution to Linear Equations" is a particular case. Also the Error Localization Problem is very important in Signal Processing (the problem is then called "Basis Selection Problem"), where information must be encoded and sent, or received and decoded, through a Telecommunication Network.

We present an exact method, based on a Benders' decomposition approach, solving instances with up to 100 fields and 40 edits. We also produce a variant of this approach to solve heuristically larger instances. Some procedures of this descending search make use of the Farkas' Lemma in Linear Programming. Computational experience on randomly generated instances shows that the approach can deal with instances of up to 1000 fields and 400 edits.

The generality of the consistency rules makes the Error Localization Problem very close to a general Mixed Integer Programming. Still, there is some structure. Therefore, we will open a discussion to the audience on how new results in Mixed Integer Programming could help solving Error Localization Problems, and viceversa!

This is part of a joint research work with Jorge Riera-Ledesma, University of La Laguna, Tenerife, Spain.

Martin Savelsbergh (Georgia Institute of Technology) The Dial-a-Flight-Problem
Abstract: Almost 3,000 businesses in the United States provide on-demand air charter services. The on-demand air charter industry provides a vital transportation link for medical services, important cargo needed to promote commerce, and personal travel supporting the growth of the economy. The companies use smaller aircraft to meet the customized needs of the traveling public for greater flexibility in scheduling and access to almost every airport in the country. Flights are planned according to the customer's schedule, not the operator's.

DayJet Inc. is a startup company in this space that will soon provide air taxi services. There are obvious advantages to an air taxi system. More than 1.5 million people board commercial airliners each day. Most fly with hundreds of other passengers to and from a limited number of major "hub" airports that are heavily congested and often located many miles from their homes and final destinations. Missed connections and flight delays add to their frustrations. An air-taxi system gives travelers the option of using small jets that fly to and from less-congested outlying airports, without packed parking lots, long lines at security checkpoints, flight delays, and lost luggage, that are closer to where they live and where they want to go. While commercial flight service now exists at only about 550 airports in the United States, air taxis will be able to land at 5,000 of the nation's 14,000 public and private runways. And all that at comparable fares.

A key challenge in setting up an air taxi system is the development of a scheduling engine that takes requests for transportation and schedules planes and pilots in a cost effective way to satisfy these requests. The dial-a-flight problem captures the essential characteristics of the scheduling problems encountered by an air taxi service.

The dial-a-flight problem is concerned with the scheduling of a set of passenger reservations for air transportation during a single day. A reservation specifies an origin airport, an earliest acceptable departure time at the origin, a destination airport, and a latest acceptable arrival time at the destination. A fleet of airplanes operable by a single pilot is available to provide the requested air transportation. Each airplane has a home base, is available for a certain period during the day, and returns home at the end of the day. A set of pilots, stationed at the home bases of the airplanes, is available to fly the airplanes. A pilot departs from the home base where he is domiciled at the start of his duty and returns to the home base where he is domiciled at the end of his duty. A pilot schedule has to satisfy FAA regulations governing flying hours and duty period, i.e., a single pilot cannot fly more than 8 hours in a day and his duty period cannot be more than 14 hours. To ensure acceptable service a passenger itinerary will involve at most two flights, i.e., a single intermediate stop is allowed. A turnaround time at an airport, i.e., the minimum time between an arrival at an airport and the next departure, is given. The objective is to minimize the costs, while satisfying all requests. A dispatcher has to decide which planes and pilots to use to satisfy the reservations and what the plane and pilots itineraries will be, i.e., the flight legs and associated departure times.

We present a variety of optimization approaches for the solution of the dial-a-flight problem.

In our time-discretized integer multicommodity network flow model, the key events from the perspective an airplane are modeled, e.g., arrival at an airport, dropping off passengers at the airport, preparing for the next flight (which one depends on whether there were "indirect" passengers on board), loading new direct flight passengers, and loading new indirect flight passengers. To keep the size of the model within acceptable limits a flexible concept of time-discretization has been designed and implemented. Each airplane has its own time-discretization and the number of time instants as well as their values are completely flexible. This flexibility is crucial, because we extensively employ dominance relations between itineraries to reduce the network size. In our column generation formulation, reservations are represented by rows and plane itineraries are represented by columns. The multicommodity flow model is modified to solve the pricing problem. A customer constrained shortest path algorithm is developed for its solution. Specialized branching schemes are employed in a branch-and-price approach to identify high quality schedules.

Joint work with... Mo Bazaraa, Daniel Espinoza, Renan Garcia, Marcos Goycoolea, George Nemhauser : Georgia Tech Emilie Danna and Zonghau Gu : ILOG, Inc. Alex Khmelnitsky and Eugene Taits : DayJet, Inc.

Eduardo Uchoa (Universidade Federal Fluminense) Robust branch-and-cut-and-price for the capacitated minimum spanning tree problem
Abstract: We propose a new formulation for the capacitated minimum spanning tree problem that leads to a robust branch-and- cut-and-price algorithm. The formulation allows the use of cuts expressed over a very large set of variables, without changing the pricing subproblem or increasing the size of LPs that are actually solved. Cuts over those variables can be quite strong, and generalize many previous know families of cuts, including capacity, root cutsets and multistars. Computation results on benchmark instances from the OR-Library show very significant improvements over previously known algorithms, specially on non-unitary weight instances.

Joint work with D.Andrade, R.Fukasawa, J.Lysgaard and M.Poggi de Aragao.

Francois Vanderbeck (Universite de Bordeaux 1) Branching in branch-and-price algorithms
Abstract: In Branch-and-Price algorithms, implementing the branching scheme can be challenging. Branching constraints may imply modifications to the pricing problem. This is a main concern for the development of a generic branch-and-price code that should run using only the pricing oracle provided by the user. The issue has not stop people from using Branch-and-Price. Firstly, branching is straightforward for many applications (we shall characterize the class of problem for which this is the case). Then, Ryan and Foster (1981) proposed a scheme for applications that can be reformulated as a set covering problem. Beyond that, a general scheme was presented by Vanderbeck (2000) but it may result in significant modifications to the pricing problem. An alternative is the scheme of Villeneuve et al. (2003) that consists in applying branching in the original formulation, but this introduces symmetry in the Dantzig-Wolfe reformulation when the problem structure involves several identical blocks. The branching scheme presented here builds on the aboves. It can be can be implemented using only the oracle provided for the original pricing problem. Branching constraints are not dualized in a Lagrangian way but are convexified in the subproblem.
Xiaodong Wang (Columbia University) Optimization of IEEE 802.11 DCF based on Bayesian estimation of the number of competing terminals
Abstract: The performance of the Distributed Coordination Function (DCF) of the IEEE 802.11 protocol has been shown to heavily depend on the number of terminals accessing the distributed medium. The DCF uses a carrier sense multiple access scheme with collision avoidance (CSMA/CA) where the backoff parameters are fixed and determined by the standard. While those parameters were chosen to provide a good protocol performance under light loads, they fail to provide an optimum utilization of the channel in many scenarios. In particular, under heavy load scenarios, the utilization of the medium can drop tenfold. Most of the optimization mechanisms proposed in the literature are based on adapting the DCF backoff parameters to the estimate of the number of competing terminals in the network. However, existing estimation algorithms are either inaccurate or too complex. In this paper we propose an enhanced version of the IEEE 802.11 DCF that employs an adaptive estimator of the number of competing terminals based on sequential Monte Carlo methods. The algorithm uses a Bayesian approach, optimizing the backoff parameters of the DCF based on the predictive distribution of the number of competing terminals. We show that our algorithm is simple yet highly accurate even at small time scales. We implement our proposed new DCF in the ns-2 simulator and show that it outperforms existing methods. We also show that its accuracy can be used to improve the results of the protocol even when the nodes are not in saturation mode. Moreover, we show that there exists a Nash equilibrium strategy that prevents rogue nodes from changing their parameters for their own benefits, making the algorithm applicable in a complete distributed fashion without having to modify the standard or the existing base stations.
Robert Weismantel (Otto-von-Guericke-University of Magdeburg) Mixed integer polynomial programming
Abstract: This talk deals with mixed integer optimization problems defined by linear constraints and a polynomial function as the objective function. We present motivating examples, illustrate techniques that reduce the problem to a mixed integer linear program and discuss complexity results. An algorithm is presented that is based on Barvinok's rational function theory, i.e., lattice points in polyhedra are encoded through rational functions. It turns out that under the assumption that the number of variables is fixed, our algorithm leads to a fully polynomial time approximation scheme. The results of this talk are based on joint work with Raymond Hemmecke, Matthias Koeppe and Jesus De Loera.
Laurence Wolsey (Universite Catholique de Louvain) A basic mixed integer set: the mixing set and its applications
Abstract: Very little is known about the polyhedral structure of even simple mixed integer programs. Here we study a very simple set, called the mixing set. This set and valid inequalities for it were proposed by Gunluk and Pochet in an effort to explain and understand why the same procedure of "mixing mixed integer rounding (MIR) inequalities" gave valid inequalities for many different variants of the constant capacity lot-sizing problem, and subsequently Miller and Wolsey took this abstraction a little further by considering the intersection of mixing sets plus certain additional constraints.

In this talk we pursue this effort at abstraction by considering two "abstract sets" that are generalizations of the mixing set. We show that, modulo a slight restriction, the convex hulls of both sets are obtained with mixing inequalities. This is joint work with Michele Conforti and Marco Saturni.

Turning back to lot-sizing, we show that a constant capacity problem with production time windows, and surprisingly both a multi-item problem with a joint set-up variable, and a class of single item problems with varying capacities can also be solved by mixing. The latter is joint work with Yves Pochet.

(PDF file with formulations is available).

Ismael de Farias (State University of New York - Buffalo) Branch-and-cut for cardinality constrained optimization
Abstract: Given a set of continuous variables and for each variable a constant, a cardinality constraint requires that no less than a specified number of variables is equal to their corresponding constants. Cardinality constraints appear in several applications, such as feature selection in data mining. I will present a polyhedral study of problems with cardinality constraints and a branch-and-cut approach to solve them. In particular, I will present a few unusual properties of these polyhedra.

Joint work with Ming Zhao.

Sven de Vries (Technische Universität München) Faster separation of 1-wheel inequalities for stable set polytopes
Abstract: For the solution of hard integer programs with branch-and-cut algorithms it is a necessity to check during the separation phase for violated inequalities of the stable set relaxation of the instances conflict graph. These conflict graphs turn out to be sparse. For instance the majority (39/60) of the new and difficult MIPLIB2003 integer programs contain large substructures with constraints of type xi 1 for binary variables.

A stable set in a graph G=(V,E) is a set of pairwise nonadjacent vertices. A common approach for finding a maximum weight stable set of G is to optimize over the convex hull STAB(G) of the incidence vectors of stable sets; this approach requires knowledge of strong valid inequalities and algorithms to separate them. We present an O(|V|2|E|+|V|3log |V|) separation algorithm for the nonsimple 1-wheel inequalities (Cheng and Cunningham, 1995), which is faster than the previously known O(|V|4) algorithm. In particular this is faster for the sparse instances coming from the conflict graphs of general integer programs.

Visitors in Residence
Tobias Achterberg Zuse Institute Berlin 7/24/2005 - 7/31/2005
Rajeev Agrawal Motorola, Inc. 6/26/2005 - 7/1/2005
Shabbir Ahmed Georgia Institute of Technology 7/24/2005 - 7/29/2005
In Soo Ahn Bradley University 6/21/2005 - 7/1/2005
Edoardo Amaldi Politecnico di Milano 7/23/2005 - 7/30/2005
Kent Andersen Carnegie Mellon University 7/24/2005 - 7/29/2005
Matthew Andrews Lucent Technologies 6/26/2005 - 7/1/2005
Paul Anghel University of Minnesota 6/22/2005 - 7/1/2005
D. Gregory Arnold Air Force Research Laboratory 7/31/2005 - 8/10/2005
Douglas N. Arnold University of Minnesota 7/15/2001 - 8/31/2006
Donald G. Aronson University of Minnesota 9/1/2002 - 8/31/2005
Festus Asemota University of Benin 6/20/2005 - 7/3/2005
Alper Atamturk University of California - Berkeley 7/24/2005 - 7/29/2005
Pasquale Avella Universita del Sannio 7/24/2005 - 7/29/2005
Gerard Awanou University of Minnesota 9/2/2003 - 8/31/2005
Francois Baccelli Ecole Normale Superieure 6/26/2005 - 7/1/2005
Egon Balas Carnegie Mellon University 7/23/2005 - 7/29/2005
Katherine Bartley University of Nebraska - Lincoln 7/31/2005 - 8/10/2005
Pietro Belotti Polytecnic of Milan 7/24/2005 - 7/29/2005
Saifallah Benjaafar University of Minnesota 7/25/2005 - 7/29/2005
Nicholas Bennett Schlumberger-Doll Research 7/31/2005 - 8/10/2005
Dimitris Bertsimas Massachusetts Institute of Technology 7/24/2005 - 7/29/2005
Ian Besse University of Iowa 7/31/2005 - 8/10/2005
Sagar Bhatt Rice University 7/31/2005 - 8/10/2005
Daniel Bienstock Columbia University 7/24/2005 - 7/29/2005
Robert E. Bixby Rice University 7/24/2005 - 7/29/2005
Henry A. Boateng University of Michigan 7/31/2005 - 8/10/2005
Maurizio Boccia University of Sannio 7/25/2005 - 7/31/2005
Alexander Bockmayr LORIA 7/24/2005 - 7/29/2005
Pierre Bonami Carnegie Mellon University 7/24/2005 - 7/29/2005
Sem C. Borst Lucent Technologies - Bell Laboratories 6/26/2005 - 7/1/2005
Maury Bramson University of Minnesota 6/22/2005 - 7/1/2005
Richard J. Braun University of Delaware 7/31/2005 - 8/10/2005
Robert Buche North Carolina State University 6/21/2005 - 7/1/2005
Patrick Campbell Los Alamos National Laboratory 7/31/2005 - 8/10/2005
Tamra Carpenter Telcordia Technologies 7/24/2005 - 7/29/2005
Juan Pablo Vielma Centeno Georgia Institute of Technology 7/23/2005 - 7/30/2005
Manoj Chari SAS Institute Inc. 7/24/2005 - 7/29/2005
Dov Chelst DeVry University 6/21/2005 - 7/3/2005
Pengwen Chen University of Florida 7/31/2005 - 8/11/2005
Qianyong Chen University of Minnesota 9/1/2004 - 8/31/2006
Julianne Chung Emory University 7/31/2005 - 8/10/2005
Kenneth L. Clarkson Bell Laboratories 6/26/2005 - 7/1/2005
Cristina Comaniciu Stevens Institute of Technology 6/26/2005 - 7/1/2005
Miguel Constantino Universidade de Lisboa 7/24/2005 - 7/29/2005
William Cook Georgia Institute of Technology 7/24/2005 - 7/29/2005
Gerard P. Cornuejols Carnegie Mellon University 7/24/2005 - 7/29/2005
Neiyer S. Correal Motorola 6/22/2005 - 7/1/2005
Chuangyin Dang City University of Hong Kong 7/24/2005 - 7/29/2005
Shilpa Das Gupta Mississippi State University 7/31/2005 - 8/10/2005
Sanjeeb Dash IBM Corporation 7/24/2005 - 7/29/2005
Nasser Dastrange Buena Vista University 7/24/2005 - 7/30/2005
Ismael de Farias State University of New York - Buffalo 7/24/2005 - 7/29/2005
Antonio DeSimone SISSA-Italy 3/10/2005 - 7/15/2005
Sven de Vries Technische Universität München 7/24/2005 - 7/29/2005
Brian DiDonna University of Minnesota 9/1/2004 - 8/31/2006
Jonathan Eckstein Rutgers 7/24/2005 - 7/29/2005
Kossi Delali Edoh Elizabeth City State University 6/21/2005 - 7/1/2005
Martin Eiger Telcordia Technologies 6/26/2005 - 7/1/2005
Friedrich Eisenbrand Max-Planck-Institut fuer Informatik 7/23/2005 - 7/29/2005
Valjean Elander University of Nevada - Las Vegas 7/31/2005 - 8/10/2005
Malena Espanol Tufts University 7/31/2005 - 8/10/2005
Daniel Espinoza Georgia Institute of Technology 7/24/2005 - 7/30/2005
Qirong Fang Purdue University 7/31/2005 - 8/10/2005
Shahrokh Farahmand University of Minnesota 6/22/2005 - 7/1/2005
Petri Fast Lawrence Livermore National Laboratories 7/31/2005 - 8/10/2005
Harshini Fernando Texas Tech University 7/31/2005 - 8/10/2005
Matthew Galati SAS Institute Inc. 7/23/2005 - 7/29/2005
Renan Garcia Georgia Institute of Technology 7/24/2005 - 7/25/2005
Tim Garoni University of Minnesota 8/25/2003 - 8/31/2005
Georgios Giannakis University of Minnesota 6/21/2005 - 7/1/2005,
7/25/2005 - 7/29/2005
Marcus Guzman Goycoolea Georgia Institute of Technology 7/24/2005 - 7/30/2005
Martin Greiner Siemens 6/25/2005 - 7/2/2005
Zonghao Gu ILOG, Inc. 7/24/2005 - 7/29/2005
Yongpei Guan Georgia Institute of Technology 7/24/2005 - 7/29/2005
Oktay Gunluk IBM Corporation 7/24/2005 - 7/29/2005
Katherine Guo Bell Laboratories 6/26/2005 - 7/3/2005
Diwakar Gupta University of Minnesota 7/25/2005 - 7/29/2005
Rohit Gupta University of Minnesota 6/22/2005 - 7/1/2005,
7/24/2005 - 7/29/2005
Kkmal Hammouda University of Minnesota 6/22/2005 - 7/1/2005
Chuan-Hsiang Han University of Minnesota 9/1/2004 - 8/31/2005
John Harlim University of Maryland 7/31/2005 - 8/10/2005
Nidhi Hegde France Telecom 6/21/2005 - 7/1/2005
Alfa Heryudono University of Delaware 7/31/2005 - 8/10/2005
Illya Hicks Texas A & M University 7/24/2005 - 7/29/2005
John Hobby Bell Laboratories 6/26/2005 - 7/1/2005
Jennie Hu SAS Institute Inc. 7/25/2005 - 7/29/2005
Mark Iwen University of Michigan 7/31/2005 - 8/10/2005
Syed Ali Jafar University of California - Irvine 6/22/2005 - 7/1/2005
Arulsaravana Jeyaraj University of California - Irvine 6/21/2005 - 7/1/2005
Chuanyi Ji Georgia Institute of Technology 6/22/2005 - 7/1/2005
Xiaoyun Ji Rensselaer Polytechnic Institute 7/23/2005 - 7/29/2005
Lijian Jiang Texas A & M University 7/31/2005 - 8/11/2005
Chao Jin University of Colorado - Boulder 7/31/2005 - 8/11/2005
Yasong Jin University of Kansas 6/21/2005 - 7/1/2005
Nihar Jindal University of Minnesota 6/22/2005 - 7/2/2005
Ellis Johnson Georgia Institute of Technology 7/25/2005 - 7/29/2005
Sookyung Joo University of Minnesota 9/1/2004 - 8/31/2006
Chiu Yen Kao University of Minnesota 9/1/2004 - 8/31/2006
Miroslav Karamanov Carnegie Mellon University 7/24/2005 - 7/29/2005
Mostafa Kaveh University of Minnesota 6/22/2005 - 7/1/2005
Edward Keyes Semiconductor Insights 7/31/2005 - 8/10/2005
Erica Zimmer Klampfl Ford Motor Company 7/24/2005 - 7/29/2005
Thorsten Koch Zuse Institute Berlin 7/24/2005 - 7/29/2005
Soumitri Kolavennu Honeywell 6/26/2005 - 7/1/2005
Richard Kollar University of Minnesota 9/1/2004 - 8/31/2005
Arie Koster Zuse Institute Berlin 7/23/2005 - 7/29/2005
Gerhard Kramer Lucent Technologies 6/26/2005 - 7/1/2005
Komandur R. Krishnan Telcordia Technologies 6/27/2005 - 7/1/2005
Simge Kucukyavuz University of Arizona 7/25/2005 - 7/29/2005
Matthias Kurzke University of Minnesota 9/1/2004 - 8/31/2006
Harold J. Kushner Brown University 6/26/2005 - 7/1/2005
Spyros Kyperountas Motorola 6/26/2005 - 7/1/2005
Richard La University of Maryland 6/27/2005 - 7/1/2005
Laszlo Ladanyi IBM Corporation 7/24/2005 - 7/29/2005
Yongzeng George Lai Wilfrid Laurier University 7/10/2005 - 7/16/2005
Jean Bernard Lasserre LAAS-CNRS 7/25/2005 - 7/30/2005
Chulhan Lee University of Texas - Austin 6/22/2005 - 7/2/2005
Eva K. Lee Georgia Institute of Technology 7/24/2005 - 7/29/2005
Jon Lee IBM Corporation 7/24/2005 - 7/29/2005
Frederic Legoll University of Minnesota 9/3/2004 - 8/1/2006
Joel Lepak University of Michigan 7/31/2005 - 8/10/2005
Adam Letchford Lancaster University 7/23/2005 - 7/28/2005
Debra Lewis University of Minnesota 7/15/2004 - 8/31/2006
Xiantao Li University of Minnesota 8/3/2004 - 8/14/2005
Yan Li Texas A & M University 7/31/2005 - 8/11/2005
Yanjun Li Purdue University 7/24/2005 - 7/29/2005
Jeff Linderoth Lehigh University 7/24/2005 - 7/29/2005
Xin Liu University of California - Davis 6/22/2005 - 7/1/2005
Yuanjin Liu Wayne State University 6/22/2005 - 7/1/2005
Andrea Lodi DEIS, University of Bologna 7/24/2005 - 7/29/2005
David Love Purdue University 6/25/2005 - 7/1/2005
Steven Low California Institute of Technology 6/26/2005 - 7/1/2005
Marco Luebbecke Technical University of Berlin 7/24/2005 - 7/29/2005
James Luedtke Georgia Institute of Technology 7/23/2005 - 7/30/2005
Tom Luo University of Minnesota 6/26/2005 - 7/1/2005
Francois Margot Carnegie Mellon University 7/24/2005 - 7/29/2005
Sara Mattia Universita di Roma "La Sapienza" 7/23/2005 - 7/30/2005
Sanjay Mehrotra Northwestern University 7/24/2005 - 7/29/2005
Sophie Michel Universite de Bordeaux 1 7/24/2005 - 7/29/2005
Andrew Miller University of Wisconsin 7/24/2005 - 7/29/2005
Lisa A. Miller University of Minnesota 7/24/2005 - 7/29/2005
Wei Mo Iowa State University 6/22/2005 - 7/1/2005
Jae Moon University of Minnesota 6/22/2005 - 7/1/2005
Jayoung Nam Indiana University 7/31/2005 - 8/10/2005
Vishnu Narayanan University of California - Berkeley 7/24/2005 - 7/30/2005
Arnie Neidhardt Telcordia Technologies 6/21/2005 - 7/1/2005
George L. Nemhauser Georgia Institute of Technology 7/24/2005 - 7/29/2005
Mahdi Nezafat University of Minnesota 6/22/2005 - 7/1/2005
Gabor Pataki University of North Carolina 7/24/2005 - 7/29/2005
Michael Perregaard Dash Associates 7/24/2005 - 7/29/2005
Peter Philip University of Minnesota 8/22/2004 - 8/31/2006
Cynthia A. Phillips Sandia National Laboratories 7/24/2005 - 7/29/2005
Vincent Poor Princeton University 6/30/2005 - 7/1/2005
Lea Popovic University of Minnesota 9/2/2003 - 8/31/2005
Alexandre Proutiere France Telecom 6/21/2005 - 7/2/2005
Deepak Rajan IBM Corporation 7/24/2005 - 7/31/2005
Ted Ralphs Lehigh University 7/24/2005 - 7/29/2005
Jorge M. Ramirez Oregon State University 7/31/2005 - 8/10/2005
Priya Ranjan Intelligent Automation, Inc. 6/21/2005 - 7/1/2005
Jean-Philippe P. Richard Purdue University 7/24/2005 - 7/29/2005
Robert Ronkese University of Delaware 7/31/2005 - 8/11/2005
David S. Ross Kaiser Permanente 7/31/2005 - 8/10/2005
Fabrizio Rossi University of L'Aquila 7/24/2005 - 7/30/2005
Ed Rothberg ILOG, Inc. 7/24/2005 - 7/29/2005
John Sabino Rice University 7/31/2005 - 8/10/2005
Juan-Jose Salazar-Gonzalez Universidad de La Laguna 7/23/2005 - 7/30/2005
Rina Santos University of Nevada - Las Vegas 7/31/2005 - 8/10/2005
Martin Savelsbergh Georgia Institute of Technology 7/24/2005 - 7/29/2005
Anureet Saxena Carnegie Mellon University 7/25/2005 - 7/29/2005
Arnd Scheel University of Minnesota 7/15/2004 - 8/31/2006
Christian Scheideler Johns Hopkins University 6/26/2005 - 7/2/2005
Suvrajeet Sen National Science Foundation 7/24/2005 - 7/29/2005
David Shallcross Telcordia Technologies 7/24/2005 - 7/29/2005
Shagi-Di Shih University of Wyoming 5/1/2005 - 7/2/2005
Rahul Sinha Illinois Institute of Technology 6/21/2005 - 7/1/2005
Stefano Smriglio University of L'Aquila 7/24/2005 - 7/30/2005
Valery P. Smyshlyaev University of Bath-UK 4/10/2005 - 7/2/2005
Joao Luis Cardoso Soarees Universidade de Coimbra 7/24/2005 - 7/30/2005
Qingshuo Song Wayne State University 6/22/2005 - 7/1/2005,
7/31/2005 - 8/10/2005
Kevin William Sowerby University of Auckland 6/21/2005 - 7/2/2005
Skyler Speakman University of Kentucky 7/31/2005 - 8/10/2005
David St John University of Illinois - Chicago 7/31/2005 - 8/10/2005
Dharmashankar Subramanian Honeywell 7/25/2005 - 7/29/2005
Jun Tan Motorola 6/21/2005 - 7/1/2005
Choon Yik Tang Honeywell 6/26/2005 - 7/1/2005
Mohit Tawarmalani Purdue University 7/24/2005 - 7/30/2005
Alain B. Tchagang University of Minnesota 6/22/2005 - 7/1/2005
David Tello Arizona State University 7/31/2005 - 8/10/2005
Ahmed Tewfik University of Minnesota 6/20/2005 - 7/8/2005
Eduardo Uchoa Universidade Federal Fluminense 7/24/2005 - 7/30/2005
Eric van den Berg Telcordia Technologies 6/26/2005 - 7/1/2005
Dieter Vandenbussche University of Illinois - Urbana-Champaign 7/24/2005 - 7/29/2005
Francois Vanderbeck Universite de Bordeaux 1 7/24/2005 - 7/29/2005
Mathieu Van Vyve University Libre de Bruxelles 7/24/2005 - 7/30/2005
Paula Andrea Vasquez University of Delaware 7/31/2005 - 8/10/2005
Pascal Olivier Vontobel University of Wisconsin - Madison 6/21/2005 - 7/2/2005
Fan Wang Motorola 6/21/2005 - 7/1/2005
Lei Wang University of Michigan 7/31/2005 - 8/10/2005
Xiaodong Wang Columbia University 6/26/2005 - 7/1/2005
Zhengdao Wang Iowa State University 6/22/2005 - 7/1/2005
Robert Weismantel Otto-von-Guericke-University of Magdeburg 7/23/2005 - 7/29/2005
Thomas Williams Mississippi State University 7/31/2005 - 8/11/2005
Laurence Wolsey Universite Catholique de Louvain 7/24/2005 - 7/29/2005
Wing Shing Wong Chinese University of Hong Kong 6/26/2005 - 7/1/2005
Doug Wright University of Minnesota 2/15/2005 - 8/31/2005
Chai Wah Wu IBM Corporation 7/31/2005 - 8/10/2005
Dapeng Wu University of Florida 6/27/2005 - 7/2/2005
Jinhong Wu George Washington University 6/21/2005 - 7/1/2005
Yu Xia The Institute of Statistical Mathematics 7/24/2005 - 7/29/2005
Yan Xu SAS Institute Inc. 7/24/2005 - 7/29/2005
Chuan Xue University of Minnesota 7/31/2005 - 8/10/2005
Yunjung Yi Honeywell 6/26/2005 - 7/1/2005
George Yin Wayne State University 6/21/2005 - 7/1/2005
Emmanuel Yomba University of Ngaoundéré 10/6/2004 - 8/31/2005
Yingqun Yu University of Minnesota 6/27/2005 - 7/1/2005
Hossein Zare University of Minnesota 6/22/2005 - 7/1/2005
Ofer Zeitouni University of Minnesota 6/26/2005 - 7/1/2005
Guoqing Zhang University of Windsor 7/27/2005 - 7/29/2005
Muhong Zhang University of California - Berkeley 7/24/2005 - 7/29/2005
Qian Zhang University of Wisconsin - Madison 6/21/2005 - 7/2/2005
Qing Zhang University of Georgia 6/26/2005 - 7/2/2005
Ming Zhao State University of New York - Buffalo 7/24/2005 - 7/29/2005
Legend: Postdoc or Industrial Postdoc Long-term Visitor

Participating Institutions: Carnegie Mellon University, Consiglio Nazionale delle Ricerche (CNR), Georgia Institute of Technology, Indiana University, Iowa State University, Kent State University, Lawrence Livermore National Laboratories, Los Alamos National Laboratory, Michigan State University, Mississippi State University, Northern Illinois University, Ohio State University, Pennsylvania State University, Purdue University, Rice University, Sandia National Laboratories, Seoul National University (BK21), Seoul National University (SRCCS), Texas A & M University, University of Chicago, University of Cincinnati, University of Delaware, University of Houston, University of Illinois - Urbana-Champaign, University of Iowa, University of Kentucky, University of Maryland, University of Michigan, University of Minnesota, University of Notre Dame, University of Pittsburgh, University of Texas - Austin, University of Wisconsin, University of Wyoming, Wayne State University
Participating Corporations: 3M, Boeing, Corning, ExxonMobil, Ford Motor Company, General Electric, General Motors, Honeywell, IBM Corporation, Johnson & Johnson, Lockheed Martin, Medtronic, Inc., Motorola, Schlumberger-Doll Research, Siemens, Telcordia Technologies