DIMACS Workshop on Large Scale Discrete Optimization in Logistics

February 8 - 10, 1999
DIMACS Center, CoRE Building (Room 431), Rutgers University, Busch Campus, Piscataway, NJ

Organizers:

• 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