;Report on DIMACS and ExxonMobil Workshop on Computational
Optimization and Logistics Challenges
in the Enterprise (COLCE)
Date of workshop: April 19-20, 2006
W. Art Chaovalitwongse (Rutgers University)
Kevin C. Furman (ExxonMobil Research and Engineering)
Fred S. Roberts (DIMACS)
Abhinav Jha, Industrial and Systems Engineering, Rutgers University
Date of Report: May 28, 2006
*DIMACS was founded as a National Science Foundation Science and Technology Center. It is a joint project of Rutgers University, Princeton University, AT&T Labs-Research, Bell Labs, NEC Laboratories America, and Telcordia Technologies, with affiliated partners Avaya Labs, Georgia Institute of Technology, HP Labs, IBM Research, Microsoft Research, Rensselaer Polytechnic Institute, and Steven Institute of Technology.
; DIMACS was founded as a National Science Foundation Science and Technology Center. It is a joint project of Rutgers University, Princeton University, AT&T Labs-Research, Bell Labs, NEC Laboratories America, and Telcordia Technologies, with affiliated partners Avaya Labs, IBM Research, Microsoft Research, and HP Labs.
1. Workshop Focus
The purpose of this 2-day workshop conference was to explore a wide range of advances in optimization techniques in the study of supply chain and logistics challenges in the enterprise. This workshop provided a forum for leading as well as beginning researchers to discuss and address the computational challenges that arise in supply chain optimization, logistics, planning and scheduling in the industrial sector. This workshop was designed to bring together operations research and mathematical optimization experts from the academic arena with industry practitioners, in an attempt to share knowledge, ideas, and scientific methodology. Both invited and contributed talks were presented over the course of the workshop across a diverse range of relevant topics. These topics included:
； Enterprise-Wide Optimization
； Transportation, Logistics & Distribution Networks
； Inventory Management
； Process Operations and Scheduling
； Planning & Long Term Investment
； Mathematical Finance, Pricing & Forecasting
； Advances in Optimization Models, Algorithms & Platforms
This conference brought together a multi-disciplinary group to enable the sharing of knowledge, ideas, and techniques. This requires, by necessity, collaboration among academicians and practitioners. This conference resulted in lively discussions of the cross-disciplinary research and opened up a new question: How do we go from the mathematical modeling and optimization techniques to the practical solutions to the enterprise's operations? The answer to this question will revolutionize research in optimization and logistics as well as the real business operations in the enterprise.
2. Summary of Presentations
2.1 Computational Models for Enterprise-wide Optimization
Speaker: Ignacio Grossmann, Carnegie Mellon University
Joint work with Biegler and Hooker (Carnegie Mellon University), Linderoth (Lehigh University) and Schaeffer (University of Pittsburgh).
Industrial Partners: ABB, Air Products, BP, Dow, and ExxonMobil
The speaker gave an overview of a new project in the area of Enterprise-wide Optimization (EWO) by a multi-disciplinary group composed of chemical engineers and operations researchers. The goal of the project is to develop new computational models for improving the operation of the petroleum and chemical industries.
The speaker explained that increasing competitive pressures for reducing costs and inventories have prompted these industries to focus on EWO. EWO involves optimizing the operations of supply, manufacturing and distribution activities of a company. The major operational activities include planning, scheduling, real-time optimization and inventory control. A major focus in EWO is the scheduling of the manufacturing facilities, as well as their modeling at the proper level of detail, often with nonlinear process models.
In order to achieve EWO throughout the process industry, the research aimed at developing a new generation of computational tools that allow the full integration and large-scale solution of the optimization models, as well as the incorporation of accurate models for the manufacturing facilities. These tools will address the following areas:
a) Modeling of production planning and scheduling models for various components
of the supply chain
b) Multi-scale optimization for coordinating the optimization of models over
geographically distributed locations and for time horizons spanning from weeks to
c) Optimization under uncertainty to account for stochastic variations
d) Algorithms and advanced computer architectures to support the three previous
The speaker then presented some preliminary results on the several industrial projects that include simultaneous planning and scheduling of multi-site batch reactors, global optimization of refinery MINLP scheduling models, multistage stochastic programming models for off-shore oil and gas exploration and process networks.
2.2 Recent Advances and Trends in Deterministic Global Optimization
Speaker: Panos M. Pardalos, University of Florida
Global optimization has been expanding in all directions at an astonishing rate during the last few decades. New algorithmic and theoretical techniques have been developed, the diffusion into other disciplines has proceeded at a rapid pace, and knowledge of all aspects of the field has grown even more profound. The speaker pointed out that one of the most striking trends in global optimization is the constantly increasing interdisciplinary nature of the field.
The talk covered the following topics:
a) Nonconvexity and discreteness in optimization
b) DC (difference of convex functions) and monotonic optimization
c) Multiquadratic programming and applications
d) Multi-variable partition approaches and Hierarchical (multi-level) optimization
e) Optimization with massive datasets
f) Supply Chain
2.3 Approximate Dynamic Programming for High-Dimensional Resource
Allocation Problems in Transportation and Logistics
Speaker: Warren B Powell, Princeton University
Joint work with Hugo Simao and Abraham George (Princeton University).
The speaker began by pointing out that there are a variety of problems in transportation and logistics where decisions have to be made about operators (drivers, crews), moving equipment (jets, locomotives, trucks) over time, with numerous sources of uncertainty. These problems are naturally formulated as dynamic programs, but the resulting problems have states with thousands and even millions of dimensions.
The speaker discussed hoe practical solutions can be obtained by combining math programming, simulation and machine learning under the umbrella of approximate dynamic programming. The speaker illustrated these techniques in the context of problems drawn from several operational problems in freight transportation and military logistics.
2.4 Approximate Dynamic Programming for the Management of Freight Cars
Speaker: Warren Powell, Princeton University
Joint work with Belgacem Bouzaiene-Ayari (Princeton University).
The management of freight cars for railroads has to handle random customer demands, random car supplies, random travel times, and randomness in the acceptability of a car to the customer. Further complicating the problem is the need to dispatch cars as soon as they are empty.
The speaker showed how approximate dynamic programming allows the modeling of the real problem with a high level of realism, producing higher quality solutions than the models that are used by most railroads. The method provides near optimal solutions when compared to solutions provided by commercial solvers when the problem is modeled deterministically. More important, the system has been successfully implemented at Norfolk Southern Railroad.
2.5 Robust Optimization for Empty Repositioning Problems
Speaker: Martin Savelsbergh, Georgia Institute of Technology
The speaker presented a robust optimization framework for dynamic empty repositioning problems modeled using time-expanded networks. A robust repositioning plan is one in which the typical flow balance constraints and flow bounds are satisfied for the nominal net supply forecast values and the plan is recoverable under a limited set of recourse actions, where a plan is recoverable when feasibility can be reestablished for any actual realization of net supply in the outcome space.
Necessary and sufficient conditions were developed for flows to be robust given three types of allowable recourse actions. When only flow changes on inventory arcs are allowed during recourse, it was shown that the resulting problem is polynomially-solvable. When recourse actions allow limited reactive repositioning, a feasibility set is developed; it is defined by a number of constraints that may grow exponentially with problem size but is independent of the size of the uncertain outcome space. In this case, computational techniques using cut generation are developed and shown to be effective for realistic problem sizes.
2.6 Vessel Arrival Processes and Queuing in Bulk Marine Terminals
Speaker: Tayfur Altiok, Rutgers University
Joint work with Dave Jagerman.
Supported in parts by grants from the NSF OISE and DHS CBP.
The speaker explained that nearly every opportunity in the world of international trade placed a demand on marine transportation since it is economical and in many situations, is the only means of transportation. The speaker pointed out that currently more than 90% of international cargo moves through marine terminals which may be handling containers or materials such as minerals (oil, coal, bauxite, etc.).
This talk concentrated on vessel arrival processes in bulk ports handling cargo. The speaker explained that vessels do not generally arrive at their scheduled times since their arrival patterns depend on location, trade routes, weather conditions, tidal activity, swells and other natural phenomena as well as unexpected failures and stoppages. Instead, they arrive in a semi-scheduled manner (Cox and Lewis). The speaker characterized this arrival process, fit a model to it and then showed some experimental results.
2.7 Introduction to Risk-Averse Optimization
Speaker: Andrzej Ruszczynski, Rutgers University
The speaker discussed several methods for risk aversion in stochastic optimization. Particular attention was paid to mean-risk models, general risk functionals, and modeling
via benchmark outcomes. Optimality conditions were developed for all these models, and specialized numerical methods were discussed. The speaker illustrated the results with a portfolio optimization problem of a large dimension.
2.8 Efficient Routing Under Uncertainty
Speaker: Fernando Ordonez, University of Southern California
Joint work with M.M. Dessouky, Z Shen, and I. Sungur (University of Southern California).
Vehicle routing in many industrial applications is faced with significant uncertainty which can make a carefully planned routing solution inefficient. The speaker discussed the problem of routing medical supplies in response to a large scale emergency, which is subject to uncertainty both in demand and travel times. The speaker pointed out that it is unclear a priori which stochastic vehicle routing model is best suited for such a problem.
For this problem, two models were studied and contrasted, which differ in how they handle the uncertainty: using chance constraint programming or robust optimization. The speaker compared the merits of these solutions approaches for this problem in terms of assumptions, computational complexity, and quality of solution in practice.
2.9 Dynamic and Data-Driven Pricing under Uncertainty
Speaker: Aurélie Thiele, Lehigh University
Traditional models of decision-making under uncertainty assume the precise knowledge of the underlying probability distributions. However, in today’s fast-changing
environment driven by volatile customer tastes, rapid technological change and short product life cycles, managers rarely have such perfect information at their disposal.
The speaker proposed a framework based on dynamic and data-driven optimization to address the challenge of predicting customers’ behavior accurately. The speaker focused on the newsvendor problem with pricing and other simple examples in revenue management. The approach is based on the monitoring of the actual demand and on the capability of the decision-maker to address sudden changes quickly, for instance by increasing the frequency of the observations and tracking additional quantities of interest, such as demand for other products or at other stores. The methodology has a strong computational component as the decision-maker must keep track of large amounts of data.
The speaker provided theoretical insights on the optimal solution, quantified the maximum response times of the decision-maker required to ensure good practical performance and illustrated findings on a numerical example.
2.10 A New Relative Robust Optimization Approach for Full Factorial Scenario
Design of Data Uncertainty and Ambiguity
Speaker: Tiravat Assavapokee, University of Houston
The speaker presented the application of bi-level programming (decision making in adversarial domains) to develop the effective algorithm for relative robust optimization problem for two-stage decision making under uncertainty and ambiguity. The structure of the first stage problem is binary MILP and the structure of the second stage problem is LP. Each uncertain parameter can independently of other parameters' settings take its values from a finite set of real numbers with unknown probability distribution. The algorithm is applied to solve the relative robust optimization problem with incredibly large number of possible scenarios (1.2158 x 10^19 scenarios). The speaker concluded that all results illustrate impressive performance in computation time of the proposed algorithm.
2.11 Modeling and Managing Uncertainty in Process Planning and Scheduling
Speaker: Marianthi Ierapetritou, Rutgers University
The speaker observed that modern industry faces major new challenges through increased global competition, greater regulatory pressures and uncertain prices of energy, raw materials and products. These competitive concerns increase the focus on integrated processes, information technology, and consideration of multiple decision criteria including profitability, flexibility, quality, and the environment.
The speaker stated that the success of any industrial sector will depend on how efficiently it generates value by dynamically optimizing deployment of its supply chain resources. Among the challenges for the dynamic optimization of the entire supply chain enterprises is the rigorous but tractable optimization of process operations and the efficient integration of different decision making stages as well as the consideration of uncertainty and risk factors.
Uncertainty appears in all the different levels of the industry from the detailed process description to multi-site manufacturing. Therefore, the successful utilization of process models relies heavily on the ability to handle system variability. The speaker presented an overview of the work along the directions of scheduling and planning optimization, and uncertainty considerations within the decision-making process.
2.12 Lot Streaming and Constraint Programming: A Review of Applications in
Supply Chain Scheduling
Speaker: Őmer S. Benli, California State University
It has long been recognized that scheduling was not a visible problem in many enterprises because other parts of the enterprise have absorbed much impact of the poor scheduling. It is no longer the case. The speaker pointed out that as internet-based technologies emerge, supply “chains” are becoming supply “webs”. Parties involved in
the supply chain will be collaborating more in order to deliver the most to the end customer, since each party will be responsible for the success or failure of the supply “web”. In this context supply chain scheduling is becoming especially important. This
can be seen clearly in the growing literature in the study of supply chain coordination in a scheduling environment.
In this talk, the current literature in supply chain scheduling was reviewed with special emphasis to lot streaming problems. Lot streaming, basically, is moving some portion of a process batch ahead to begin a downstream operation. Although the resulting models of realistic applications are computationally intractable, the recent advances in the integration of optimization and constraint programming, and the resulting user friendly software that is becoming available may result in the computational viability of this approach. The speaker concluded with summarizing the relevant work in this area.
2.13 A Polynomial Time Algorithm for the Stochastic Lot-Sizing Problem
Speaker: Andrew Miller, University of Wisconsin-Madison
Joint work with Yongpei Guan (University of Oklahoma).
In 1958, Wagner and Whitin first identified properties of the basic economic lot-size model and derived an efficient algorithm for it. The utility of their results, while substantial, has been limited somewhat by the assumption that demand is deterministic.
The speaker discussed the uncapacitated lot-sizing problem with stochastic demands. It was shown that, if demand is modeled as a scenario tree that satisfies certain conditions, there are properties of the resulting model that are analogous to the Wagner-Whitin model.
One property in particular (call it the production path property) is as follows: If production occurs at some point in the time horizon for some realization of demand, then the optimal amount to produce is always exactly enough (given the inventory on hand) to satisfy all of the demand from the present until some future period, for some realization of demand from now until that period. This property and others allow a definition for a polynomial dynamic programming algorithm for this problem. The speaker stated that the eventual goal of the continued research is to be able to solve actual production planning and supply chain problems with uncertain demands.
2.14 Second Level Local Optimization Approach to Employee Timetabling
Speaker: Drago Bokal, Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
Joint work with G. Fijavž, D. Vodopivec and S. Pintar, and is funded by ICIT d. o. o. and Hit d. d. as part of the Scheduler Expert project (www.schedulerexpert.com).
The speaker presented a model and a series of local optimization algorithms (variants of local hill climbing and tabu search) for solving employee timetabling problem. The foci are as follows. First, the model is carefully designed to allow for evaluation of constraint violations in essentially constant time. This enables the running of algorithms to their convergence stage and investigation of the relation between various neighborhood types. The speaker said that the model shows superiority of larger exhaustive neighborhoods when these are given sufficient time to converge, and confirms results of Schaerf and Meisels that smaller, in part randomly chosen neighborhoods provide suboptimal results faster. Second, concepts of optimization (data, constraints, algorithms) are isolated as building-blocks to allow for combining them in a variety of different ways. Advantage of thus obtained second-level local optimization algorithms is demonstrated.
The speaker said that this approach enables the observation of significantly different convergence vs. quality behavior of algorithms when using alternative implementations of constraints of the model. Each of these behaviors was used for specific purpose in combined optimization: either for fast design of suboptimal solutions or for fine-tuning the solutions in later stages.
2.15 Optimization Problems and Computational Challenges in Ship Scheduling and
Containerized Cargo Routing
Speaker: Richa Agarwal, Georgia Institute of Technology
Joint work with Ozlem Ergun (Georgia Institute of Technology).
A common problem faced by carriers in the Sea-Cargo industry is the design of their service routes. Growing international markets and increasing number of collaborations among carriers create a need for designing service routes that utilize a large fleet to maximize revenue by sending cargo on these routes.
The speaker focused on the computational challenge in integrating the ship scheduling and cargo routing problems. The integrated problem was formulated as a mixed integer linear program with exponential number of variables and various algorithms were proposed to exploit the separability of the problem to solve it efficiently. A simple greedy heuristic provides a feasible solution quickly. A column generation based algorithm provides good quality solutions, however incurring a long computational time. Finally, a Bender's decomposition based sophisticated algorithm provides high quality solutions in acceptable computational time. One of the sub-problems, the ship routing problem, itself offers many computational challenges and an efficient iterative procedure is proposed to solve it. The speaker concluded that all results illustrate impressive performance in computation time of the proposed algorithm.
2.16 Scheduling On Demand Passenger Air Service
Speaker: George Nemhauser, Georgia Institute of Technology
The speaker discussed the problem of scheduling daily flights for a non-scheduled airline. A non-scheduled airline provides regional “on demand” air transportation on small jet planes having a capacity of 3 passengers. A request for travel specifies an origin, destination, earliest departure time, and latest arrival time. Based on requests already accepted for that day, the accept/reject problem is to determine whether the new request can be accommodated. At the beginning of the day an optimal schedule that minimizes flying time is created for all of the accepted requests for that day.
DayJet will begin providing this service in 2006 using the Eclipse 500, which costs less than a million dollars, is fuel efficient and has a range of over a thousand miles. DayJet expects to have several hundred jets covering overlapping regions of the U.S. in a few years. This service is especially useful for areas that are not well served by large airports. By using small airports, DayJet eliminates the hassles associated with long drives to the airport, packed parking lots, security lines, etc. For many travelers, this service will yield huge time savings in comparison to the alternatives of a scheduled airline or driving.
In this talk, the speaker discussed the optimization models and algorithms that we have developed for scheduling DayJet’s forthcoming service. This is a very difficult optimization problem that requires customized algorithms.
2.17 Easing Rescheduling Complexity for a Bulk Gas Production and Distribution
Speaker: Jeff Linderoth, Lehigh University
Joint work with Wasu Glankwamdee, Jackie Griffin and Jierui Shen (Lehigh University).
The speaker addressed the issue of why a large industrial gas company is often forced to reschedule its production and distribution plans during the course of a month. An optimization model was built to approximate the model in place at the company and a simulation mechanism that allows the creation of instances of varying time-granularities. The speaker gave computational results to reveal the cause of the frequent rescheduling and suggested a mechanism for easing the rescheduling burden.
2.18 Spares Provisioning under Performance Based Logistics Contract – Profit
Speaker: Dinesh Kumar, Stevens Institute of Technology
Joint work with David Nowicki and Dinesh Verma (Stevens Institute of Technology).
The speaker observed that Performance based logistics (PBL) is emerging as a preferred logistic support strategy within the public sector, especially the Department of Defense. Under a PBL strategy the customer buys performance, such as operational