ExxonMobil Research & Engineering (EMRE)

1545 Route 22 East

Annandale, New Jersey 08801

**Organizers:****Wanpracha Chaovalitwongse**, DIMACS, wchaoval@rci.rutgers.edu**Kevin C. Furman**, EMRE, kevin.c.furman@exxonmobil.com**Fred Roberts**, DIMACS, froberts@dimacs.rutgers.edu

This workshop is jointly sponsored by the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), and ExxonMobil Research and Engineering (EMRE).

Title: Optimization Problems and Computational Challenges in Ship Scheduling and Containerized Cargo Routing

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 computational challenge lies in integrating the ship scheduling and cargo routing problems. We formulate the integrated problem as a mixed integer linear program with exponential number of variables and propose various algorithms that 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 subproblems, the ship routing problem, itself offers many computational challenges and an efficient iterative procedure is proposed to solve it. All results illustrate impressive performance in computation time of the proposed algorithm.

Title: Vessel Arrival Process and Queueing in Bulk Marine Terminals

In the world of international trade, nearly every opportunity places a demand on marine transportation since it is economical and in many situations the only means of transportation. Today, 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 concentrates on vessel arrival processes in bulk ports handling bulk cargo. Vessel arrival patterns depend on location, trade routes, weather conditions, tidal activity, swells and other natural phenomena as well as unexpected failures or stoppages. For this reason, vessels do not generally arrive at their scheduled times. They rather arrive on a semi-scheduled manner (Cox and Lewis). We will characterize this arrival process and fit a model to it. We will look at some experimental results.

If time permits, we will discuss the SHIP/G/1 queue to be able to study the queueing behavior at bulk ports.

The talk is based on the speaker's joint work with Dave Jagerman.

Supported in parts by grants from the NSF OISE and DHS CBP.

Title: A New Relative Robust Optimization Approach for Full Factorial Scenario Design of Data Uncertainty and Ambiguity

This work presents 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). All results illustrate impressive performance in computation time of the proposed algorithm.

Title: Lot Streaming and Constraint Programming: A Review of Applications in Supply Chain Scheduling

It has long been recognized1 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. 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 presentation, the current literature in supply chain scheduling will be 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 presentation will conclude with summarizing the relevant work in this area.

Title: Second Level Local Optimization Approach to Employee Timetabling

A model and a series of local optimization algorithms (variants of local hill climbing and tabu search) for solving employee timetabling problem are presented. The foci are as follows. First, the model is carefully designed to allow for evaluation of constraint violations in essentially constant time. This enabled us to run algorithms to their convergence stage and investigate the relation between various neighborhood types. 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.

This approach also enabled us to observe 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 finetuning the solutions in later stages. The research is 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).

Title: Approximate dynamic programming for the management of freight cars

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. We show how approximate dynamic programming allows us to model 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.

Title: Optimization Using Surrogates for Engineering Design

This talk will outline the surrogate management framework, which is presently built on the filter MADS method for general nonlinear programming without derivatives. The focus is on the numerical results, with a brief introduction to the MADS algorithm and a slight mention of the convergence results.

This line of research was motivated by industrial applications, indeed, by a question I was asked by Paul Frank of Boeing Phantom Works. His group was often asked for help in dealing with very low dimensional design problems driven by expensive simulations. Everyone there was dissatisfied with the common practice of substituting inexpensive surrogates for the expensive ``true'' objective and constraint functions in the optimal design formulation. I hope to demonstrate in this talk just how simple the answer to Paul's question is.

The surrogate management framework has been implemented successfully by several different groups, and it is unreasonably effective in practice, where most of the application are extended valued and certainly nondifferentiable. This has forced my colleagues and me to begin to learn some nonsmooth analysis, which in turn has led to MADS, a replacement for the GPS infrastructure algorithm.

Title: Easing Rescheduling Complexity for a Bulk Gas Production and Distribution Problem

This paper addresses 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. We build an optimization model approximating the model in place at the company and a simulation mechanism that allows us to create instances of varying time-granularities. Computational results are given to reveal the cause of the frequent rescheduling. A mechanism for easing the rescheduling burden is suggested.

Title: Logic-Based Optimization for Interdependent Layered Networks (ILN) Problems

This paper discusses incorporating constraint programming into mathematical programming approaches for ILN problems. This methodology can be used to model interdependent infrastructures, such as power, telephone, and transportation. Previously, we have used mixed integer programming formulations for models of this type. In this paper, logical constraints are employed to depict the interdependencies among the networks. Linear constraints (network flow constraints) are used for each individual network. Constraint programming provides the capability of defining the structure of the search space and specifying the algorithm for exploring the search space, which makes it possible to solve the model by combined logical inference and branch-and-bound.

A realistic problem of managing disruption to the critical infrastructure systems in the area south of 60th street, Manhattan region of New York is discussed in the paper. The subway system includes 115 stations and 338 local and express track sections. The phone system model includes 18 switching centers and their associated service areas, 72 controlled environmental vaults where distribution cables are joined into larger feeder cables and all the associated wiring. The power system as modeled includes 16 substations and 32 service areas and each substation distributes power along 8-24 feeders to 18 phone switching centers, 178 AC/DC rectifiers for the subways and service to all residences and businesses in the area. A restoration model that aims for the optimal recovery strategy is developed in OPL and solved by ILOG Solver and Hybrid.

Title: Computational Methods for Enterprise-wide Optimization of Process Industries

In this presentation we give an overview of a new project in the area of Enterprise-wide Optimization (EWO) by a multidisciplinary group at Carnegie Mellon University (Biegler, Hooker, Grossmann), Lehigh University (Linderoth) and the University of Pittsburgh (Schaeffer) composed of chemical engineers and operations researchers. This project is in collaboration with five industrial partners, ABB, Air Products, BP, Dow, and ExxonMobil. The goal is to develop novel computational models for improving the operation of the petroleum and chemical industries. Due to increasing competitive pressures for reducing costs and inventories, Enterprise-wide Optimization (EWO) has become a major goal in these industries. EWO involves optimizing the operations of supply, manufacturing (batch or continuous) 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 our research effort is 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 the various components of the supply chain; b) Multi-scale optimization for coordinating the optimization of models over geographically distributed locations and for a time horizons spanning from weeks to years; c) Optimization under uncertainty to account for stochastic variations (e.g. demands, process yields, breakdowns); d) Algorithms and advanced computer architectures to support the three previous points. We present some preliminary results on the several industrial projects that include simultaneous planning and scheduling of mutisite batch reactors, global optimization of refinery MINLP scheduling models, multistage stochastic programming models for off-shore oil and gas exploration and process networks.

Title: A Polynomial Time Algorithm for the Stochastic Lot-Sizing Problem

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. In this research we study the uncapacitated lot-sizing problem with stochastic demands. We show 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 us to define a polynomial dynamic programming algorithm for this problem. This research continues research by these and other authors whose eventual goal is to be able to solve actual production planning and supply chain problems with uncertain demands.

Title: Modeling and Managing Uncertainty in Process Planning and Scheduling

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 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. An overview of the work along the directions of scheduling and planning optimization, and uncertainty considerations within the decision-making process will be presented.

Title: Models for Optimizing Multiple Resources in a Performance-Based Logistics (PBL) Contract

Today, there is a significant emphasis in the public sectors on leveraging Performance-Based Logistics (PBL) concepts to define and monitor contractual relationships between public and private industry. In a PBL contract the customer buys performance instead of contracting for a specified collection of resources defining the underlying support infrastructure. Performance is commonly defined by more than one metric and there is great deal of dependency between these measures and these measures may even be contradictory in nature. In the presence of multiple performance measures, contractors of PBL have to identify and optimize the resources required to meet these multiple performance targets and constraints to maximize their profit. In this paper we develop a mathematical model using goal programming to determine the optimal mix of resources that will simultaneously optimize multiple performance measures such as operational availability, reliability, maintainability, total cost of ownership, expected backorder and the waiting time delays for various support infrastructure resources.

Title: Scheduling On Demand Passenger Air Service

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. They expect 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, they eliminate 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, I will discuss the optimization models and algorithms that we have developed for scheduling DayJet's forthcoming service. This is very difficult optimization problem that requires customized algorithms.

Title: Spares Provisioning under Performance Based Logistics Contract - Profit Centric Approach

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 availability, mission readiness and operational reliability, instead of contracting for a specified collection of resources defining the underlying support infrastructure. The literature on PBL is still in its infancy and additional research is required to optimize logistic resources such as spare parts, equipment, facilities, labor etc within a PBL context. In this paper an optimization model is developed for spares provisioning under a multi-item, multi-echelon scenario. The objective of the optimization model is to maximize the profit to the supplier under a PBL contract.

Title: Efficient Routing Under Uncertainty

Vehicle routing in many industrial applications is faced with significant uncertainty which can make a carefully planned routing solution inefficient. In this work we consider the problem of routing medical supplies in response to a large scale emergency, which is subject to uncertainty both in demand and travel times. It is unclear a priori which stochastic vehicle routing model is best suited for such a problem. We study and contrast two models for this problem, which differ in how they handle the uncertainty: using chance constraint programming or robust optimization. We compare the merits of these solution approaches for this problem in terms of assumptions, computational complexity, and quality of solution in practice.

Title: Recent Advances and Trends in Deterministic Global Optimization

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 our knowledge of all aspects of the field has grown even more profound. At the same time one of the most striking trends in global optimization is the constantly increasing interdisciplinary nature of the field.

This talk will cover the following topics: Nonconvexity and discreteness in optimization, DC (difference of convex functions) and monotonic optimization, Multiquadratic programming and applications, Multi-variable partition approaches and Hierarchical (multi-level) optimization, Optimization with massive datasets, Supply Chain, E-commerce, and E-manufacturing.

Title: Approximate Dynamic Programming for High-Dimensional Resource Allocation Problems in Transportation and Logistics

There are a variety of problems in transportation and logistics where we have to make decisions 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. We will show how practical solutions can be obtained by combining math programming, simulation and machine learning under the umbrella of approximate dynamic programming. The techniques will be illustrated in the context of problems drawn from several operational problems in freight transportation and military logistics.

Title: Branch-and-Cut for Piecewise Linear Optimization

We present a branch-and-cut algorithm for the problem of maximizing a piecewise linear function (PLF) subject to piecewise linear constraints, the piecewise linear optimization problem (PLO). Besides being interesting on its own, PLO is the most popular strategy to model difficult nonlinear programming problems.

Our algorithm dispenses with the use of binary variables in the formulation. At the same time, it solves discontinuous PLO regardless of whether there are PLFs that are lower-semicontinuous. In addition, we will present several families of facet-defining inequalities for the convex hull of the set of feasible solutions, and computational results that demonstrate the efficiency of the algorithm and the families of facets.

Title: Some Optimization Issues in the Internet

In this talk, we consider some optimization issues that arise in the design and operations of Internet Protocol (IP) networks. The Internet is organized as a set of Autonomous Systems (ASes). An AS is a network controlled by a single entity. Routing is done within each AS as well as between ASes. We first consider the OSPF weight setting problem in traffic engineering, where AS link weights used in Open Shortest Path First (OSPF) routing need to be set to minimize network routing cost.

We then consider survivable AS network design, where, given a set of routers, estimated traffic demands, and a set of potential links in an AS, we wish to determine link capacities such that all traffic can be OSPF-routed in the network subject to single link failures and at minimum cost.

We finally consider some optimization issues that arise in Border Gateway Protocol (BGP) routing where an entity needs to route beyond its AS. An egress router is a router in the border of two ASes. We describe how egress router selection can be used to do traffic engineering.

Parts of this talk are joint with Luciana Buriol (UFRGS, Brazil), Marten Ericsson (KTH, Sweden), Tim Griffin (Cambridge U., U.K.), Panos Pardalos (U. of Florida), Jennifer Rexford (Princeton U.), Celso Ribeiro (UFF, Brazil), Renata Teixeira (U. Paris VI, France), and Mikkel Thorup (AT&T Research).

Title: Introduction to Risk-Averse Optimization

We shall discuss several methods for modeling risk aversion in stochastic optimization. Particular attention will be given to mean-risk models, general risk functionals, and modeling via benchmark outcomes. For all these models we shall develop optimality conditions, and discuss specialized numerical methods. The results will be illustrated with a portfolio optimization problem of large dimension.

Title: Robust Optimization for Empty Repositioning Problems

We present 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. We develop necessary and sufficient conditions for flows to be robust given three types of allowable recourse actions. When only flow changes on inventory arcs are allowed during recourse, we show that the resulting problem is polynomially-solvable. When recourse actions allow limited reactive repositioning, we develop a feasibility set 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.

Title: Nested Partitions Optimization Framework and its Applications

Designing and operation of complex large-scale systems such as transportation systems, manufacturing systems, supply chain networks, and health care systems are very difficult tasks. Many contributing factors exist; chief among them is the exponential explosion of alternatives normally leading to NP-hard optimization problems. In the case of stochastic optimization, the situation is further complicated by randomness. We have recently developed a new framework called Nested Partitions (NP) for global optimization. NP uses partitioning, random sampling, selection of a promising index, and backtracking techniques to create a Markov chain, which has been proven with probability one to converge to a global optimum. One important feature of the NP method is that it can combine global search and local search (domain knowledge or heuristic) procedures in a natural way. The NP method is also highly matched to massively parallel processing capabilities. The global and parallelism nature of the optimization framework provides an efficient and effective platform for information sharing and exchange during search procedure. In this talk, we will introduce the NP framework, discuss related theoretical issues, and demonstrate its effectiveness through a few application examples.

Title: Dynamic and Data-Driven Pricing under Uncertainty

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. In this work, we propose a framework based on dynamic and data-driven optimization to address the challenge of predicting customers' behavior accurately. We focus on the newsvendor problem with pricing and other simple examples in revenue management. Our 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. We provide theoretical insights on the optimal solution, quantify the maximum response times of the decision-maker required to ensure good practical performance and illustrate our findings on a numerical example.

Title: Optimization of the Logistics Support Enterprise for the Lockheed Martin Joint Strike Fighter

Over the next 20 years, the Lockheed Martin (LM) Joint Strike Fighter (JSF) will replace a wide range of fighter aircraft in US, NATO, and other allied armed forces. In a radical departure from historical norms, the spare-parts logistics operations for the global, cross-service fleet will be centrally managed by LM. The logistics system is currently modeled using a high-resolution discrete event simulation known as the Support Enterprise Model (SEM). We discuss the high-level architecture of an approach to optimizing key parameters of the SEM, specifically the system-wide inventory and resource allocations. The complexity of SEM necessitates an optimization strategy based on a novel hybridization of optimization technologies, including mixed-integer programming, scenario-based decomposition for stochastic programming (progressive hedging), and local search, in addition to multi-fidelity surrogate models of SEM. We contrast our approach to more traditional algorithms for optimizing military logistics operations, emphasizing both minimization of modeling assumptions and new challenges for logistics optimization such as customer-defined business rules.

Title: Strategic and Tactical Supply Chain Planning with Xpress-Mosel

We present 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. We develop necessary and sufficient conditions for flows to be robust given three types of allowable recourse actions. When only flow changes on inventory arcs are allowed during recourse, we show that the resulting problem is polynomially-solvable. When recourse actions allow limited reactive repositioning, we develop a feasibility set 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.

Program

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on March 21, 2006.