DIMACS Center, CoRE Building (Room 431), Rutgers University, Busch Campus, Piscataway, NJ

**George Nemhauser**, Georgia Tech**Martin Savelsbergh**, Georgia Tech

1. TITLE On the Solution of Traveling Salesman Problems SPEAKER Bill Cook AFFILIATION Rice University ABSTRACT Following the theoretical studies of J.B. Robinson and H.W. Kuhn in the late 1940s and the early 1950s, G.B. Dantzig, R. Fulkerson, and S.M. Johnson demonstrated in 1954 that large instances of the TSP could be solved by linear programming. Their approach remains the only known tool for solving TSP instances with more than several hundred cities; over the years, it has evolved further through the work of M. Grotschel, S. Hong, M. Junger, P. Miliotis, D. Naddef, M. Padberg, W.R. Pulleyblank, G. Reinelt, G. Rinaldi, and others. We describe some of its refinements that led to the solution of a 13,509-city instance. This talk is based on joint work with David Applegate, Robert Bixby, and Vasek Chvatal. 2. TITLE: Solving aircraft maintenance scheduling problems SPEAKER: Daniel Bienstock AFFILIATION: Columbia University, New York ABSTRACT: A common problem faced by airlines is that of scheduling long-term maintenance cycles for the aircraft in their fleet. Maintenance must be scheduled at periodic intervals and follows a structured pattern. Moreover, maintenance is time-consuming (a single "check" may require several weeks during which the aircraft is unavailable), is expensive and it also consumes other resources -- as a result, an airline does not have unlimited maintenance capacity at any given time. In fact, maintenace capacity can be quite tight, and typically one may hasten a maintenance check (or delay it, within allowable bounds). At the same time, enough aircraft must be available at any one time to meet forecast demand. Finally, as aircraft age they can be sold (or returned, in the case of leased planes) and this must also be taken into account in a long-term plan. We consider an integer programming model to tackle the type of problem just described, and present some cutting-planes and a strategy for obtaining good solutions for this model. On real-life instances of the problem (involving several dozen planes and a planning horizon of a few years) our approach yields solutions that are within 3% to 5% of the optimum. 3. TITLE: The Prize Collecting Steiner Tree Problem SPEAKER: David S. Johnson, AFFILIATION: AT&T Labs ABSTRACT: In the prize collecting Steiner tree problem, we are given a weighted graph, with the weights on the edges being "costs" and the weights on the vertices being "prizes." This is a bicriteria problem in which one wants to find a subtree of the graph with low total cost and high total prize. It has potential applications to the design of local access networks for telecommunication. Goemans and Williamson have proposed a primal-dual approximation algorithm for minimizing the sum of the edge costs plus the sum of the prizes NOT included in the tree, and proved that it is guaranteed to come within a factor of 2 of the optimal for this objective function. In this talk we describe the Goemans-Williamson algorithm and some of its variants, as well as a branch-and-cut algorithm for finding the optimal solution to the problem. We then report on results of an experimental study evaluating the effectiveness of the Goemans- Williamson algorithm and its variants in practice for a wide variety of instances. This is a progress report on ongoing joint work with Howard Karloff, Abilio Macena, Maria Minkoff, Mauricio Resende, and Steven Phillips. 4. TITLE Approximation algorithms via linear programming: rounding algorithms SPEAKER David Shmoys AFFILIATION Cornell University ABSTRACT One of the most well-studied approaches to computing good solutions to hard combinatorial optimization problems consists of (1) formulating the problem as an integer program; (2) solving the linear programming relaxation of this integer program; and (3) rounding the optimal fractional solution to an integer one that is nearly as good. There have been a number of significant advances in the design of approximation algorithms, polynomial-time algorithms with an associated performance guarantee, based on this philosophy. Furthermore, experiemental results that rely on some of these results have provided evidence that the mathematical insights gained can have more than just a theoretical role to play. We shall survey several recent results on approximation algorithms for facility location and scheduling problems. 5. TITLE: BC-PROD and LOTSIZELIB SPEAKER: Laurence A. Wolsey AFFILIATION: CORE, Universite Catholique de Louvain ABSTRACT: BC-PROD, a specialised branch-and-cutsystem for production planning problems involving lot-sizing, and LOTSIZELIB, a recently created library of lot-sizing instances including mathematical problem descriptions, models in a standard LP modelling language and matrices, are presented. Extensions to BC-PROD and the development of a similar system for network design are then discussed. This is joint work with G. Belvaux. Finally we present new modelling results for lot-sizing with sales due to M. Loparic and Y. Pochet 6. TITLE: Optimization in IBM Manufacturing SPEAKER: Brenda Dietrich (instead of Bill Pulleyblank) AFFILIATION: IBM Thomas J. Watson Research Laboratory ABSTRACT: A variety of optimization applications are used throughout IBM Manufacturing. The business problems addressed include multi-year logistics network design, annual capacity planning, and daily production scheduling. Integer programming, linear programming, and quick-and-dirty heuristics have been used to address these problems. I will discuss some of these activities, addressing the business problem, the mathematical model and solution method, and the solution deployment process. 7. TITLE: Optimal and Approximation Algorithms for Large Scale Supply Chain Management Problems SPEAKER: David Simchi-Levi AFFILIATION: Department of Industrial Engineering and Management Sciences Northwestern University ABSTRACT: In this talk, we analyze the problems faced by companies that rely on TL (Truckload) and LTL (Less-Than-Truckload) carriers for the distribution of products across their supply chain. The goal is to design an inventory policy and a transportation strategy so as to minimize system-wide cost by taking advantage of the transportation cost structure. We propose strong LP formulations for these problems and develop structural properties for two common transportation cost functions: (i) the incremental discount, and (ii) the all-unit discount cost functions. In the former case, we model the problem using a set-partitioning approach and characterize structural properties of the resulting formulation. These properties are used to identify cases in which the linear programming relaxation of the set-partitioning formulation is tight, and to suggest an efficient algorithm. In the case of all-unit discount cost functions, we develop approximation algorithms with fixed bounds for the single warehouse lot sizing problem. We also developed a randomized algorithm for the single warehouse, multi-retailer model when the warehouse uses the cross-docking strategy. In almost all cases we show that our bounds are, in some sense, best possible. 8. TITLE: An Overview of Classical and Modern Heuristics for the Vehicle Routing Problem SPEAKER: Gilbert Laporte AFFILIATION: Ecole des Hautes Etudes Commerciales and Centre for Research on Transportation, Montreal ABSTRACT: The Vehicle Routing Problem consists of determining a set of least cost routes through n customers, using a fleet of identical vehicles based at a depot, while satisfying some side constraints. Over the past four decades, several algorithms have been proposed for this problem, but to this date no exact algorithm can consistently solve instances of more than 30 customers. Most research has concentrated on the development of heuristics. Classical heuristics employ methods based on savings, sweep procedures, insertion techniques, incomplete column generation, etc. Modern heuristics (or metaheuristics) are based on simulated annealing, tabu search, genetic search and ant systems. In this talk I will review the main heuristic ideas used for the solution of the vehicle routing problem and I will point out some methodological difficulties encountered while making computational comparisons. 9. TITLE: Dynamic programming approximations for the discrete multicommodity network flow problem over a dynamic graph SPEAKER: Warren B. Powell AFFILIATION: Program in Statistics and Operations Research Department of Civil Engineering and Operations Research Princeton University Princeton, NJ 08540 ABSTRACT: We propose a version of the integer multicommodity network flow problem defined over a dynamic graph. The problem arises in the management of heterogeneous resources that are needed to serve tasks defined at given points in time. Resources are reusable, and are assumed to be modified by the task (the task changes the attributes of the resources). We propose an adaptive dynamic programming approximation that provides integer solutions. The method can be applied easily to both deterministic and stochastic problems. We show that for deterministic problems, the algorithm produces solutions that are very close to an LP relaxation. 10. TITLE Painting Cars and the Traveling Salesman Problem SPEAKER Thomas L. Magnanti AFFILIATION MIT ABSTRACT In automobile assembly plants, painting similarly-colored cars sequentially saves millions of dollars annually. We study an optimized implementation of an automated vehicle storage and retrieval system that acts as a buffer and allows the perturbation of the vehicle sequence around the painting stage of the manufacturing process. The problem of resequencing can be cast as a traveling salesman problem with time windows (TSPTW) and with 0/1 costs. For a real-life sequence, direct modeling using the strongest known TSPTW formulation yields an integer program with over 14,000,000 variables. By exploiting the special structure of the problem, we quickly solve the Lagrangean relaxation and create an IP-based heuristic that generates solutions within 3% of optimality in approximately one minute. Using this heuristic, an automobile manufacturer can plan each day's sequence, and also adjust the sequence in real time during the assembly process to compensate for faulty installations that cause unexpected delays to some cars. The entire process has the potential to save the manufacturer $2-3 million for each production line at each plant. 11. TITLE: GRASP: Greedy randomized adaptive search procedures SPEAKER: Mauricio G. C. Resende AFFILIATION: AT&T Labs Research, Florham Park, New Jersey ABSTRACT: GRASP is a metaheuristic for finding approximate solutions to combinatorial optimization problems. It was first applied in 1988 by Feo & Resende to set covering. Since then, numerous applications (including to problems in logistics) of GRASP have appeared in the literature. Several extensions and enhancements to the basic procedure have been proposed. In this talk, we provide some intuition behind the basic concepts in GRASP, survey extensions and enhancements to the basic procedure, and review the wide range of applications. 12. TITLE AI Techniques for large-scale Discrete Optimization SPEAKER Jimmy Crawford AFFILIATION i2 Technologies ABSTRACT This talk will overview several techniques that have come out of the AI community over the last few years that can be productively combined with OR approaches to solve large scale discrete optimization problems. We will also look at some of the work that has been done to date on effecting such a synthesis. Finally, we'll present some hard problems in supply chain planning that are beyond the reach of today's techniques in AI or OR. 13. TITLE: Optimization Problems in Air Traffic Management SPEAKER: Michael O. Ball AFFILIATION: Robert H Smith School of Business and Institute for Systems Research University of Maryland College Park, MD 20742 ABSTRACT: The Federal Aviation Administration, Euro-Control and other organizations around the world are tasked with insuring the safe and efficient flow of air traffic. As recently as 20 years ago, attention could be directed only to safety, as the flow of air traffic was much smaller than capacity of the airspace system, so that little or no attention needed to be directed toward flow management. Today the maximum arrival and departure rates at airports are binding constraints that must be considered when deciding upon flight routes and takeoff times. These rates can be substantially impacted by weather requiring modification of flight routes and schedules on a near-real-time basis. In some cases, the limitations on the number of flights that can be safely accommodated within enroute airspace sectors also represent limiting constraints which impact flight planning. In recent years a new paradigm for traffic flow management, called Collaborative Decision Making (CDM), has been developed and adopted by the FAA and the airline community within the US. One of the principal goals of CDM is to share decision making responsibility between the FAA and airlines soas to allow the airlines to control decisions that require consideration of economic tradeoffs. The resultant systems typically involve an iteration between the FAA and airlines, where the FAA performs basic constraint identification and resource allocation, and the airlines perform more refined allocation among their own flights. The FAA also implicitly plays the role of a neutral arbitrator that oversees the exchange of resources among airlines. A CDM-based system has been developed and successfully deployed for computing ground elay programs, which are mechanisms for allocating landing time slots at irports subject to weather-induced capacity reductions. The CDM paradigm provides a new challenge for optimization modeling. In this talk we review air traffic flow management optimization models in general and escribe models that have been specifically developed for use in the context of CDM-based ground delay programs. We also review recent work on large-scale integer programming models that involve networks of airports and airspace constraints. Suggestions for adapting these models to the CDM context are provided. 14. TITLE: Airline Integrated Recovery: AIR and SimAIR SPEAKER: Ellis L. Johnson AFFILIATION: Georgia Institute of Technology ABSTRACT: By integrated recovery is meant the rescheduling of planes taking into account passengers and crew as well as routings of planes so that maintenance constraints are satisfied. SimAIR is a tool being developed to simulate airline recovery and study both recovery methods as well as robust planning so that the airline is able to recover more quickly and at less additional cost. 15. TITLE: Very Large Scale Neighborhood Search SPEAKER: Ravindra K. Ahuja, AFFILIATION: Center for Applied Optimization & Dept. of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611 ABSTRACT: Neighborhood search algorithms have been found to be very effective in solving difficult combinatorial optimization problems. We describe neighborhood search algorithms for a clam of combinatorial optimizations problems with very large neighborhood, possibly exponential in terms of the size of the problems. This approach is especially amenable to partitioning problems which are characterized by a two-phase decision process: first, the optimal assignment of elements to clusters; and second, the optimal configuration of elements within each cluster. The following important problems fall in this category (i) vehicle routing problems with or without time windows; (ii) multi-traveling salesman problem; (iii) multi-facility location problems; (iv) capacitated minimum spanning tree problems; (v) parallel machine scheduling problems; (vi) problems in group technology; (vii) graph partitioning and clustering problems; and more. Researchers have examined heuristic algorithms using neighborhood search which proceed by performing exchanges of one or multiple elements between two clusters, called two-exchanges. Neighborhood search algorithms which are capable of performing exchanges involving multiple clusters, called multi-exchanges, would in general, have better empirical performance, but are not popular because the number of such exchanges grow exponentially with the number of clusters considered in the exchange. In this presentation, we propose a generic approach that uses network flow techniques, to identify exchanges involving multiple clusters in time comparable to the time taken by two-exchanges irrespective of the number of clusters involved in the exchange. Applications of this technique to a variety of partitioning problems will be described and also extensions to non-partitioning problems.Other Workshops

DIMACS Homepage

Contacting the Center

Document last modified on February 1, 1999.