Search

In the modern era, abundant information is easily accessible from various sources, however, only a few of these sources are reliable as they mostly contain unverified contents. We develop a system to validate the truthfulness of a given statement together with underlying evidence. The proposed system provides supporting evidence when the statement is tagged as false. Our work relies on an inference method on a knowledge graph (KG) to identify the truthfulness of statements. In order to extract the evidence of falseness, the proposed algorithm takes into account combined knowledge from KG and ontologies. The system shows very good results as it provides valid and concise evidence. The quality of KG plays a role in the performance of the inference method which explicitly affects the performance of our evidence-extracting algorithm. [ABSTRACT FROM AUTHOR]

This paper proposes an active learning algorithm and models which can gradually learn individual’s preference through pairwise comparisons. The active learning scheme aims at finding individual’s most preferred choice (e.g. an airline itinerary) with minimized number of pairwise comparisons. The pairwise comparisons are encoded into probabilistic models based on assumptions of choice models and deep Gaussian processes. More specifically, this paper develops two novel probabilistic models assuming correlated Gumbel noises and latent utility functions. One is based on shallow Gaussian priors and the other assumes deep Gaussian priors. In the active learning algorithm, the next-to-compare decision is determined by an original acquisition function. The proposed algorithm and models have been benchmarked using functions with multiple local optima and one public airline itinerary dataset. In both experiments, nests are designed to capture correlated Gumbel noises. The experiments indicate the effectiveness of our active learning algorithm and models. The deep Gaussian models are proven to find the best choice with a lower number of pairwise comparisons than the shallow one. In both experiments, deep Gaussian models outperform the shallow model. The shallow model is recommended when the choice set is large and less computational time is required (e.g. in one experiment, deep Gaussian models require approximately 60%-70% more time on average). [ABSTRACT FROM AUTHOR]

Retailers procure inventory by placing purchase orders (POs) with suppliers. POs specify product price, quantity, quality, delivery times, and other aspects of the fulfillment process, such as carton labeling requirements and packaging formats. When servicing an order, a supplier may fail to meet the fulfillment terms, thus committing a fulfillment error and triggering a chargeback penalty. We collect supplier compliance manuals from 111 retailers to characterize fulfillment errors and chargebacks in practice. The majority of chargeback penalties listed by retailers pertain to execution quality: aspects of the fulfillment process beyond product price, quantity, quality, and delivery time. We use an empirically grounded analytical model in combination with game‐theoretic analysis to demonstrate that the chargebacks most commonly used in practice do a poor job coordinating supply chains around execution quality. [ABSTRACT FROM AUTHOR]

We present an algorithm for L1-norm kernel PCA and provide a convergence analysis for it. While an optimal solution of L2-norm kernel PCA can be obtained through matrix decomposition, finding that of L1-norm kernel PCA is not trivial due to its non-convexity and non-smoothness. We provide a novel reformulation through which an equivalent, geometrically interpretable problem is obtained. Based on the geometric interpretation of the reformulated problem, we present a “fixed-point” type algorithm that iteratively computes a binary weight for each observation. As the algorithm requires only inner products of data vectors, it is computationally efficient and the kernel trick is applicable. In the convergence analysis, we show that the algorithm converges to a local optimal solution in a finite number of steps. Moreover, we provide a rate of convergence analysis, which has been never done for any L1-norm PCA algorithm, proving that the sequence of objective values converges at a linear rate. In numerical experiments, we show that the algorithm is robust in the presence of entry-wise perturbations and computationally scalable, especially in a large-scale setting. Lastly, we introduce an application to outlier detection where the model based on the proposed algorithm outperforms the benchmark algorithms. [ABSTRACT FROM AUTHOR]

Subset selection in multiple linear regression aims to choose a subset of candidate explanatory variables that tradeoff fitting error (explanatory power) and model complexity (number of variables selected). We build mathematical programming models for regression subset selection based on mean square and absolute errors, and minimal-redundancy–maximal-relevance criteria. The proposed models are tested using a linear-program-based branch-and-bound algorithm with tailored valid inequalities and big M values and are compared against the algorithms in the literature. For high dimensional cases, an iterative heuristic algorithm is proposed based on the mathematical programming models and a core set concept, and a randomized version of the algorithm is derived to guarantee convergence to the global optimum. From the computational experiments, we find that our models quickly find a quality solution while the rest of the time is spent to prove optimality; the iterative algorithms find solutions in a relatively short time and are competitive compared to state-of-the-art algorithms; using ad-hoc big M values is not recommended. [ABSTRACT FROM AUTHOR]

In this research, we address the railway multiterritory dispatch planning (RMTDP) problem. The goal of the RMTDP problem is to find the optimal movement of trains across consecutive dispatch territories, and it is one of the major challenges that decision makers face on a daily basis. It ideally takes into account the correct placement of maintenance windows, remaining capacity of terminals, and availability of train crews, among other critical aspects such as locomotive balance, fueling locations, and inspections. Although these train movement plans are made at the corridor level, which comprises several dispatch territories, when it comes to execution, the meet–pass decisions are made at the individual dispatch territories. This notion causes disruptions and misalignment at the boundaries of dispatch territories. The approach in this paper aims at finding a holistic conflict-free master plan by optimally matching train lineups at territory boundaries and smoothly routing trains through bottlenecks. We propose an efficient solution approach that iteratively constructs a master scheduling plan while minimizing the amount of train delay within a given planning horizon. This is accomplished by designing a time–space network model to identify feasible schedules and developing a mathematical programming–based heuristic to solve the underlying model. A thorough computational study shows the effectiveness of our heuristic approach, as we report reasonable average run times of 3.0 and 6.5 minutes to solve instances of moderate to large size problems, respectively. The results obtained from the algorithm using test snapshots from a Class I railroad company have been shown to assistant chief dispatchers and have received encouraging feedback for applicability. [ABSTRACT FROM AUTHOR]

In production planning in the glass container industry, machine-dependent setup times and costs are incurred for switch overs from one product to another. The resulting multi-item capacitated lot-sizing problem has sequence-dependent setup times and costs. We present two novel linear mixed-integer programming formulations for this problem, incorporating all the necessary features of setup carryovers. The compact formulation has polynomially many constraints, whereas the stronger formulation uses an exponential number of constraints that can be separated in polynomial time. We also present a five-step heuristic that is effective both in finding a feasible solution (even for tightly capacitated instances) and in producing good solutions to these problems. We report computational experiments. [ABSTRACT FROM AUTHOR]

We introduce a semi-supervised discrete choice model with algorithmic approaches to estimate choice models when relatively few requests have actual preferences but the majority only have the choice sets. Two classic semi-supervised learning algorithms, the expectation maximization algorithm and the cluster-and-label algorithm, have been adapted to our choice modeling problem setting. We also develop two new algorithms based on the cluster-and-label algorithm. The new algorithms use the Bayesian Information Criterion to evaluate a clustering setting to automatically generate new clusters out of existing clusters and adjust the number of clusters. Two computational studies focusing on travel demand forecasting (i.e., a hotel booking case and a large-scale airline itinerary shopping case) are presented to evaluate the prediction accuracy and computational effort of the proposed algorithms. Algorithmic recommendations are rendered under various scenarios based on the hotel booking case while economic insights are derived based on the itinerary shopping case. [ABSTRACT FROM AUTHOR]

An operator of a network of battery swap stations for electric vehicles must make a long-term investment decision on the number of batteries and charging bays in the system and periodic short-term decisions on when and how many batteries to recharge. Both decisions must be made concurrently, because there exists a trade-off between the long-term investment in batteries and charging bays, and short-term expenses for operating the system. Costs for electric energy as well as demand rates for batteries are stochastic: We consider an infinite time horizon for operation of the system. We derive an optimization problem, which cannot be solved optimally in a reasonable time for real world instances. By optimally solving various small problem instances, we show the mechanics of the model and the influence of its parameters on the optimal cost. We then develop a near-optimal solution heuristic based on Monte Carlo sampling following the ideas of approximate dynamic programming for the infinite horizon dynamic program. We show that operating battery swap stations in a network where lateral transshipments are allowed can substantially decrease expected operating costs. The online appendix is available at https://doi.org/10.1287/trsc.2017.0781 [ABSTRACT FROM AUTHOR]

As teams of professional leagues are becoming more and more analytically driven, the interest in effective data management and access of sports plays has dramatically increased. In this article, we present a retrieval system that can quickly find the most relevant plays from historical games given an input query. To search through a large number of games at an interactive speed, our system is built upon a distributed framework so that each query-result pair is evaluated in parallel. We also propose a pairwise learning to rank approach to improve search ranking based on users' clickthrough behavior. The similarity metric in training the rank function is based on automatically learnt features from a convolutional autoencoder. Finally, we showcase the efficacy of our learning to rank approach by demonstrating rank quality in a user study. [ABSTRACT FROM AUTHOR]

Principal component analysis (PCA) is often used to reduce the dimension of data by selecting a few orthonormal vectors that explain most of the variance structure of the data. L1 PCA uses the L1 norm to measure error, whereas the conventional PCA uses the L2 norm. For the L1 PCA problem minimizing the fitting error of the reconstructed data, we propose three algorithms based on iteratively reweighted least squares. We first develop an exact reweighted algorithm. Next, an approximate version is developed based on eigenpair approximation when the algorithm is near convergent. Finally, the approximate version is extended based on stochastic singular value decomposition. We provide convergence analyses, and compare their performance against benchmark algorithms in the literature. The computational experiment shows that the proposed algorithms consistently perform the best and the scalability is improved as we use eigenpair approximation and stochastic singular value decomposition. [ABSTRACT FROM AUTHOR]

Planning a trip with an electric vehicle requires consideration of both battery dynamics and the availability of charging infrastructure. Recharging costs for an electric vehicle, which increase as the battery's charge level increases, are fundamentally different than refueling costs for conventional vehicles, which do not depend on the amount of fuel already in the tank. Furthermore, the viability of any route requiring recharging is sensitive to the availability of charging stations along the way. In this paper, we study the problem of finding an optimal adaptive routing and recharging policy for an electric vehicle in a network. Each node in the network represents a charging station and has an associated probability of being available at any point in time or occupied by another vehicle. We develop efficient algorithms for finding an optimal a priori routing and recharging policy and then present solution approaches to an adaptive problem that build on a priori policy. We present two heuristic methods for finding adaptive policies-one with adaptive recharging decisions only and another with both adaptive routing and recharging decisions. We then further enhance our solution approaches to a special case of the grid network. We conduct numerical experiments to demonstrate the empirical performance of our solutions and provide insights to our findings. The online appendix is available at . [ABSTRACT FROM AUTHOR]

Objectives: Identifying stroke during a 9-1-1 call is critical to timely prehospital care. However, emergency medical dispatchers (EMDs) recognize stroke in less than half of 9-1-1 calls, potentially due to the words used by callers to communicate stroke signs and symptoms. We hypothesized that callers do not typically use words and phrases considered to be classical descriptors of stroke, such as focal neurologic deficits, but that a mixed-methods approach can identify words and phrases commonly used by 9-1-1 callers to describe acute stroke victims. Methods: We performed a mixed-method, retrospective study of 9-1-1 call audio recordings for adult patients with confirmed stroke whowere transported by ambulance in a large urban city. Content analysis, a qualitative methodology, and computational linguistics, a quantitative methodology, were used to identify key words and phrases used by 9-1-1 callers to describe acute stroke victims. Because a caller's level of emotional distress contributes to the communication during a 9-1-1 call, the Emotional Content and Cooperation Score was scored by a multidisciplinary team. Results: Atotal of 110 9-1-1 calls, received between June and September 2013, were analyzed. EMDs recognized stroke in 48% of calls, and the emotional state of most callers (95%) was calm. In 77% of calls in which EMDs recognized stroke, callers specifically used the word "stroke"; however, the word "stroke" was used in only 38% of calls. Vague, non-specific words and phrases were used to describe stroke victims' symptoms in 55% of calls, and 45% of callers used distractor words and phrases suggestive of non-stroke emergencies. Focal neurologic symptoms were described in 39% of calls. Computational linguistics identified 9 key words that were more commonly used in calls where the EMD identified stroke. These words were concordant with terms identified through qualitative content analysis. Conclusions:Most 9-1-1 callers used vague, non-specific, or distractor words and phrases and infrequently provide classic stroke descriptions during 9-1-1 calls for stroke. Both qualitative and quantitative methodologies identified similar key words and phrases associated with accurate EMD stroke recognition. This study suggests that tools incorporating commonly used words and phrases could potentially improve EMD stroke recognition. [ABSTRACT FROM AUTHOR]

Current consensus holds that 1) passing through wholesale electricity clearing prices to end-use consumers will produce maximal efficiency gains and 2) simpler forms of time-varying retail rates will capture only a small portion of potential benefits. We show that neither holds in the presence of capacity costs typical in U.S. wholesale markets. Using an optimization model describing the short-term problem faced by an electricity retailer, we find hourly prices that optimally pass through capacity costs. We estimate benefits for a retailer using these prices as well as optimal configurations of a number of time-varying rate structures. Testing a range of realistic assumptions, we find that in the absence of a well-designed demand charge, passing through clearing prices may miss up to three quarters of the benefits possible from optimal hourly prices. By contrast, a simpler critical peak pricing structure enables retailers to achieve approximately two-thirds of the total possible benefits. [ABSTRACT FROM AUTHOR]

OVERVIEW: This study explores the concept of big data and whether, and to what extent, it might affect R&D management in the future. Through extensive discussions to dissect the nature of big data and to achieve a common understanding of what it represents, a research framework was constructed to analyze the impact of big data based on its potential to inform, enable, and transform or disrupt R&D management across four dimensions: strategy, people, technology, and process integration. A literature review, interviews with experts, and case studies of organizations using big data demonstrate that this phenomenon will have significant implications for R&D and innovation management, although the nature and extent of that impact is somewhat uneven among different industry sectors. [ABSTRACT FROM AUTHOR]

Recharging decisions for electric vehicles require many special considerations because of battery dynamics. Battery longevity is prolonged by recharging less frequently and at slower rates, and also by not charging the battery too close to its maximum capacity. In this paper, we address the problem of finding an optimal recharging policy for an electric vehicle along a given path. The path consists of a sequence of nodes, each representing a charging station, and the driver must decide where to stop and how much to recharge at each stop. We present efficient algorithms for finding an optimal policy in general instances with deterministic travel costs and homogeneous charging stations, and also for two specialized cases-one where the vehicle can stop anywhere along the path to recharge and another with equidistant charging stations along the path. In addition, we develop two heuristic procedures that we characterize analytically and explore empirically. We further analyze and test our solution methods on model variations that include stochastic travel costs and nonhomogeneous charging stations. [ABSTRACT FROM AUTHOR]

We propose a clustering-based iterative algorithm to solve certain optimization problems in machine learning, where we start the algorithm by aggregating the original data, solving the problem on aggregated data, and then in subsequent steps gradually disaggregate the aggregated data. We apply the algorithm to common machine learning problems such as the least absolute deviation regression problem, support vector machines, and semi-supervised support vector machines. We derive model-specific data aggregation and disaggregation procedures. We also show optimality, convergence, and the optimality gap of the approximated solution in each iteration. A computational study is provided. [ABSTRACT FROM AUTHOR]

In order to accept future high-yield booking requests, airlines protect seats from low-yield passengers. More seats may be reserved when passengers faced with closed fare classes can upsell to open higher fare classes. We address the airline revenue management problem with capacity nesting and customer upsell, and formulate this problem by a stochastic optimization model to determine a set of static protection levels for each itinerary. We apply an approximate dynamic programming framework to approximate the objective function by piecewise linear functions, whose slopes (marginal revenue) are iteratively updated and returned by an efficient heuristic that simultaneous handles both nesting and upsells. The resulting allocation policy is tested over a real airline network and benchmarked against the randomized linear programming bid-price policy under various demand settings. Simulation results suggest that the proposed allocation policy significantly outperforms when incremental demand or upsell probability are high. Structural analyses are also provided for special demand dependence cases. [ABSTRACT FROM AUTHOR]

This paper presents the development of a novel vehicle-routing-based algorithm for optimizing component pick-up and placement on a collect-and-place type machine in printed circuit board manufacturing. We present a two-phase heuristic that produces solutions of remarkable quality with respect to other known approaches in a reasonable amount of computational time. In the first phase, a construction procedure is used combining greedy aspects and solutions to subproblems modeled as a generalized traveling salesman problem and quadratic assignment problem. In the second phase, this initial solution is refined through an iterative framework requiring an integer programming step. A detailed description of the heuristic is provided and extensive computational results are presented. [ABSTRACT FROM AUTHOR]

In recent supply chains, often operating multiple delivery modes such as standard freight shipping and air is an effective way of addressing both delivery lead time uncertainties and service rates. We propose a model on how to optimally operate multiple delivery modes. We consider a serial supply chain and an expediting option from intermediate installations to the downstream of the chain. The goods move stochastically among the installations and the system faces a stochastic demand. We identify systems that yield simple optimal policies, in which both regular ordering and expediting follow a variant of the base stock policy. Expediting allows the system to be leaner due to the reduced regular order amount. In addition, we provide managerial insights linking expediting, base stock levels, and expediting costs based on analytical and numerical results. [ABSTRACT FROM AUTHOR]

Purchase orders specify many aspects of a fulfillment process, including item quantity, delivery time, carton labeling, bar coding, electronic data interchange, retail ticketing, and others. These fulfillment terms are instrumental for highly optimized retail supply chains employing automation and techniques such as pack-by-store. When fulfilling a purchase order, a supplier may commit a fulfillment error, i.e., the supplier may fail to adhere to the terms specified by the retailer. The retailer may then penalize the supplier for the fulfillment error via a chargeback deduction, which reduces the supplier's revenue. We present a study of the fulfillment errors and chargebacks that occur in practice using data collected from a major retailer's distribution center. While fulfillment errors involving incorrect product quantities and delivery times have received the most attention in the literature, we find that the majority of fulfillment errors in the context we study involve documentation, bar coding, and retail ticketing. We refer to these as correctable fulfillment errors, since they are amended at the retailer's distribution center through rework. We develop a model of inventory management with correctable fulfillment errors and use the retailer's data to assess the cost of these correctable fulfillment errors to the retailer's inventory system. Our research provides guidance to managers in identifying products and suppliers that impose large fulfillment error costs as well as in setting appropriate chargebacks for fulfillment errors. [ABSTRACT FROM AUTHOR]

Investigations have been performed into using clustering methods in data mining time-series data from smart meters. The problem is to identify patterns and trends in energy usage profiles of commercial and industrial customers over 24-h periods and group similar profiles. We tested our method on energy usage data provided by several U.S. power utilities. The results show accurate grouping of accounts similar in their energy usage patterns, and potential for the method to be utilized in energy efficiency programs. [ABSTRACT FROM AUTHOR]

The current scarcity of public charging infrastructure is one of the major barriers to mass household adoption of plug-in electric vehicles (PEVs). Although most PEV drivers can recharge their vehicles at home, the limited driving range of the vehicles restricts their usefulness for long-distance travel. In this paper, an agent-based information system is presented for identifying patterns in residential PEV ownership and driving activities to enable strategic deployment of new charging infrastructure. Driver agents consider their own driving activities within the simulated environment, in addition to the presence of charging stations and the vehicle ownership of others in their social network, when purchasing a new vehicle. Aside from conventional vehicles, drivers may select among multiple electric alternatives, including two PEV options. The Chicagoland area is used as a case study to demonstrate the model, and several different deployment scenarios are analyzed. [ABSTRACT FROM AUTHOR]

We present a framework for obtaining fully polynomial time approximation schemes (FPTASs) for stochastic univariate dynamic programs with either convex or monotone single-period cost functions. This framework is developed through the establishment of two sets of computational rules, namely, the calculus of Κ-approximation functions and the calculus of Κ-approximation sets. Using our framework, we provide the first FPTASs for several NP-hard problems in various fields of research such as knapsack models, logistics, operations management, economics, and mathematical finance. Extensions of our framework via the use of the newly established computational rules are also discussed. [ABSTRACT FROM AUTHOR]

Purpose: In airline revenue management, the modeling of the spill and recapture effects is essential for an accurate estimation of the passenger flow and the revenue in a flight network. However, as most current approaches toward spill and recapture involve either non-linearity or a tremendous amount of additional variables, it is computationally intractable to apply those techniques to the classical network design and capacity planning models. Design/methodology: We present a new framework that incorporates the spill and recapture effects, where the spill from an itinerary is recaptured by other itineraries based on their attractiveness. The presented framework distributes the accepted demand of an itinerary according to the currently available itineraries, without adding extra variables for the recaptured spill. Due to its compactness, we integrate the framework with the classical capacity planning and network design models. Findings: Our preliminary computational study shows an increase of 1.07% in profitability and a better utilization of the network capacity, on a medium-size North American airline provided by Sabre Airline Solutions. Originality/value: Our investigation leads to a holistic model that tackles the network design and capacity planning simultaneously with an accurate modeling of the spill and re- capture effects. Furthermore, the presented framework for spill and recapture is versatile and can be easily applied to other disciplines such as the hospitality industry and product line design (PLD) problems. [ABSTRACT FROM AUTHOR]

Theoretical analyses of a set of iterated-tour partitioning vehicle routing algorithms applicable to a wide variety of commonly used vehicle routing problem variants are presented. We analyze the worst-case performance of the algorithms and establish tightness of the derived bounds. Among other variants, we capture the cases of pick-up and delivery and multiple depots. We also introduce brand new concepts such as mobile depots, partitioning of customer nodes into groups, and potential opportunistic under-utilization of vehicle capacity by only partially loading the vehicle, among others, which arise from a printed circuit board application. The problems studied are of critical importance in many practical applications. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013 [ABSTRACT FROM AUTHOR]

Traditional approaches in inventory control first estimate the demand distribution among a predefined family of distributions based on data fitting of historical demand observations, and then optimize the inventory control using the estimated distributions. These approaches often lead to fragile solutions whenever the preselected family of distributions was inadequate. In this article, we propose a minimax robust model that integrates data fitting and inventory optimization for the single-item multi-period periodic review stochastic lot-sizing problem. In contrast with the standard assumption of given distributions, we assume that histograms are part of the input. The robust model generalizes the Bayesian model, and it can be interpreted as minimizing history-dependent risk measures. We prove that the optimal inventory control policies of the robust model share the same structure as the traditional stochastic dynamic programming counterpart. In particular, we analyze the robust model based on the chi-square goodness-of-fit test. If demand samples are obtained from a known distribution, the robust model converges to the stochastic model with true distribution under generous conditions. Its effectiveness is also validated by numerical experiments. [ABSTRACT FROM AUTHOR]

We introduce a new combinatorial problem referred to as the component set identification problem, arising in the context of knowledge discovery, information integration, and knowledge source/service composition. The main motivation for studying this problem is the widespread proliferation of digital knowledge sources and services. Considering a granular knowledge domain consisting of a large number of individual bits and pieces of domain knowledge (properties) and a large number of knowledge sources and services that provide mappings between sets of properties, the objective of the component set identification problem is to select a minimum cost combination of knowledge sources that can provide a joint mapping from a given set of initially available properties (initial knowledge) to a set of initially unknown properties (target knowledge). We position the component set identification problem relative to other combinatorial problems and provide a classification scheme for the different variations of the problem. The problem is next modeled on a directed graph and analyzed in terms of its complexity. The directed graph representation is then augmented and transformed into a time-expanded network representation that is subsequently used to develop an exact solution procedure based on integer programming and branch-and-bound. We enhance the solver by developing preprocessing techniques. All findings are supported by computational experiments. [ABSTRACT FROM AUTHOR]

We provide a practical methodology for solving the generalized joint replenishment (GJR) problem, based on a mathematical programming approach to approximate dynamic programming. We show how to automatically generate a value function approximation basis built upon piecewise-linear ridge functions by developing and exploiting a theoretical connection with the problem of finding optimal cyclic schedules. We provide a variant of the algorithm that is effective in practice, and we exploit the special structure of the GJR problem to provide a coherent, implementable framework. [ABSTRACT FROM AUTHOR]

Airline schedule development continues to remain one of the most challenging planning activities for any airline. An airline schedule comprises a list of flights and specifies the origin, destination, scheduled departure, and arrival time of each flight in the airline's network. A critical component of the schedule development activity is the choice of flight block-times, which depend on several factors. Many airlines decide schedule block-times based on fixed percentiles of block-time distributions built from historical data, however, such techniques have not resulted in significantly improved on-time performance (OTP) of the schedule during operations. Thus, from a passenger's perspective, the service-level guarantee of an airline's network continues to be low. We first define two service-level metrics for an airline schedule. The first one is similar to the OTP measure of the U.S. Department of Transportation and we define it as the flight service level. The second metric, called the network service level, is geared toward completion of passenger itineraries. We then develop a stochastic integer programming formulation that optimally perturbs a given schedule to maximize expected profit, while ensuring the two service levels. We also develop a variant of this model that maximizes service levels, while achieving desired network profitability. To solve these models, we develop an efficient algorithm that guarantees optimality. Through extensive computational experiments, using real-world data, we demonstrate that our models and algorithms are efficient and achieve the desired trade-off between service level and profitability. [ABSTRACT FROM AUTHOR]

We address the short-term production planning and scheduling problem coming from the glass container industry. A furnace melts the glass that is distributed to a set of parallel molding machines. Both furnace and machine idleness are not allowed. The resulting multi-machine multi-item continuous setup lotsizing problem with a common resource has sequence-dependent setup times and costs. Production losses are penalized in the objective function since we deal with a capital intensive industry. We present two mixed integer programming formulations for this problem, which are reduced to a network flow type problem. The two formulations are improved by adding valid inequalities that lead to good lower bounds. We rely on a Lagrangian decomposition based heuristic for generating good feasible solutions. We report computational experiments for randomly generated instances and for real-life data on the aforementioned problem, as well as on a discrete lotsizing and scheduling version. [ABSTRACT FROM AUTHOR]

Crane sequencing in container terminals determines the order of ship discharging and loading jobs that quay cranes (QCs) perform, so that the duration of a vessel's stay is minimized. The ship's load profile, berthing time, number of available bays, and QCs are considered. More important, clearance and yard congestion constraints need to be included, which, respectively, ensure that a minimum distance between adjacent QCs is observed and yard storage blocks are not overly accessed at any point in time. In sequencing for a single ship, a mixed-integer programming (MIP) model is proposed, and a heuristic approach based on the model is developed that produces good solutions. The model is then reformulated as a generalized set covering problem and solved exactly by branch and price (B&P). For multiship sequencing, the yard congestion constraints are relaxed in the spirit of Lagrangian relaxation, so that the problem decomposes by vessel into smaller subproblems solved by B&P. An efficient primal heuristic is also designed. Computational experiments reveal that large-scale problems can be solved in a reasonable computational time. [ABSTRACT FROM AUTHOR]

Massive Radio Frequency Identification (RFID) data sets are expected to become commonplace in supply chain management systems. Warehousing and mining this data is an essential problem with great potential benefits for inventory management, object tracking, and product procurement processes. Since RFID tags can be used to identify each individual item, enormous amounts of location-tracking data are generated. With such data, object movements can be modeled by movement graphs, where nodes correspond to locations and edges record the history of item transitions between locations. In this study, we develop a movement graph model as a compact representation of RFID data sets. Since spatiotemporal as well as item information can be associated with the objects in such a model, the movement graph can be huge, complex, and multidimensional in nature. We show that such a graph can be better organized around gateway nodes, which serve as bridges connecting different regions of the movement graph. A graph-based object movement cube can be constructed by merging and collapsing nodes and edges according to an application-oriented topological structure. Moreover, we propose an efficient cubing algorithm that performs simultaneous aggregation of both spatiotemporal and item dimensions on a partitioned movement graph, guided by such a topological structure. [ABSTRACT FROM AUTHOR]

The single-item stochastic inventory control problem is to find an inventory replenishment policy in the presence of independent discrete stochastic demands under periodic review and finite time horizon. In this paper, we prove that this problem is intractable and design for it a fully polynomial-time approximation scheme. [ABSTRACT FROM AUTHOR]

The flow of packages and documents in collective groups, called splits, of an express package carrier consists of picking up the packages by a courier at customers' locations and bringing them to a station for sorting. Next the splits are transported, either in bulk or containerized conveyances, to a major regional sorting facility called the ramp. In this work we focus on the afternoon and evening operations concerned with stations and the ramp. We deal with the sorting decisions at the stations and the ramp, as well as the transportation decisions among these locations. We model these processes by means of a dynamic program where time periods represent time slices in the afternoon and evening. The resulting myopic problem is a linear mixed-integer program. The overall model is solved by approximate dynamic programming where the value function is approximated by a linear function. Further strategies are developed to speed up the algorithm and decrease the time needed to find feasible solutions. The methodology is tested on several instances from an international express package carrier. Our solutions are substantially better than the current best practice. [ABSTRACT FROM AUTHOR]

We devise an algorithm for solving the infinite-dimensional linear programs that arise from general deterministic semi-Markov decision processes on Borel spaces. The algorithm constructs a sequence of approximate primal-dual solutions that converge to an optimal one. The innovative idea is to approximate the dual solution with continuous piecewise linear ridge functions that naturally represent functions defined on a high-dimensional domain as linear combinations of functions defined on only a single dimension. This approximation gives rise to a primal/dual pair of semi-infinite programs, for which we show strong duality. In addition, we prove various properties of the underlying ridge functions. [ABSTRACT FROM AUTHOR]

The tactical planning process of an airline is typically decomposed into several stages among which fleeting, aircraft routing, and crew pairing form the core. In such a decomposed and sequential approach, the output of fleeting forms the input to aircraft routing and crew pairing. In turn, the output to aircraft routing is part of the input to crew pairing. Due to this decomposition, the resulting solution is often suboptimal. We propose a model that completely integrates the fleeting and crew-pairing stages and guarantees feasibility of plane-count feasible aircraft routings, but neglects aircraft maintenance constraints. We design two solution methodologies to solve the model. One is based on a combination of Lagrangian relaxation and column generation, while the other one is a Benders decomposition approach. We conduct computational experiments for a variety of instances obtained from a major carrier. [ABSTRACT FROM AUTHOR]

Due to irregular operations, the crew cost at the end of a month is typically substantially higher than the crew cost projected in planning. We assume that the fleeting and the aircraft routing decisions have already been made. We present a model and a solution methodology that produces robust crew schedules in planning. Besides the objective of minimizing the crew cost, we introduce the objective of maximizing the number of move-up crews, i.e., the crews that can potentially be swapped in operations. To solve the resulting largescale integer program, we use a combination of delayed column generation and Lagrangian relaxation. The restricted master problem is solved by means of Lagrangian relaxation and the "duals" of the restricted master problem, which are used in delayed column generation, and correspond to the Lagrangian multipliers. We report computational experiments that demonstrate the benefits of using the robust crew schedule instead of the traditional one. We evaluate various crew schedules by generating random disruptions and then running a crew recovery module. We compare solutions with respect to the direct crew cost and indirect costs such as uncovered legs, reserved crews, and deadheading. The main conclusion is that robustness leads to reduced operational crew cost; however, in planning the trade-off between the inflated direct crew cost and robustness needs to be exploited judicially. [ABSTRACT FROM AUTHOR]

Semi-Markov decision processes on Borel spaces with deterministic kernels have many practical applications, particularly in inventory theory. Most of the results from general semi-Markov decision processes do not carry over to a deterministic kernel since such a kernel does not provide ‘smoothness.’ We develop infinite dimensional linear programming theory for a general stochastic semi-Markov decision process. We give conditions, general enough to allow deterministic kernels, for solvability and strong duality of the resulting linear programs. By using the developed linear programming theory we give conditions for the existence of a stationary deterministic policy for deterministic kernels, which is optimal among all possible policies. [ABSTRACT FROM AUTHOR]

We establish a duality theory for a broad class of deterministic inventory control problems on continuous spaces that includes the classical joint replenishment problem and inventory routing. Using this theory, we establish the existence of an optimal policy, which has been an open question. We show how a primal-dual pair of infinite dimensional linear programs encode both cyclic and noncyclic schedules, and provide various results regarding cyclic schedules, including an example showing that they need not be optimal. [ABSTRACT FROM AUTHOR]

Recently, a new algorithm for computing an optimal subadditive dual function to an integer program has been proposed. In this paper we show how to apply the algorithm to the set partitioning problem. We give several enhancements to the algorithm and we report computational experiments. The results show that it is tractable to obtain an optimal subadditive function for small and medium size problems. To the best of our knowledge this is the first work that reports computational experiments on computing an optimal subadditive dual function. [ABSTRACT FROM AUTHOR]

Solving LP relaxations of airline crew scheduling models is computationally challenging due to the presence of a large number of variables, complex feasibility rules to generate columns, and nonlinear cost. We perform computational experiments with a nonlinear pricing strategy. We develop a column generation scheme that uses several pruning rules to fathom column enumeration. The pruning rules are categorized into approximate and exact, where the approximate rules might prune columns that would yield an improved objective value. The pruning rules use the fact that columns are paths in a network, and we use shortest path algorithms and their extensions to obtain bounds. [ABSTRACT FROM AUTHOR]

We study the polyhedron of the single node capacitated network design model with integer variable upper bounds. We first give a characterization of valid inequalities that is useful in proving the validity of several classes of inequalities. Next we derive several classes of valid inequalities and we give conditions for them to be facet-defining. Sequence independent lifting is used to obtain additional facets. We conclude by reporting computational results with a branch-and-cut algorithm. [ABSTRACT FROM AUTHOR]