Algorithm to solve a chance‐constrained network capacity design problem with stochastic demands and finite support

We consider the problem of determining the capacity to assign to each arc in a given network, subject to uncertainty in the supply and/or demand of each node. This design problem underlies many real‐world applications, such as the design of power transmission and telecommunications networks. We first consider the case where a set of supply/demand scenarios are provided, and we must determine the minimum‐cost set of arc capacities such that a feasible flow exists for each scenario. We briefly review existing theoretical approaches to solving this problem and explore implementation strategies to reduce run times. With this as a foundation, our primary focus is on a chance‐constrained version of the problem in which α% of the scenarios must be feasible under the chosen capacity, where α is a user‐defined parameter and the specific scenarios to be satisfied are not predetermined. We describe an algorithm which utilizes a separation routine for identifying violated cut‐sets which can solve the problem to optimality, and we present computational results. We also present a novel greedy algorithm, our primary contribution, which can be used to solve for a high quality heuristic solution. We present computational analysis to evaluate the performance of our proposed approaches. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 236–246, 2016     

Robust capacity planning in semiconductor manufacturing

We present a stochastic programming approach to capacity planning under demand uncertainty in semiconductor manufacturing. Given multiple demand scenarios together with associated probabilities, our aim is to identify a set of tools that is a good compromise for all these scenarios. More precisely, we formulate a mixed‐integer program in which expected value of the unmet demand is minimized subject to capacity and budget constraints. This is a difficult two‐stage stochastic mixed‐integer program which cannot be solved to optimality in a reasonable amount of time. We instead propose a heuristic that can produce near‐optimal solutions. Our heuristic strengthens the linear programming relaxation of the formulation with cutting planes and performs limited enumeration. Analyses of the results in some real‐life situations are also presented. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Inventory management with advance capacity information

An important aspect of supply chain management is dealing with demand and supply uncertainty. The uncertainty of future supply can be reduced if a company is able to obtain advance capacity information (ACI) about future supply/production capacity availability from its supplier. We address a periodic‐review inventory system under stochastic demand and stochastic limited supply, for which ACI is available. We show that the optimal ordering policy is a state‐dependent base‐stock policy characterized by a base‐stock level that is a function of ACI. We establish a link with inventory models that use advance demand information (ADI) by developing a capacitated inventory system with ADI, and we show that equivalence can only be set under a very specific and restrictive assumption, implying that ADI insights will not necessarily hold in the ACI environment. Our numerical results reveal several managerial insights. In particular, we show that ACI is most beneficial when there is sufficient flexibility to react to anticipated demand and supply capacity mismatches. Further, most of the benefits can be achieved with only limited future visibility. We also show that the system parameters affecting the value of ACI interact in a complex way and therefore need to be considered in an integrated manner. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Expansion planning for waste‐to‐energy systems using waste forecast prediction sets

We consider an expansion planning problem for Waste‐to‐Energy (WtE) systems facing uncertainty in future waste supplies. The WtE expansion plans are regarded as strategic, long term decisions, while the waste distribution and treatment are medium to short term operational decisions which can adapt to the actual waste collected. We propose a prediction set uncertainty model which integrates a set of waste generation forecasts and is constructed based on user‐specified levels of forecasting errors. Next, we use the prediction sets for WtE expansion scenario analysis. More specifically, for a given WtE expansion plan, the guaranteed net present value (NPV) is evaluated by computing an extreme value forecast trajectory of future waste generation from the prediction set that minimizes the maximum NPV of the WtE project. This problem is essentially a multiple stage min‐max dynamic optimization problem. By exploiting the structure of the WtE problem, we show this is equivalent to a simpler min‐max optimization problem, which can be further transformed into a single mixed‐integer linear program. Furthermore, we extend the model to optimize the guaranteed NPV by searching over the set of all feasible expansion scenarios, and show that this can be solved by an exact cutting plane approach. We also propose a heuristic based on a constant proportion distribution rule for the WtE expansion optimization model, which reduces the problem into a moderate size mixed‐integer program. Finally, our computational studies demonstrate that our proposed expansion model solutions are very stable and competitive in performance compared to scenario tree approaches. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 47–70, 2016     

Sensitivity analysis on responsive pricing and production under imperfect demand updating

This paper examines three types of sensitivity analysis on a firm's responsive pricing and responsive production strategies under imperfect demand updating. Demand has a multiplicative form where the market size updates according to a bivariate normal model. First, we show that both responsive production and responsive pricing resemble the classical pricing newsvendor with posterior demand uncertainty in terms of the optimal performance and first‐stage decision. Second, we show that the performance of responsive production is sensitive to the first‐stage decision, but responsive pricing is insensitive. This suggests that a “posterior rationale” (ie, using the optimal production decision from the classical pricing newsvendor with expected posterior uncertainty) allows a simple and near‐optimal first‐stage production heuristic for responsive pricing. However, responsive production obtains higher expected profits than responsive pricing under certain conditions. This implies that the firm's ability to calculate the first‐stage decision correctly can help determine which responsive strategy to use. Lastly, we find that the firm's performance is not sensitive to the parameter uncertainty coming from the market size, total uncertainty level and information quality, but is sensitive to uncertainty originating from the procurement cost and price‐elasticity.     

Generation and storage dispatch in electricity networks with generator disruptions

We present methods for optimizing generation and storage decisions in an electricity network with multiple unreliable generators, each colocated with one energy storage unit (e.g., battery), and multiple loads under power flow constraints. Our model chooses the amount of energy produced by each generator and the amount of energy stored in each battery in every time period in order to minimize power generation and storage costs when each generator faces stochastic Markovian supply disruptions. This problem cannot be optimized easily using stochastic programming and/or dynamic programming approaches. Therefore, in this study, we present several heuristic methods to find an approximate optimal solution for this system. Each heuristic involves decomposing the network into several single‐generator, single‐battery, multiload systems and solving them optimally using dynamic programming, then obtaining a solution for the original problem by recombining. We discuss the computational performance of the proposed heuristics as well as insights gained from the models. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 493–511, 2015     

Vertically restrictive pricing in supply chains with price‐dependent demand

We examine the behavior of a manufacturer and a retailer in a decentralized supply chain under price‐dependent, stochastic demand. We model a retail fixed markup (RFM) policy, which can arise as a form of vertically restrictive pricing in a supply chain, and we examine its effect on supply chain performance. We prove the existence of the optimal pricing and replenishment policies when demand has a linear additive form and the distribution of the uncertainty component has a nondecreasing failure rate. We numerically compare the relative performance of RFM to a price‐only contract and we find that RFM results in greater profit for the supply chain than the price‐only contract in a variety of scenarios. We find that RFM can lead to Pareto‐improving solutions where both the supplier and the retailer earn more profit than under a price‐only contract. Finally, we compare RFM to a buyback contract and explore the implications of allowing the fixed markup parameter to be endogenous to the model. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006.     

Interdiction models for delaying adversarial attacks against critical information technology infrastructure

Information technology (IT) infrastructure relies on a globalized supply chain that is vulnerable to numerous risks from adversarial attacks. It is important to protect IT infrastructure from these dynamic, persistent risks by delaying adversarial exploits. In this paper, we propose max‐min interdiction models for critical infrastructure protection that prioritizes cost‐effective security mitigations to maximally delay adversarial attacks. We consider attacks originating from multiple adversaries, each of which aims to find a “critical path” through the attack surface to complete the corresponding attack as soon as possible. Decision‐makers can deploy mitigations to delay attack exploits, however, mitigation effectiveness is sometimes uncertain. We propose a stochastic model variant to address this uncertainty by incorporating random delay times. The proposed models can be reformulated as a nested max‐max problem using dualization. We propose a Lagrangian heuristic approach that decomposes the max‐max problem into a number of smaller subproblems, and updates upper and lower bounds to the original problem via subgradient optimization. We evaluate the perfect information solution value as an alternative method for updating the upper bound. Computational results demonstrate that the Lagrangian heuristic identifies near‐optimal solutions efficiently, which outperforms a general purpose mixed‐integer programming solver on medium and large instances.     

An asymptotically optimal greedy heuristic for the multiperiod single‐sourcing problem: The cyclic case

The dynamics of the environment in which supply chains evolve requires that companies frequently redesign their logistics distribution networks. In this paper we address a multiperiod single‐sourcing problem that can be used as a strategic tool for evaluating the costs of logistics network designs in a dynamic environment. The distribution networks that we consider consist of a set of production and storage facilities, and a set of customers who do not hold inventories. The facilities face production capacities, and each customer's demand needs to be delivered by a single facility in each period. We deal with the assignment of customers to facilities, as well as the location, timing, and size of inventories. In addition, to mitigate start and end‐of‐study effects, we view the planning period as a typical future one, which will repeat itself. This leads to a cyclic model, in which starting and ending inventories are equal. Based on an assignment formulation of the problem, we propose a greedy heuristic, and prove that this greedy heuristic is asymptotically feasible and optimal in a probabilistic sense. We illustrate the behavior of the greedy heuristic, as well as some improvements where the greedy heuristic is used as the starting point of a local interchange procedure, on a set of randomly generated test problems. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 412–437, 2003     

Single‐commodity stochastic network design under demand and topological uncertainties with insufficient data

Stochastic network design is fundamental to transportation and logistic problems in practice, yet faces new modeling and computational challenges resulted from heterogeneous sources of uncertainties and their unknown distributions given limited data. In this article, we design arcs in a network to optimize the cost of single‐commodity flows under random demand and arc disruptions. We minimize the network design cost plus cost associated with network performance under uncertainty evaluated by two schemes. The first scheme restricts demand and arc capacities in budgeted uncertainty sets and minimizes the worst‐case cost of supply generation and network flows for any possible realizations. The second scheme generates a finite set of samples from statistical information (e.g., moments) of data and minimizes the expected cost of supplies and flows, for which we bound the worst‐case cost using budgeted uncertainty sets. We develop cutting‐plane algorithms for solving the mixed‐integer nonlinear programming reformulations of the problem under the two schemes. We compare the computational efficacy of different approaches and analyze the results by testing diverse instances of random and real‐world networks. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 154–173, 2017     

Opportunistic retooling of a flexible machine subject to failure

A set of jobs can be processed without interruption by a flexible machine only if the set of tools required by all jobs can be loaded in the tool magazine. However, in practice the total number of tools required by a job set would exceed the tool magazine capacity. In such situations, the job set has to be carefully partitioned at the start of the production run such that each partition can be processed without interruption. During the production run, if there are unscheduled machine downtimes due to machine failure, this provides an additional opportunity to optimally retool the magazine for a smaller job set consisting of just the unprocessed jobs. In this paper, we study job sequencing rules that allow us to minimize the total expected cost of machine down time due to machine failures and magazine retooling, assuming a dynamic re‐sequencing of the unprocessed jobs after each machine failure. Using these rules, we develop a branch‐and‐bound heuristic that allows us to solve problems of reasonable size. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 79–97, 2001     

Outbound supply chain network design with mode selection and lead time considerations

We present a large‐scale network design model for the outbound supply chain of an automotive company that considers transportation mode selection (road vs. rail) and explicitly models the relationship between lead times and the volume of flow through the nodes of the network. We formulate the problem as a nonlinear zero‐one integer program, reformulate it to obtain a linear integer model, and develop a Lagrangian heuristic for its solution that gives near‐optimal results in reasonable time. We also present scenario analyses that examine the behavior of the supply chain under different parameter settings and the performance of the solution procedures under different experimental conditions. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

A three‐stage procurement optimization problem under uncertainty

This article examines a problem faced by a firm procuring a material input or good from a set of suppliers. The cost to procure the material from any given supplier is concave in the amount ordered from the supplier, up to a supplier‐specific capacity limit. This NP‐hard problem is further complicated by the observation that capacities are often uncertain in practice, due for instance to production shortages at the suppliers, or competition from other firms. We accommodate this uncertainty in a worst‐case (robust) fashion by modeling an adversarial entity (which we call the “follower”) with a limited procurement budget. The follower reduces supplier capacity to maximize the minimum cost required for our firm to procure its required goods. To guard against uncertainty, the firm can “protect” any supplier at a cost (e.g., by signing a contract with the supplier that guarantees supply availability, or investing in machine upgrades that guarantee the supplier's ability to produce goods at a desired level), ensuring that the anticipated capacity of that supplier will indeed be available. The problem we consider is thus a three‐stage game in which the firm first chooses which suppliers' capacities to protect, the follower acts next to reduce capacity from unprotected suppliers, and the firm then satisfies its demand using the remaining capacity. We formulate a three‐stage mixed‐integer program that is well‐suited to decomposition techniques and develop an effective cutting‐plane algorithm for its solution. The corresponding algorithmic approach solves a sequence of scaled and relaxed problem instances, which enables solving problems having much larger data values when compared to standard techniques. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Stochastic production capacity: A bane or a boon for quick response supply chains?

The quick response (QR) system that can cope with demand volatility by shortening lead time has been well studied in the literature. Much of the existing literature assumes implicitly or explicitly that the manufacturers under QR can always meet the demand because the production capacity is always sufficient. However, when the order comes with a short lead time under QR, availability of the manufacturer's production capacity is not guaranteed. This motivates us to explore QR in supply chains with stochastic production capacity. Specifically, we study QR in a two-echelon supply chain with Bayesian demand information updating. We consider the situation where the manufacturer's production capacity under QR is uncertain. We first explore how stochastic production capacity affects supply chain decisions and QR implementation. We then incorporate the manufacturer's ability to expand capacity into the model. We explore how the manufacturer determines the optimal capacity expansion decision, and the value of such an ability to the supply chain and its agents. Finally, we extend the model to the two-stage two-ordering case and derive the optimal ordering policy by dynamic programming. We compare the single-ordering and two-ordering cases to generate additional managerial insights about how ordering flexibility affects QR when production capacity is stochastic. We also explore the transparent supply chain and find that our main results still hold.     

An integrated electric power supply chain and fuel market network framework: Theoretical modeling with empirical analysis for New England

In this article, we develop a novel electric power supply chain network model with fuel supply markets that captures both the economic network transactions in energy supply markets and the physical network transmission constraints in the electric power network. The theoretical derivation and analysis are done using the theory of variational inequalities. We then apply the model to a specific case, the New England electric power supply chain, consisting of six states, five fuel types, 82 power generators, with a total of 573 generating units, and 10 demand market regions. The empirical case study demonstrates that the regional electric power prices simulated by our model match the actual electricity prices in New England very well. We also compute the electric power prices and the spark spread, an important measure of the power plant profitability, under natural gas and oil price variations. The empirical examples illustrate that in New England, the market/grid‐level fuel competition has become the major factor that affects the influence of the oil price on the natural gas price. Finally, we utilize the model to quantitatively investigate how changes in the demand for electricity influence the electric power and the fuel markets from a regional perspective. The theoretical model can be applied to other regions and multiple electricity markets under deregulation to quantify the interactions in electric power/energy supply chains and their effects on flows and prices. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Coping with shortages caused by disruptive events in automobile supply chains

Unpredictable disruptive events significantly increase the difficulty of the management of automobile supply chains. In this paper, we propose an automobile production planning problem with component chips substitution in a finite planning horizon. The shortage of one chip can be compensated by another chip of the same type with a higher-end feature at an additional cost. Therefore, the automobile manufacturer can divert the on-hand inventory of chips to product lines that are more profitable in the event of shortages caused by supply chain disruptions. To cope with this, we propose a max-min robust optimization model that captures the uncertain supplies of chips. We show that the robust model has a mixed-integer programming equivalence that can be solved by a commercial IP solver directly. We compare the max-min robust model with the corresponding deterministic and two-stage stochastic models for the same problem through extensive numerical experiments. The computational results show that the max-min robust model outperforms the other two models in terms of the average and worst-case profits.     

The graph association problem: Mathematical models and a lagrangian heuristic

Graph association is the problem of merging many graphs that collectively describe a set of possibly repetitive entities and relationships into a single graph that contains unique entities and relationships. As a form of data association, graph association can be used to identify when two sensors are observing the same object so information from both sensors can be combined and analyzed in a meaningful and consistent way. Graph association between two graphs is related to the problem of graph matching, and between multiple graphs it is related to the common labeling of a graph set (also known as multiple graph matching) problem. This article contribution is to formulate graph association as a binary linear program and introduce a heuristic for solving multiple graph association using a Lagrangian relaxation approach to address issues with between‐graph transitivity requirements. The algorithms are tested on a representative dataset. The developed model formulation was found to accurately solve the graph association problem. Furthermore, the Lagrangian heuristic was found to solve the developed model within 3% of optimal on many problem instances, and found better solutions to large problems than is possible by directly using CPLEX. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Integrating decisions with advance supply information in an assemble-to-order system

We study a periodic-review assemble-to-order (ATO) system with multiple components and multiple products, in which the inventory replenishment for each component follows an independent base-stock policy and stochastic product demands are satisfied according to a First-Come-First-Served rule. We assume that the replenishment for various component suffers from lead time uncertainty. However, the decision maker has the so-called advance supply information (ASI) associated with the lead times and thus can take advantage of the information for system optimization. We propose a multistage stochastic integer program that incorporates ASI to address the joint optimization of inventory replenishment and component allocation. The optimal base-stock policy for the inventory replenishment is determined using the sample average approximation algorithm. Also, we provide a modified order-based component allocation (MOBCA) heuristic for the component allocation. We additionally consider a special case of the variable lead times where the resulting two-stage stochastic programming model can be characterized as a single-scenario case of the proposed multistage model. We carry out extensive computational studies to quantify the benefits of integrating ASI into joint optimization and to explore the possibility of employing the two-stage model as a relatively efficient approximation scheme for the multistage model.     

Should firms conceal information when dealing with common suppliers?

A firm making quantity decision under uncertainty loses profit if its private information is leaked to competitors. Outsourcing increases this risk as a third party supplier may leak information for its own benefit. The firm may choose to conceal information from the competitors by entering in a confidentiality agreement with the supplier. This, however, diminishes the firm's ability to dampen competition by signaling a higher quantity commitment. We examine this trade‐off in a stylized supply chain in which two firms, endowed with private demand information, order sequentially from a common supplier, and engage in differentiated quantity competition. In our model, the supplier can set different wholesale prices for firms, and the second‐mover firm could be better informed. Contrary to what is expected, information concealment is not always beneficial to the first mover. We characterize conditions under which the first mover firm will not prefer concealing information. We show that this depends on the relative informativeness of the second mover and is moderated by competition intensity. We examine the supplier's incentive in participating in information concealment, and develop a contract that enables it for wider set of parameter values. We extend our analysis to examine firms' incentive to improve information. © 2014 Wiley Periodicals, Inc. 62:1–15, 2015     

Revenue management with aircraft reassignment flexibility

A well‐studied problem in airline revenue management is the optimal allocation of seat inventory among different fare‐classes, given a capacity for the flight and a demand distribution for each class. In practice, capacity on a flight does not have to be fixed; airlines can exercise some flexibility on the supply side by swapping aircraft of different capacities between flights as partial booking information is gathered. This provides the airline with the capability to more effectively match their supply and demand. In this paper, we study the seat inventory control problem considering the aircraft swapping option. For theoretical and practical purposes, we restrict our attention to the class of booking limit policies. Our analytical results demonstrate that booking limits considering the swapping option can be considerably different from those under fixed capacity. We also show that principles on the relationship between the optimal booking limits and demand characteristics (size and risk) developed for the fixed‐capacity problem no longer hold when swapping is an option. We develop new principles and insights on how demand characteristics affect the optimal booking limits under the swapping possibility. We also develop an easy to implement heuristic for determining the booking limits under the swapping option and show, through a numerical study, that the heuristic generates revenues close to those under the optimal booking limits. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011