ScholarBank@NUShttps://scholarbank.nus.edu.sgThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Mon, 06 Apr 2020 09:53:06 GMT2020-04-06T09:53:06Z50611- Choice prediction with semidefinite optimization when utilities are correlated"""https://scholarbank.nus.edu.sg/handle/10635/114900Title: Choice prediction with semidefinite optimization when utilities are correlated"""
Authors: Mishra, V.K.; Natarajan, K.; Tao, H.; Teo, C.-P.
Abstract: We consider the problem of making choice prediction by optimizing the expectation of maximum utility in discrete choice situations, and propose a discrete choice model which generates choice probabilities through a semidefinite program. The choice model, termed as the cross moment model (CMM) is parsimonious in that it uses only the mean and covariance information of the utilities. It is encouraging that CMM generates reasonable choice estimates when utilities are correlated even though no distributional assumptions on random utilities are made. © 2012 IEEE.
Sun, 01 Jan 2012 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1149002012-01-01T00:00:00Z
- Asymptotically optimal schedules for single-server flow shop problems with setup costs and timeshttps://scholarbank.nus.edu.sg/handle/10635/44116Title: Asymptotically optimal schedules for single-server flow shop problems with setup costs and times
Authors: Iravani, S.M.R.; Teo, C.P.
Abstract: We consider the processing of M jobs in a flow shop with N stations in which only a single server is in charge of all stations. We demonstrate that for the objective of minimizing the total setup and holding cost, a class of easily implementable schedules is asymptotically optimal. © 2004 Published by Elsevier B.V.
Sat, 01 Jan 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/441162005-01-01T00:00:00Z
- Stochastic transportation-inventory network design problemhttps://scholarbank.nus.edu.sg/handle/10635/44089Title: Stochastic transportation-inventory network design problem
Authors: Shu, J.; Teo, C.-P.; Shen, Z.-J.M.
Abstract: We study the stochastic transportation-inventory network design problem involving one supplier and multiple retailers. Each retailer faces some uncertain demand, and safety stock must be maintained to achieve suitable service levels. However, risk-pooling benefits may be achieved by allowing some retailers to serve as distribution centers for other retailers. The problem is to determine which retailers should serve as distribution centers and how to allocate the other retailers to the distribution centers. Shen et al. (2003) formulated this problem as a set-covering integer-programming model. The pricing problem that arises from the column generation algorithm gives rise to a new class of the submodular function minimization problem. In this paper, we show that by exploiting certain special structures, we can solve the general pricing problem in Shen et al. efficiently. Our approach utilizes the fact that the set of all lines in a two-dimension plane has low VC-dimension. We present computational results on several instances of sizes ranging from 40 to 500 retailers. Our solution technique can be applied to a wide range of other concave cost-minimization problems. © 2005 INFORMS.
Sat, 01 Jan 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/440892005-01-01T00:00:00Z
- Staggering periodic replenishment in multivendor JIT environmentshttps://scholarbank.nus.edu.sg/handle/10635/44029Title: Staggering periodic replenishment in multivendor JIT environments
Authors: Hum, S.-H.; Sharafali, M.; Teo, C.-P.
Abstract: The delivery scheduling problem studied in this paper was motivated by the operation in a large personal computer assembly plant, which was using multisourcing for some of its materials. The company's objective was to design a delivery schedule so that the average inventory level in the factory was minimized. We show that the problem is intimately related to a classical inventory staggering problem, where the focus is on the computation of the peak inventory level associated with the replenishment policy. This connection allows us to show that the delivery scheduling problem is NP-hard. For the two-vendor case with integral replenishment intervals, we propose a generalized form of Homer's scheduling heuristic and obtain performance bounds for the classical inventory staggering problem. Our analysis uses the Chinese remainder theorem in an interesting way. The approach can be generalized to the case with more than two vendors, leading to a strong linear-programming-based lower bound for the inventory staggering problem. We illustrate this technique for the case in which all the replenishment intervals are relatively prime, establishing a bound that is not greater than 140% of the optimal. We examine the implications of these results to the delivery scheduling problem. © 2005 INFORMS.
Sat, 01 Jan 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/440292005-01-01T00:00:00Z
- Persistence in discrete optimization under data uncertaintyhttps://scholarbank.nus.edu.sg/handle/10635/44206Title: Persistence in discrete optimization under data uncertainty
Authors: Bertsimas, D.; Natarajan, K.; Teo, C.-P.
Abstract: An important question in discrete optimization under uncertainty is to understand the persistency of a decision variable, i.e., the probability that it is part of an optimal solution. For instance, in project management, when the task activity times are random, the challenge is to determine a set of critical activities that will potentially lie on the longest path. In the spanning tree and shortest path network problems, when the arc lengths are random, the challenge is to pre-process the network and determine a smaller set of arcs that will most probably be a part of the optimal solution under different realizations of the arc lengths. Building on a characterization of moment cones for single variate problems, and its associated semidefinite constraint representation, we develop a limited marginal moment model to compute the persistency of a decision variable. Under this model, we show that finding the persistency is tractable for zero-one optimization problems with a polynomial sized representation of the convex hull of the feasible region. Through extensive experiments, we show that the persistency computed under the limited marginal moment model is often close to the simulated persistency value under various distributions that satisfy the prescribed marginal moments and are generated independently.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/442062006-01-01T00:00:00Z
- Inventory cost effect of consolidating several one-warehouse multiretailer systemshttps://scholarbank.nus.edu.sg/handle/10635/43929Title: Inventory cost effect of consolidating several one-warehouse multiretailer systems
Authors: Lim, W.-S.; Ou, J.; Teo, C.-P.
Abstract: Consolidation of warehouses is a new trend in global logistics management, and the reduction in order processing and inventory costs is often cited as one of the main motivations. In this note we show that when retailers face constant demand rates and their ordering costs are independent of the warehouse that services them, consolidated systems are rarely suboptimal and always lead to close-to-optimal inventory replenishment costs. In particular, we prove that using two (one) properly selected warehouses, the systemwide inventory replenishment cost is in the worst case at most 2% (14.75%) more than the optimal.
Wed, 01 Jan 2003 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/439292003-01-01T00:00:00Z
- Many-to-one stable matching: Geometry and fairnesshttps://scholarbank.nus.edu.sg/handle/10635/44211Title: Many-to-one stable matching: Geometry and fairness
Authors: Sethuraman, J.; Teo, C.-P.; Qian, L.
Abstract: Baïou and Balinski characterized the stable admissions polytope using a system of linear inequalities. The structure of feasible solutions to this system of inequalities - fractional stable matchings - is the focus of this paper. The main result associates a geometric structure with each fractional stable matching. This insight appears to be interesting in its own right, and can be viewed as a generalization of the lattice structure (for integral stable matchings) to fractional stable matchings. In addition to obtaining simple proofs of many known results, the geometric structure is used to prove the following two results: First, it is shown that assigning each agent their "median" choice among all stable partners results in a stable matching, which can be viewed as a "fair" compromise; second, sufficient conditions are identified under which stable matchings exist in a problem with externalities, in particular, in the stable matching problem with couples. © 2006 INFORMS.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/442112006-01-01T00:00:00Z
- Impact on inventory costs with consolidation of distribution centershttps://scholarbank.nus.edu.sg/handle/10635/44950Title: Impact on inventory costs with consolidation of distribution centers
Authors: Teo, C.P.; Ou, J.; Goh, M.
Abstract: The consolidation of Distribution Centers (DCs) is a new trend in global logistics management, with a reduction in inventory costs often being cited as one of the main benefits. This paper uses an analytical modeling approach to study the impact on facility investment and inventory costs when several DCs are consolidated into a central DC. In particular, our model suggests that consolidation leads to lower total facility investment and inventory costs if the demands are identically and independently distributed, or when they follow independent but possibly nonidentical Poisson processes. This agrees with the conclusion of the classical EOQ and newsvendor models. However, we show by an example that, for general stochastic demand processes, the total facility investment and inventory costs of a consolidated system can be infinitely worse off than that of a decentralized system. This arises mainly because the order replenishment fixed cost yields a cost component proportional to the square root of the mean value of the demand, while the demand uncertainty yields a cost component proportional to the standard deviation of the demand. Whether consolidation is cost effective or not depends on the trade-off between these two components, as indicated by an extensive numerical study. We also propose an algorithm that solves for a distribution system with the total facility investment and inventory costs within √2 of the optimal.
Mon, 01 Jan 2001 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/449502001-01-01T00:00:00Z
- Process flexibility revisited: The graph expander and its applicationshttps://scholarbank.nus.edu.sg/handle/10635/44079Title: Process flexibility revisited: The graph expander and its applications
Authors: Chou, M.C.; Chua, G.A.; Teo, C.-P.; Zheng, H.
Abstract: We examine how to design a flexible process structure for a production system to match supply with demand more effectively. We argue that good flexible process structures are essentially highly connected graphs, and we use the concept of graph expansion (a measure of graph connectivity) to achieve various insights into this design problem. Whereas existing literature on process flexibility has focused on the expected performance of process structure, we analyze in this paper the worst-case performance of the flexible structure design problem under a more general setting, which encompasses a large class of objective functions. Chou et al. [Chou, M. C., G. Chua, C. P. Teo, H. Zheng. 2010. Design for process flexibility: Efficiency of the long chain and sparse structure. Oper. Res. 58(1) 43-58] showed the existence of a sparse process structure that performs nearly as well as the fully flexible system on average, but the approach using random sampling yields few insights into the nature of the process structure. We show that the ë-expander structure, a variant of the graph expander structure (a highly connected but sparse graph) often used in communication networks, is within .-optimality of the fully flexible system for all demand scenarios. Furthermore, the same expander structure works uniformly well for all objective functions in our class. Based on this insight, we derive design guidelines for general nonsymmetrical systems and develop a simple and easy-to-implement heuristic to design flexible process structures. Numerical results show that this simple heuristic performs well for a variety of numerical examples previously studied in the literature and compares favourably even with the best solutions obtained via extensive simulation and known demand distribution. Subject classifications: facilities planning: design; production: flexible manufacturing; networks/graphs: stochastic. Area of review: Manufacturing, Service, and Supply Chain Operations. History: Received December 2008; revisions received May 2010, December 2010; accepted December 2010. © 2011 INFORMS.
Sat, 01 Jan 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/440792011-01-01T00:00:00Z
- Warehouse sizing to minimize inventory and storage costshttps://scholarbank.nus.edu.sg/handle/10635/44924Title: Warehouse sizing to minimize inventory and storage costs
Authors: Goh, M.; Jihong, O.; Chung-Piaw, T.
Abstract: This paper considers a warehouse sizing problem whose objective is to minimize the total cost of ordering, holding, and warehousing of inventory. Unlike typical economic lot sizing models, the warehousing cost structure examined here is not the simple unit rate type, but rather a more realistic step function of the warehouse space to be acquired. In the cases when only one type of stock-keeping unit (SKU) is warehoused, or when multiple SKUs are warehoused, but, with separable inventory costs, closed form solutions are obtained for the optimal warehouse size. For the case of multi-SKUs with joint inventory replenishment cost, a heuristic with a provable performance bound of 94% is provided.
Mon, 01 Jan 2001 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/449242001-01-01T00:00:00Z
- Modified critical fractile approach for a class of partial postponement problemshttps://scholarbank.nus.edu.sg/handle/10635/44048Title: Modified critical fractile approach for a class of partial postponement problems
Authors: Fu, Q.; Lee, C.-Y.; Teo, C.-P.
Abstract: This paper studies a single period partial postponement problem, which is motivated by an inventory planning problem encountered in Reebok NFL replica jersey supply chain. We consider a group of regular products each facing a random demand. There are two stocking options. One is to procure the regular products. The other is to stock a common component which can be customized later to any one of the regular products, after demand realization. We obtain an insightful interpretation of the optimality conditions for this class of problems, and use it to obtain rules of thumb that practitioners can incorporate into their inventory models to determine the stocking levels to minimize the supply chain cost. Instead of proposing a numerical procedure to obtain the optimal solution, we propose an adaptation of the classical critical fractile approach for this class of partial postponement problem. The closed-form formula obtained are surprisingly effective. Our numerical results suggest that this simple approach to inventory planning often comes close to the performance of the optimal solution obtained from numerical method. © 2011 Elsevier B.V.
Sun, 01 Jan 2012 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/440482012-01-01T00:00:00Z
- Newsvendor pricing problem in a two-sided markethttps://scholarbank.nus.edu.sg/handle/10635/44117Title: Newsvendor pricing problem in a two-sided market
Authors: Chou, M.C.; Sim, C.K.; Teo, C.-P.; Zheng, H.
Abstract: We study the pricing problem of a "platform" intermediary to jointly determine the selling price of the platforms (hardware) sold to consumers and the royalty charged to content developers for content (software), when the demands for content and for platforms are interdependent. Our model elucidates the impact of supply chain replenishment costs and demand uncertainty on the strategic issues of platform pricing in a two-sided market. © 2011 Production and Operations Management Society.
Sun, 01 Jan 2012 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/441172012-01-01T00:00:00Z
- Mixed 0-1 linear programs under objective uncertainty: A completely positive representationhttps://scholarbank.nus.edu.sg/handle/10635/44016Title: Mixed 0-1 linear programs under objective uncertainty: A completely positive representation
Authors: Natarajan, K.; Teo, C.P.; Zheng, Z.
Abstract: In this paper, we analyze mixed 0-1 linear programs under objective uncertainty. The mean vector and the second-moment matrix of the nonnegative objective coefficients are assumed to be known, but the exact form of the distribution is unknown. Our main result shows that computing a tight upper bound on the expected value of a mixed 0-1 linear program in maximization form with random objective is a completely positive program. This naturally leads to semidefinite programming relaxations that are solvable in polynomial time but provide weaker bounds. The result can be extended to deal with uncertainty in the moments and more complicated objective functions. Examples from order statistics and project networks highlight the applications of the model. Our belief is that the model will open an interesting direction for future research in discrete and linear optimization under uncertainty. © 2011 INFORMS.
Sat, 01 Jan 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/440162011-01-01T00:00:00Z
- Designing two-echelon supply networkshttps://scholarbank.nus.edu.sg/handle/10635/44102Title: Designing two-echelon supply networks
Authors: Romeijn, H.E.; Shu, J.; Teo, C.-P.
Abstract: A modern distribution network design model needs to deal with the trade-offs between a variety of factors, including (1) location and associated (fixed) operating cost of distribution centers (DCs), (2) total transportation costs, and (3) storage holding and replenishment costs at DCs and retail outlets. In addition, network design models should account for factors such as (4) stockouts, by setting appropriate levels of safety stocks, or (5) capacity concerns, which may affect operating costs in the form of congestion costs. The difficulty of making such trade-offs is compounded by the fact that even finding the optimal two-echelon inventory policy in a fixed and uncapacitated distribution network is already a hard problem. In this paper, we propose a generic modeling framework to address these issues that continues and extends a recent stream of research aimed at integrating insights from modern inventory theory into the supply chain network design domain. Our approach is flexible and general enough to incorporate a variety of important side constraints into the problem. © 2006 Elsevier B.V. All rights reserved.
Mon, 01 Jan 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/441022007-01-01T00:00:00Z
- From CVaR to uncertainty set: Implications in joint chance-constrained optimizationhttps://scholarbank.nus.edu.sg/handle/10635/44178Title: From CVaR to uncertainty set: Implications in joint chance-constrained optimization
Authors: Chen, W.; Sim, M.; Sun, J.; Teo, C.-P.
Abstract: We review and develop different tractable approximations to individual chance-constrained problems in robust optimization on a variety of uncertainty sets and show their interesting connections with bounds on the conditional-value-at-risk (CVaR) measure. We extend the idea to joint chance-constrained problems and provide a new formulation that improves upon the standard approach. Our approach builds on a classical worst-case bound for order statistics problems and is applicable even if the constraints are correlated. We provide an application of the model on a network resource allocation problem with uncertain demand. ©2010 INFORMS.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/441782010-01-01T00:00:00Z
- Design for process flexibility: Efficiency of the long chain and sparse structurehttps://scholarbank.nus.edu.sg/handle/10635/44066Title: Design for process flexibility: Efficiency of the long chain and sparse structure
Authors: Chou, M.C.; Chua, G.A.; Teo, C.-P.; Zheng, H.
Abstract: The concept of chaining, or in more general terms, sparse process structure, has been extremely influential in the process flexibility area, with many large automakers already making this the cornerstone of their business strategies to remain competitive in the industry. The effectiveness of the process strategy, using chains or other sparse structures, has been validated in numerous empirical studies. However, to the best of our knowledge, there have been relatively few concrete analytical results on the performance of such strategies vis-á-vis the full flexibility system, especially when the system size is large or when the demand and supply are asymmetrical. This paper is an attempt to bridge this gap. © 2010 INFORMS.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/440662010-01-01T00:00:00Z
- On a cutting plane heuristic for the stable roommates problem and its applicationshttps://scholarbank.nus.edu.sg/handle/10635/44958Title: On a cutting plane heuristic for the stable roommates problem and its applications
Authors: Teo, C.-P.; Sethuraman, J.
Abstract: We propose a new cutting plane heuristic for the classical stable roommates problem. Our approach utilises a new linear programming formulation for the problem, and the underlying geometric properties of the fractional solution to construct the violated inequality. We test the approach on moderate size problems, with encouraging computational performance. To further illustrate the versatility of this approach, we also show how it can be suitably extended to handle variants of the basic stable roommates model.
Sat, 01 Jan 2000 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/449582000-01-01T00:00:00Z
- On range and response: Dimensions of process flexibilityhttps://scholarbank.nus.edu.sg/handle/10635/44095Title: On range and response: Dimensions of process flexibility
Authors: Chou, M.C.; Chua, G.A.; Teo, C.-P.
Abstract: There are two dimensions to process flexibility: range versus response. Range is the extent to which a system can adapt, while response is the rate at which the system can adapt. Although both dimensions are important, the existing literature does not analytically examine the response dimension vis-a-vis the range dimension. In this paper, we model the response dimension in terms of uniformity of production cost. We distinguish between primary and secondary production where the latter is more expensive. We examine how the range and response dimension interact to affect the performance of the process flexible structure. We provide analytical lower bounds to show that under all scenarios on response flexibility, moderate form of range flexibility (via chaining structure) still manages to accrue non-negligible benefits vis-a-vis the fully flexible structure (the bound is 29.29% when demand is normally distributed). We show further that given limited resources, upgrading system response dimension outperforms upgrading system range dimension in most cases. This confirms what most managers believe in intuitively. We observe also that improving system response can provide even more benefits when coupled with initiatives to reduce demand variability. This is in direct contrast with range flexibility, which is more valuable when the system has higher variability. © 2010 Elsevier B.V. All rights reserved.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/440952010-01-01T00:00:00Z
- Scheduling arrivals to a stochastic service delivery system using copositive coneshttps://scholarbank.nus.edu.sg/handle/10635/117148Title: Scheduling arrivals to a stochastic service delivery system using copositive cones
Authors: Kong, Q.; Lee, C.-Y.; Teo, C.-P.; Zheng, Z.
Abstract: In this paper we investigate a stochastic appointment-scheduling problem in an outpatient clinic with a single doctor. The number of patients and their sequence of arrivals are fixed, and the scheduling problem is to determine an appointment time for each patient. The service durations of the patients are stochastic, and only the mean and covariance estimates are known. We do not assume any exact distributional form of the service durations, and we solve for distributionally robust schedules that minimize the expectation of the weighted sum of patients' waiting time and the doctor's overtime. We formulate this scheduling problem as a convex conic optimization problem with a tractable semidefinite relaxation. Our model can be extended to handle additional support constraints of the service durations. Using the primal-dual optimality conditions, we prove several interesting structural properties of the optimal schedules. We develop an efficient semidefinite relaxation of the conic program and show that we can still obtain near-optimal solutions on benchmark instances in the existing literature. We apply our approach to develop a practical appointment schedule at an eye clinic that can significantly improve the efficiency of the appointment system in the clinic, compared to an existing schedule. ©2013 INFORMS.
Wed, 01 May 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1171482013-05-01T00:00:00Z
- Effective routing and scheduling in adversarial queueing networkshttps://scholarbank.nus.edu.sg/handle/10635/43955Title: Effective routing and scheduling in adversarial queueing networks
Authors: Sethuraman, J.; Teo, C.-P.
Abstract: In an adversarial queueing network, the incoming traffic is decided by an adversary, who operates under a reasonable rate restriction. This model provides a valuable, complementary point of view to that of the traditional queueing network model in which arrivals are modeled by stochastic processes. As a result, the adversarial queueing network model has attracted much attention in recent years, especially as a way of modeling packet injections into a communication network. Our main result is a simple, effective packet routing and scheduling algorithm with a provably good performance. Specifically, our algorithm keeps the system stable (bounded number of packets in the system), with the bound on the number of packets in the system that is O((1 - r) -1), where r can be interpreted as the arrival rate of the packets into the communication network. This improves upon the work of Gamarnik, who designed an algorithm for which the number of packets in the system is O((1 - r) -2); moreover, our result matches the traditional queueing-theoretic number-in-system bound. © 2005 Springer Science+Business Media, Inc.
Sat, 01 Jan 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/439552005-01-01T00:00:00Z
- Procurement management using option contracts: Random spot price and the portfolio effecthttps://scholarbank.nus.edu.sg/handle/10635/44071Title: Procurement management using option contracts: Random spot price and the portfolio effect
Authors: Fu, Q.; Lee, C.-Y.; Teo, C.-P.
Abstract: This article considers the value of portfolio procurement in a supply chain, where a buyer can either procure parts for future demand from sellers using fixed price contracts or, option contracts or tap into the market for spot purchases. A single-period portfolio procurement problem when both the product demand and the spot price are random (and possibly correlated) is examined and the optimal portfolio procurement strategy for the buyer is constructed. A shortest-monotone path algorithm is provided for the general problem to obtain the optimal procurement solution and the resulting expected minimum procurement cost. In the event that demand and spot price are independent, the solution algorithm simplifies considerably. More interestingly, the optimal procurement cost func ion in this case has an intuitive geometrical interpretation that facilitates managerial insights. The portfolio effect, i.e., the benefit of portfolio contract procurement over a single contract procurement is also studied. Finally, an extension to a two-period problem to examine the impact of inventory on the portfolio procurement strategy is discussed. Copyright © "IIE".
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/440712010-01-01T00:00:00Z
- Probabilistic combinatorial optimization: Moments, semidefinite programming, and asymptotic boundshttps://scholarbank.nus.edu.sg/handle/10635/44011Title: Probabilistic combinatorial optimization: Moments, semidefinite programming, and asymptotic bounds
Authors: Bertsimas, D.; Natarajan, K.; Teo, C.-P.
Abstract: We address the problem of evaluating the expected optimal objective value of a 0-1 optimization problem under uncertainty in the objective coefficients. The probabilistic model we consider prescribes limited marginal distribution information for the objective coefficients in the form of moments. We show that for a fairly general class of marginal information, a tight upper (lower) bound on the expected optimal objective value of a 0-1 maximization (minimization) problem can be computed in polynomial time if the corresponding deterministic problem is solvable in polynomial time. We provide an efficiently solvable semidefinite programming formulation to compute this tight bound. We also analyze the asymptotic behavior of a general class of combinatorial problems that includes the linear assignment, spanning tree, and traveling salesman problems, under knowledge of complete marginal distributions, with and without independence. We calculate the limiting constants exactly. © 2004 Society for Industrial and Applied Mathematics.
Sat, 01 Jan 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/440112005-01-01T00:00:00Z
- Distributionally robust mixed integer linear programs: Persistency models with applicationshttps://scholarbank.nus.edu.sg/handle/10635/116873Title: Distributionally robust mixed integer linear programs: Persistency models with applications
Authors: Li, X.; Natarajan, K.; Teo, C.-P.; Zheng, Z.
Abstract: In this paper, we review recent advances in the distributional analysis of mixed integer linear programs with random objective coefficients. Suppose that the probability distribution of the objective coefficients is incompletely specified and characterized through partial moment information. Conic programming methods have been recently used to find distributionally robust bounds for the expected optimal value of mixed integer linear programs over the set of all distributions with the given moment information. These methods also provide additional information on the probability that a binary variable attains a value of 1 in the optimal solution for 0-1 integer linear programs. This probability is defined as the persistency of a binary variable. In this paper, we provide an overview of the complexity results for these models, conic programming formulations that are readily implementable with standard solvers and important applications of persistency models. The main message that we hope to convey through this review is that tools of conic programming provide important insights in the probabilistic analysis of discrete optimization problems. These tools lead to distributionally robust bounds with applications in activity networks, vertex packing, discrete choice models, random walks and sequencing problems, and newsvendor problems. © 2013 Elsevier B.V. All rights reserved.
Sun, 16 Mar 2014 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1168732014-03-16T00:00:00Z
- Process flexibility: Design, evaluation, and applicationshttps://scholarbank.nus.edu.sg/handle/10635/44115Title: Process flexibility: Design, evaluation, and applications
Authors: Chou, M.C.; Teo, C.-P.; Zheng, H.
Abstract: One of the most effective ways of minimizing supply/demand mismatch costs, with little increase in operational costs, is to deploy valuable resources in a flexible and timely manner to meet the realized demand. This notion of flexible processes has significantly changed operations in many manufacturing and service companies. For example, a flexible production system is now commonly used by automobile manufacturers, and a workforce cross-training system is now a common practice in many service industries. However, there is a trade-off between the level of flexibility available in the system and the associated complexity and operating costs. The challenge is to have the "right" level of flexibility to capture the bulk of the benefits from a fully flexible system, while controlling the increase in implementation costs. This paper reviews developments in process flexibility over the past decade. In particular, we focus on the phenomenon, often observed in practice, that a slight increase in process flexibility can lead to a significant improvement in system performance. This review explores the issues from three perspectives: design, evaluation, and applications. We also discuss how the concept of process flexibility has been deployed in several manufacturing and service systems. © 2008 Springer Science+Business Media, LLC.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/441152008-01-01T00:00:00Z
- Benford's law and number selection in fixed-odds numbers gamehttps://scholarbank.nus.edu.sg/handle/10635/44067Title: Benford's law and number selection in fixed-odds numbers game
Authors: Chou, M.C.; Kong, Q.; Teo, C.-P.; Wang, Z.; Zheng, H.
Abstract: In fixed-odds numbers games, the prizes and the odds of winning are known at the time of placement of the wager. Both players and operators are subject to the vagaries of luck in such games. Most game operators limit their liability exposure by imposing a sales limit on the bets received for each bet type, at the risk of losing the rejected bets to the underground operators. This raises a question-how should the game operator set the appropriate sales limit? We argue that the choice of the sales limit is intimately related to the ways players select numbers to bet on in the games. There are ample empirical evidences suggesting that players do not choose all numbers with equal probability, but have a tendency to bet on (small) numbers that are closely related to events around them (e. g., birth dates, addresses, etc.). To the best of our knowledge, this is the first paper to quantify this phenomenon and examine its relation to the classical Benford's law. We use this connection to develop a choice model, and propose a method to set the appropriate sales limit in these games. © Springer Science+Business Media, LLC 2009.
Thu, 01 Jan 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/440672009-01-01T00:00:00Z
- Anonymous monotonic social welfare functionshttps://scholarbank.nus.edu.sg/handle/10635/44049Title: Anonymous monotonic social welfare functions
Authors: Sethuraman, J.; Teo, C.-P.; Vohra, R.V.
Abstract: This paper presents two results about preference domain conditions that deepen our understanding of anonymous and monotonic Arrovian social welfare functions (ASWFs). We characterize the class of anonymous and monotonic ASWFs on domains without Condorcet triples. This extends and generalizes an earlier characterization (as Generalized Majority Rules) by Moulin (Axioms of Cooperative Decision Making, Cambridge University Press, New York, 1988) for single-peaked domains. We also describe a domain where anonymous and monotonic ASWFs exist only when there are an odd number of agents. This is a counter-example to a claim by Muller (Int. Econ. Rev. 23 (1982) 609), who asserted that the existence of 3-person anonymous and monotonic ASWFs guaranteed the existence of n-person anonymous and monotonic ASWFs for any n > 3. Both results build upon the integer programming approach to the study of ASWFs introduced in Sethuraman et al. (Math. Oper. Res. 28 (2003) 309). © 2005 Elsevier Inc. All rights reserved.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/440492006-01-01T00:00:00Z
- Models for minimax stochastic linear optimization problems with risk aversionhttps://scholarbank.nus.edu.sg/handle/10635/44018Title: Models for minimax stochastic linear optimization problems with risk aversion
Authors: Bertsimas, D.; Doan, X.V.; Natarajan, K.; Teo, C.-P.
Abstract: We propose a semidefinite optimization (SDP) model for the class of minimax two-stage stochastic linear optimization problems with risk aversion. The distribution of second-stage random variables belongs to a set of multivariate distributions with known first and second moments. For the minimax stochastic problem with random objective, we provide a tight SDP formulation. The problem with random right-hand side is NP-hard in general. In a special case, the problem can be solved in polynomial time. Explicit constructions of the worst-case distributions are provided. Applications in a productiontransportation problem and a single facility minimax distance problem are provided to demonstrate our approach. In our experiments, the performance of minimax solutions is close to that of data-driven solutions under the multivariate normal distribution and better under extremal distributions. The minimax solutions thus guarantee to hedge against these worst possible distributions and provide a natural distribution to stress test stochastic optimization problems under distributional ambiguity. Copyright © 2010 INFORMS.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/440182010-01-01T00:00:00Z
- World container port throughput follows lognormal distributionhttps://scholarbank.nus.edu.sg/handle/10635/43948Title: World container port throughput follows lognormal distribution
Authors: Ding, D.; Teo, C.-P.
Abstract: We show in this paper that the throughput data for the top 300 container ports reported each year by the various authorities follows a simple truncated lognormal distribution. This surprising phenomenon repeats itself every year from 1982 to 2006, despite many tumultuous changes in the container shipping world. The empirical data suggests that Gibrat's Law of proportionate growth indeed holds for the world container throughput data. Unfortunately, the classical stochastic growth model and other variants often used to explain the origin of this law appears to be too simplistic for the container terminal industry. We use instead the perspective that the container terminal throughput data are essentially an aggregate measure of the number of visitations as each container circulates on the world shipping network, and use this to propose a Markov chain based container circulation model to explain the origin of this phenomenon. Simulation results show that our network-based model is able to replicate the behavior of the empirical data to a reasonable degree of accuracy, and does not contradict the law of proportionate growth. More importantly, this model is able to replicate the relationship between the degree of connectivity of a port (i.e. number of linkages with other ports) and its association with the container throughput data, an empirical regularity which could not be explained using classical approaches. © 2010 Taylor & Francis.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/439482010-01-01T00:00:00Z
- Berth management in container terminal: The template design problemhttps://scholarbank.nus.edu.sg/handle/10635/44032Title: Berth management in container terminal: The template design problem
Authors: Moorthy, R.; Teo, C.-P.
Abstract: One of the foremost planning problems in container transshipment operation concerns the allocation of home berth (preferred berthing location) to a set of vessels scheduled to call at the terminal on a weekly basis. The home berth location is subsequently used as a key input to yard storage, personnel, and equipment deployment planning. For instance, the yard planners use the home berth template to plan for the storage locations of transshipment containers within the terminal. These decisions (yard storage plan) are in turn used as inputs in actual berthing operations, when the vessels call at the terminal. In this paper, we study the economical impact of the home berth template design problem on container terminal operations. In particular, we show that it involves a delicate trade-off between the service (waiting time for vessels) and cost (movement of containers between berth and yard) dimension of operations in the terminal. The problem is further exacerbated by the fact that the actual arrival time of the vessels often deviates from the scheduled arrival time, resulting in last-minute scrambling and change of plans in the terminal operations. Practitioners on the ground deal with this issue by building (capacity) buffers in the operational plan and to scramble for additional resources if needs be. We propose a framework to address the home berth design problem. We model this as a rectangle packing problem on a cylinder and use a sequence pair based simulated annealing algorithm to solve the problem. The sequence pair approach allows us to optimize over a large class of packing efficiently and decomposes the home berth problem with data uncertainty into two smaller subproblems that can be readily handled using techniques from stochastic project scheduling. To evaluate the quality of a template, we use a dynamic berth allocation package developed recently by Dai et al. (unpublished manuscript, 2004) to obtain various berthing statistics associated with the template. Extensive computational results show that the proposed model is able to construct efficient and robust template for transshipment hub operations.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/440322006-01-01T00:00:00Z
- Warehouse-retailer network design problemhttps://scholarbank.nus.edu.sg/handle/10635/44235Title: Warehouse-retailer network design problem
Authors: Teo, C.-P.; Shu, J.
Abstract: In this paper, we study the distribution network design problem integrating transportation and infinite horizon multiechelon inventory cost function. We consider the trade-off between inventory cost, direct shipment cost, and facility location cost in such a system. The problem is to determine how many warehouses to set up, where to locate them, how to serve the retailers using these warehouses, and to determine the optimal inventory policies for the warehouses and retailers. The objective is to minimize the total multiechelon inventory, transportation, and facility location costs. To the best of our knowledge, none of the papers in the area of distribution network design has explicitly addressed the issues of the 2-echelon inventory cost function arising from coordination of replenishment activities between the warehouses and the retailers. We structure this problem as a set-partitioning integer-programming model and solve it using column generation. The pricing subproblem that arises from the column generation algorithm gives rise to a new class of the submodular function minimization problem. We show that this pricing subproblem can be solved in O(n logn) time, where n is the number of retailers. Computational results show that the moderate size distribution network design problem can be solved efficiently via this approach.
Thu, 01 Jan 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/442352004-01-01T00:00:00Z
- Cyclic deadlock prediction and avoidance for zone-controlled AGV systemhttps://scholarbank.nus.edu.sg/handle/10635/43974Title: Cyclic deadlock prediction and avoidance for zone-controlled AGV system
Authors: Lochana Moorthy, R.; Hock-Guan, W.; Wing-Cheong, N.; Chung-Piaw, T.
Abstract: Automated guided vehicles (AGVs) are now becoming popular in automated materials handling systems, flexible manufacturing systems and even containers handling applications at seaports. Its performance affects the efficiency of the entire system. Deadlock formation is a serious problem as it stalls the AGVS. The objective of this paper is to develop an efficient AGV deadlock prediction and avoidance algorithm for container port operations. Deadlock in a broad sense is a situation in which at least a part of the system stalls. There are a lot of situations in which the system may stall and most of these situations can be avoided through the control and navigation system. This paper discusses the development of an efficient strategy for predicting and avoiding the deadlocks in a large scale AGVS A variety of deadlock-detecting algorithms are available, but these methods work mainly for manufacturing system where the network layout is simple and uses only a small number of AGVs. The AGVS under study has complex layout and involves close to 80 AGVs. The proposed solution is implemented using the Automod simulation software, and the performance of the technique is presented. Simulation shows that all the potential deadlock situations can be detected and avoided via this methodology. Also, the proposed strategy is computationally efficient and is able to provide the movement decision to the vehicles within the 1.5-s sampling time. © 2002 Elsevier Science B.V. All rights reserved.
Wed, 01 Jan 2003 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/439742003-01-01T00:00:00Z
- Approximation algorithms for general one-warehouse multi-retailer systemshttps://scholarbank.nus.edu.sg/handle/10635/44101Title: Approximation algorithms for general one-warehouse multi-retailer systems
Authors: Shen, Z.-J.M.; Shu, J.; Simchi-Levi, D.; Teo, C.-P.; Zhang, J.
Abstract: Logistical planning problems are complicated in practice because planners have to deal with the challenges of demand planning and supply replenishment, while taking into account the issues of (i) inventory perishability and storage charges, (ii) management of backlog and/or lost sales, and (iii) cost saving opportunities due to economies of scale in order replenishment and transportation. It is therefore not surprising that many logistical planning problems are computationally difficult, and finding a good solution to these problems necessitates the development of many ad hoc algorithmic procedures to address various features of the planning problems. In this article, we identify simple conditions and structural properties associated with these logistical planning problems in which the warehouse is managed as a cross-docking facility. Despite the nonlinear cost structures in the problems, we show that a solution that is within ε-optimality can be obtained by solving a related piece-wise linear concave cost multi-commodity network flow problem. An immediate consequence of this result is that certain classes of logistical planning problems can be approximated by a factor of (1 + ε) in polynomial time. This significantly improves upon the results found in literature for these classes of problems. We also show that the piece-wise linear concave cost network flow problem can be approximated to within a logarithmic factor via a large scale linear programming relaxation. We use polymatroidal constraints to capture the piece-wise concavity feature of the cost functions. This gives rise to a unified and generic LP-based approach for a large class of complicated logistical planning problems. © 2009 Wiley Periodicals, Inc.
Thu, 01 Jan 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/441012009-01-01T00:00:00Z
- A polynomial-time algorithm for the bistable roommates problemhttps://scholarbank.nus.edu.sg/handle/10635/44920Title: A polynomial-time algorithm for the bistable roommates problem
Authors: Sethuraman, J.; Teo, C.-P.
Abstract: In a recent paper, Weems introduced the bistable matching problem, and asked if a polynomial-time algorithm exists to decide the feasibility of the bistable roommates problem. We resolve this question in the affirmative using linear programming. In addition, we show that several (old and new) results for the bistable marriage and roommates problem become transparent using the polyhedral approach. This technique has been used recently by the authors to address classical stable matching problems.
Mon, 01 Jan 2001 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/449202001-01-01T00:00:00Z
- Tight bounds on expected order statisticshttps://scholarbank.nus.edu.sg/handle/10635/44205Title: Tight bounds on expected order statistics
Authors: Bertsimas, D.; Natarajan, K.; Teo, C.-P.
Abstract: In this article, we study the problem of finding tight bounds on the expected value of the kth-order statistic E [Xk:n] under first and second moment information on n real-valued random variables. Given means E[Xi] = μi and variances Var [Xi] = σi 2, we show that the tight upper bound on the expected value of the highest-order statistic E[Xn:n] can be computed with a bisection search algorithm. An extremal discrete distribution is identified that attains the bound, and two closed-form bounds are proposed. Under additional covariance information Cov[Xi, Xj] = Qij, we show that the tight upper bound on the expected value of the highest-order statistic can be computed with semidefinite optimization. We generalize these results to find bounds on the expected value of the kth-order statistic under mean and variance information. For k < n, this bound is shown to be tight under identical means and variances. All of our results are distribution-free with no explicit assumption of independence made. Particularly, using optimization methods, we develop tractable approaches to compute bounds on the expected value of order statistics. © 2006 Cambridge University Press.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/442052006-01-01T00:00:00Z
- Optimal logistics outsourcing: A geometric approachhttps://scholarbank.nus.edu.sg/handle/10635/44130Title: Optimal logistics outsourcing: A geometric approach
Authors: Mai, Y.; Teo, C.-P.; Miao, L.
Abstract: We introduce a geometric approach to study logistics outsourcing issues in a principal-agent setting. A method is proposed to determine the optimal outsourcing contract, using the notion of general cost sharing function. Compared with traditional methods, this simplifies the discussion on optimal contract design significantly. This restriction of the contract space does not lead to any deterioration in performance as it includes the optimal contract in the feasible contract options. The simplicity of this approach makes it more adaptable to analyzing logistics outsourcing contract options. We use a newsvendor problem to demonstrate the applicability of this approach. Some extension of this approach is proposed to complete a further insight of this approach. ©2010 IEEE.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/441302010-01-01T00:00:00Z
- Effective routing and scheduling in adversarial queueing networkshttps://scholarbank.nus.edu.sg/handle/10635/43964Title: Effective routing and scheduling in adversarial queueing networks
Authors: Sethuraman, J.; Teo, C.-P.
Wed, 01 Jan 2003 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/439642003-01-01T00:00:00Z
- Integer programming and arrovian social welfare functionshttps://scholarbank.nus.edu.sg/handle/10635/44003Title: Integer programming and arrovian social welfare functions
Authors: Sethuraman, J.; Piaw, T.C.; Vohra, R.V.
Abstract: We characterize the class of Arrovian Social Welfare Functions (ASWFs) as integer solutions to a collection of linear inequalities. Many of the classical possibility, impossibility, and characterization results can be derived in a simple and unified way from this integer program. Among the new results we derive is a characterization of preference domains that admit a nondictatorial, neutral ASWF. We also give a polyhedral characterization of all ASWFs on single-peaked domains.
Wed, 01 Jan 2003 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/440032003-01-01T00:00:00Z
- Effective zero-inventory-ordering policies for the single-warehouse multiretailer problem with piecewise linear cost structureshttps://scholarbank.nus.edu.sg/handle/10635/44030Title: Effective zero-inventory-ordering policies for the single-warehouse multiretailer problem with piecewise linear cost structures
Authors: Chan, L.M.A.; Muriel, A.; Shen, Z.-J.M.; Simchi-Levi, D.; Teo, C.-P.
Abstract: We analyze the problem faced by companies that rely on TL (Truckload) and LTL (Less than Truckload) carriers for the distribution of products across their supply chain. Our goal is to design simple inventory policies and transportation strategies to satisfy time-varying demands over a finite horizon, while minimizing systemwide cost by taking advantage of quantity discounts in the transportation cost structures. For this purpose, we study the cost effectiveness of restricting the inventory policies to the class of zero-inventory-ordering (ZIO) policies in a single-warehouse multiretailer scenario in which the warehouse serves as a cross-dock facility. In particular, we demonstrate that there exists a ZIO inventory policy whose total inventory and transportation cost is no more than 4/3 (5.6/4.6 if transportation costs are stationary) times the optimal cost. However, finding the best ZIO policy is an NP-hard problem as well. Thus, we propose two algorithms to find an effective ZIO policy: An exact algorithm whose running time is polynomial for any fixed number of retailers, and a linear-programming-based heuristic whose effectiveness is demonstrated in a series of computational experiments. Finally, we extend the worst-case results developed in this paper to systems in which the warehouse does hold inventory.
Tue, 01 Jan 2002 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/440302002-01-01T00:00:00Z
- LP based approach to optimal stable matchingshttps://scholarbank.nus.edu.sg/handle/10635/45043Title: LP based approach to optimal stable matchings
Authors: Teo, Chung-Piaw; Sethuraman, Jay
Abstract: We study the classical stable marriage and stable roommates problems using a polyhedral approach. We propose a new LP formulation for the stable roommates problem. This formulation is non-empty if and only if the underlying roommates problem has a stable matching. Furthermore, for certain special weight functions on the edges, we construct a 2-approximation algorithm for the optimal stable roommates problem. Our technique uses a crucial geometry of the fractional solutions in this formulation. For the stable marriage problem, we show that a related geometry allows us to express any fractional solution in the stable marriage polytope as convex combination of stable marriage solutions. This leads to a genuinely simple proof of the integrality of the stable marriage polytope. Based on these ideas, we devise a heuristic to solve the optimal stable roommates problem. The heuristic combines the power of rounding and cutting-plane methods. We present some computational results based on preliminary implementations of this heuristic.
Wed, 01 Jan 1997 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/450431997-01-01T00:00:00Z
- Impact on inventory costs with consolidation of distribution centershttps://scholarbank.nus.edu.sg/handle/10635/45038Title: Impact on inventory costs with consolidation of distribution centers
Authors: Teo, Chung Piaw; Ou, Jihong; Goh, Mark
Abstract: An attempt is made to study the impact of inventory costs when considering the consolidation strategy. Focus is on the common intuition that consolidation reduces total inventory costs due to the risk pooling effect. It is shown that when the demands are identically and independently distributed (i.i.d), consolidation is an optimal strategy for inventory costs minimization.
Fri, 01 Jan 1999 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/450381999-01-01T00:00:00Z
- Managing risk in a four-digit number gamehttps://scholarbank.nus.edu.sg/handle/10635/43928Title: Managing risk in a four-digit number game
Authors: Teo, C.-P.; Leong, S.M.
Abstract: The four-digit number game is a popular game of chance played in Southeast Asia. The players in this game choose a four-digit number and place their bets on it. In this paper, we study the design of a control mechanism for managing bets in this game. Our objective is to design a control mechanism to decide whether bets should be accepted or rejected. We propose a nonlinear optimization model for this problem and provide the mathematical justification for the control mechanism used by several operators in this region. We also suggest a simple improved control mechanism. Using data provided by a company in the region, we show that our control mechanism can accept more money per draw, while the risk exposure of the proposed mechanism can be considerably smaller than the current system.
Tue, 01 Jan 2002 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/439282002-01-01T00:00:00Z
- Beyond Risk: Ambiguity in Supply Chainshttps://scholarbank.nus.edu.sg/handle/10635/116833Title: Beyond Risk: Ambiguity in Supply Chains
Authors: Natarajan, K.; Sim, M.; Teo, C.-P.
Tue, 11 Oct 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1168332011-10-11T00:00:00Z
- The geometry of fractional stable matchings and its applicationshttps://scholarbank.nus.edu.sg/handle/10635/44889Title: The geometry of fractional stable matchings and its applications
Authors: Teo, C.-P.; Sethuraman, J.
Abstract: We study the classical stable marriage and stable roommates problems using a polyhedral approach. We propose a new LP formulation for the stable roommates problem, which has a feasible solution if and only if the underlying roommates problem has a stable matching. Furthermore, for certain special weight functions on the edges, we construct a 2-approximation algorithm for the optimal stable roommates problem. Our technique exploits features of the geometry of fractional solutions of this formulation. For the stable marriage problem, we show that a related geometry allows us to express any fractional solution in the stable marriage polytope as a convex combination of stable marriage solutions. This also leads to a genuinely simple proof of the integrality of the stable marriage polytope.
Thu, 01 Jan 1998 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/448891998-01-01T00:00:00Z
- Analysis of LP relaxations for multiway and multicut problemshttps://scholarbank.nus.edu.sg/handle/10635/44907Title: Analysis of LP relaxations for multiway and multicut problems
Authors: Bertsimas, D.; Teo, C.-P.; Vohra, R.
Abstract: We introduce in this paper an exact nonlinear formulation of the multiway cut problem. By simple linearizations of this formulation, we derive several well-known and new formulations for the problem. We further establish a connection between the multiway cut and the maximum-weighted independent set problem. This leads to the study of several instances of the multiway cut problem through the theory of perfect graphs. We also introduce a new randomized rounding argument to study the sharpness of these formulations. © 1999 John Wiley & Sons, Inc. Networks 34: 102-114, 1999.
Fri, 01 Jan 1999 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/449071999-01-01T00:00:00Z
- Multistage lot sizing problems via randomized roundinghttps://scholarbank.nus.edu.sg/handle/10635/44894Title: Multistage lot sizing problems via randomized rounding
Authors: Teo, C.-P.; Bertsimas, D.
Abstract: We study the classical multistage lot sizing problem that arises in distribution and inventory systems. A celebrated result in this area is the 94% and 98% approximation guarantee provided by power-of-two policies. In this paper, we propose a simple randomized rounding algorithm to establish these performance bounds. We use this new technique to extend several results for the capacitated lot sizing problems to the case with submodular ordering cost. For the joint replenishment problem under a fixed base period model, we construct a 95.8% approximation algorithm to the (possibly dynamic) optimal lot sizing policy. The policies constructed are stationary but not necessarily of the power-of-two type. This shows that for the fixed based planning model, the class of stationary policies is within 95.8% of the optimum, improving on the previously best known 94% approximation guarantee.
Mon, 01 Jan 2001 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/448942001-01-01T00:00:00Z
- A constant-factor approximation algorithm for packet routing and balancing local vs. global criteriahttps://scholarbank.nus.edu.sg/handle/10635/44984Title: A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria
Authors: Srinivasan, A.; Chung-Piaw, T.
Abstract: We present the first constant-factor approximation algorithm for a fundamental problem: the store-and-forward packet routing problem on arbitrary networks. Furthermore, the queue sizes required at the edges are bounded by an absolute constant. Thus, this algorithm balances a global criterion (routing time) with a local criterion (maximum queue size) and shows how to get simultaneous good bounds for both. For this particular problem, approximating the routing time well, even without considering the queue sizes, was open. We then consider a class of such local vs. global problems in the context of covering integer programs and show how to improve the local criterion by a logarithmic factor by losing a constant factor in the global criterion. © 2001 Society for Industrial and Applied Mathematics.
Sat, 01 Jan 2000 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/449842000-01-01T00:00:00Z
- Gale-Shapley stable marriage problem revisited: Strategic issues and applicationshttps://scholarbank.nus.edu.sg/handle/10635/44970Title: Gale-Shapley stable marriage problem revisited: Strategic issues and applications
Authors: Teo, C.-P.; Sethuraman, J.; Tan, W.-P.
Abstract: We study strategic issues in the Gale-Shapley stable marriage model. In the first part of the paper, we derive the optimal cheating strategy and show that it is not always possible for a woman to recover her women-optimal stable partner from the men-optimal stable matching mechanism when she can only cheat by permuting her preferences. In fact, we show, using simulation, that the chances that a woman can benefit from cheating are slim. In the second part of the paper, we consider a two-sided matching market found in Singapore. We study the matching mechanism used by the Ministry of Education (MOE) in the placement of primary six students in secondary schools, and discuss why the current method has limited success in accommodating the preferences of the students, and the specific needs of the schools (in terms of the "mix" of admitted students). Using insights from the first part of the paper, we show that stable matching mechanisms are more appropriate in this matching market and explain why the strategic behavior of the students need not be a major concern.
Mon, 01 Jan 2001 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/449702001-01-01T00:00:00Z
- The parsimonious property of cut covering problems and its applicationshttps://scholarbank.nus.edu.sg/handle/10635/44971Title: The parsimonious property of cut covering problems and its applications
Authors: Bertsimas, D.; Teo, C.
Abstract: We consider the analysis of linear programming relaxations of a large class of combinatorial problems that can be formulated as problems of covering cuts, including the Steiner tree, the traveling salesman, the vehicle routing, the matching, the T-join and the survivable network design problem, to name a few. We prove that all of the problems in the class satisfy a nice structural property, the parsimonious property, generalizing earlier work by Goemans and Bertsimas (1993). We utilize the parsimonious property to establish worst-case bounds between the gap of the IP and LP values for the class of 0-1 proper functions, leading to a new 2-approximation algorithm for this class of problems. We also extend the parsimonious property to a class of cut-covering problems that model certain instances of the edge-disjoint path problem. © 1997 Elsevier Science B.V.
Wed, 01 Jan 1997 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/449711997-01-01T00:00:00Z
- Greedy, randomized and approximate dynamic programming algorithms for facility location problemshttps://scholarbank.nus.edu.sg/handle/10635/140255Title: Greedy, randomized and approximate dynamic programming algorithms for facility location problems
Authors: Bertsimas, Dimitris; Teo, Chung-Piaw; Vohra, Rakesh
Tue, 01 Dec 1998 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1402551998-12-01T00:00:00Z
- On a cutting plane heuristic for the stable roommates problem and its applicationshttps://scholarbank.nus.edu.sg/handle/10635/140173Title: On a cutting plane heuristic for the stable roommates problem and its applications
Authors: Teo, Chung-Piaw; Sethuraman, Jay
Wed, 01 Apr 1998 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1401731998-04-01T00:00:00Z