Open Access. Powered by Scholars. Published by Universities.®

Operations Research, Systems Engineering and Industrial Engineering Commons

Open Access. Powered by Scholars. Published by Universities.®

Articles 1 - 30 of 30

Full-Text Articles in Operations Research, Systems Engineering and Industrial Engineering

Robust Distributed Scheduling Via Time Period Aggregation, Shih-Fen Cheng, John Tajan, Hoong Chuin Lau Dec 2015

Robust Distributed Scheduling Via Time Period Aggregation, Shih-Fen Cheng, John Tajan, Hoong Chuin Lau

Shih-Fen Cheng

In this paper, we evaluate whether the robustness of a market mechanism that allocates complementary resources could be improved through the aggregation of time periods in which resources are consumed. In particular, we study a multi-round combinatorial auction that is built on a general equilibrium framework. We adopt the general equilibrium framework and the particular combinatorial auction design from the literature, and we investigate the benefits and the limitation of time-period aggregation when demand-side uncertainties are introduced. By using simulation experiments on a real-life resource allocation problem from a container port, we show that, under stochastic conditions, the performance variation …


Robust Distributed Scheduling Via Time Period Aggregation, Shih-Fen Cheng, John Tajan, Hoong Chuin Lau Dec 2015

Robust Distributed Scheduling Via Time Period Aggregation, Shih-Fen Cheng, John Tajan, Hoong Chuin Lau

Shih-Fen Cheng

In this paper, we evaluate whether the robustness of a market mechanism that allocates complementary resources could be improved through the aggregation of time periods in which resources are consumed. In particular, we study a multi-round combinatorial auction that is built on a general equilibrium framework. We adopt the general equilibrium framework and the particular combinatorial auction design from the literature, and we investigate the benefits and the limitation of time-period aggregation when demand-side uncertainties are introduced. By using simulation experiments on a real-life resource allocation problem from a container port, we show that, under stochastic conditions, the performance variation …


Robust Distributed Scheduling Via Time Period Aggregation, Shih-Fen Cheng, John Tajan, Hoong Chuin Lau Dec 2015

Robust Distributed Scheduling Via Time Period Aggregation, Shih-Fen Cheng, John Tajan, Hoong Chuin Lau

Shih-Fen CHENG

In this paper, we evaluate whether the robustness of a market mechanism that allocates complementary resources could be improved through the aggregation of time periods in which resources are consumed. In particular, we study a multi-round combinatorial auction that is built on a general equilibrium framework. We adopt the general equilibrium framework and the particular combinatorial auction design from the literature, and we investigate the benefits and the limitation of time-period aggregation when demand-side uncertainties are introduced. By using simulation experiments on a real-life resource allocation problem from a container port, we show that, under stochastic conditions, the performance variation …


Direct Neighbor Search, Jilian Zhang, Kyriakos Mouratidis, Hwee Hwa Pang Jun 2014

Direct Neighbor Search, Jilian Zhang, Kyriakos Mouratidis, Hwee Hwa Pang

Kyriakos MOURATIDIS

In this paper we study a novel query type, called direct neighbor query. Two objects in a dataset are direct neighbors (DNs) if a window selection may exclusively retrieve these two objects. Given a source object, a DN search computes all of its direct neighbors in the dataset. The DNs define a new type of affinity that differs from existing formulations (e.g., nearest neighbors, nearest surrounders, reverse nearest neighbors, etc.) and finds application in domains where user interests are expressed in the form of windows, i.e., multi-attribute range selections. Drawing on key properties of the DN relationship, we develop an …


Budgeted Personalized Incentive Approaches For Smoothing Congestion In Resource Networks, Pradeep Varakantham, Na Fu, William Yeoh, Shih-Fen Cheng, Hoong Chuin Lau Jun 2014

Budgeted Personalized Incentive Approaches For Smoothing Congestion In Resource Networks, Pradeep Varakantham, Na Fu, William Yeoh, Shih-Fen Cheng, Hoong Chuin Lau

Shih-Fen CHENG

Congestion occurs when there is competition for resources by sel sh agents. In this paper, we are concerned with smoothing out congestion in a network of resources by using personalized well-timed in- centives that are subject to budget constraints. To that end, we provide: (i) a mathematical formulation that computes equilibrium for the re- source sharing congestion game with incentives and budget constraints; (ii) an integrated approach that scales to larger problems by exploiting the factored network structure and approximating the attained equilib- rium; (iii) an iterative best response algorithm for solving the uncon- strained version (no budget) of the …


Multi-Agent Orienteering Problem With Time-Dependent Capacity Constraints, Cen Chen, Shih-Fen Cheng, Hoong Chuin Lau Jun 2014

Multi-Agent Orienteering Problem With Time-Dependent Capacity Constraints, Cen Chen, Shih-Fen Cheng, Hoong Chuin Lau

Shih-Fen CHENG

The Orienteering Problem (OP), as originally defined by Tsiligirides, is the problem of cross-countr sport in which participants get rewards from visiting a predefined set of checkpoints. As Orienteering Problem can be used to describe a wide variety of real-world problems like route planning for facility inspection, patrolling of strategic location, and reward-weighted traveling salesman problem, it has attracted continuous interests from researchers and a large number of variants and corresponding algorithms for solving them have been introduced.


A Multi-Objective Memetic Algorithm For Vehicle Resource Allocation In Sustainable Transportation Planning, Hoong Chuin Lau, Lucas Agussurja, Shih-Fen Cheng, Pang Jin Tan Jun 2014

A Multi-Objective Memetic Algorithm For Vehicle Resource Allocation In Sustainable Transportation Planning, Hoong Chuin Lau, Lucas Agussurja, Shih-Fen Cheng, Pang Jin Tan

Shih-Fen CHENG

Sustainable supply chain management has been an increasingly important topic of research in recent years. At the strategic level, there are computational models which study supply and distribution networks with environmental considerations. At the operational level, there are, for example, routing and scheduling models which are constrained by carbon emissions. Our paper explores work in tactical planning with regards to vehicle resource allocation from distribution centers to customer locations in a multi-echelon logistics network. We formulate the bi-objective optimization problem exactly and design a memetic algorithm to efficiently derive an approximate Pareto front. We illustrate the applicability of our approach …


An Agent-Based Simulation Approach To Experience Management In Theme Parks, Shih-Fen Cheng, Larry Junjie Lin, Jiali Du, Hoong Chuin Lau, Pradeep Reddy Varakantham Jun 2014

An Agent-Based Simulation Approach To Experience Management In Theme Parks, Shih-Fen Cheng, Larry Junjie Lin, Jiali Du, Hoong Chuin Lau, Pradeep Reddy Varakantham

Shih-Fen CHENG

In this paper, we illustrate how massive agent-based simulation can be used to investigate an exciting new application domain of experience management in theme parks, which covers topics like congestion control, incentive design, and revenue management. Since all visitors are heterogeneous and self-interested, we argue that a high-quality agent-based simulation is necessary for studying various problems related to experience management. As in most agent-base simulations, a sound understanding of micro-level behaviors is essential to construct high-quality models. To achieve this, we designed and conducted a first-of-its-kind real-world experiment that helps us understand how typical visitors behave in a theme-park environment. …


Interacting Knapsack Problem In Designing Resource Bundles, Truong Huy D. Nguyen, Pradeep Reddy Varakantham, Hoong Chuin Lau, Shih-Fen Cheng Jun 2014

Interacting Knapsack Problem In Designing Resource Bundles, Truong Huy D. Nguyen, Pradeep Reddy Varakantham, Hoong Chuin Lau, Shih-Fen Cheng

Shih-Fen CHENG

In many real-life businesses, the service provider/seller keeps a log of the visitors’ behavior as a way to assess the efficiency of the current business/operation model and find room for improvement. For example, by tracking when visitors entering attractions in a theme park, theme park owners can detect when and where congestion may occur, thus having contingency plans to reroute the visitors accordingly. Similarly, a Cable TV service provider can track channel switching events at each household to identify uninteresting channels. Subsequently, the repertoire of channels up for subscription can evolve over time to better serve the entertainment demand of …


Uncertain Congestion Games With Assorted Human Agent Populations, Asrar Ahmed, Pradeep Reddy Varakantham, Shih-Fen Cheng May 2013

Uncertain Congestion Games With Assorted Human Agent Populations, Asrar Ahmed, Pradeep Reddy Varakantham, Shih-Fen Cheng

Shih-Fen CHENG

Congestion games model a wide variety of real-world resource congestion problems, such as selfish network routing, traffic route guidance in congested areas, taxi fleet optimization and crowd movement in busy areas. However, existing research in congestion games assumes: (a) deterministic movement of agents between resources; and (b) perfect rationality (i.e. maximizing their own expected value) of all agents. Such assumptions are not reasonable in dynamic domains where decision support has to be provided to humans. For instance, in optimizing the performance of a taxi fleet serving a city, movement of taxis can be involuntary or nondeterministic (decided by the specific …


Decentralized Decision Support For An Agent Population In Dynamic And Uncertain Domains, Pradeep Reddy Varakantham, Shih-Fen Cheng, Thi Duong Nguyen May 2013

Decentralized Decision Support For An Agent Population In Dynamic And Uncertain Domains, Pradeep Reddy Varakantham, Shih-Fen Cheng, Thi Duong Nguyen

Shih-Fen CHENG

This research is motivated by problems in urban transportation and labor mobility, where the agent flow is dynamic, non-deterministic and on a large scale. In such domains, even though the individual agents do not have an identity of their own and do not explicitly impact other agents, they have implicit interactions with other agents. While there has been much research in handling such implicit effects, it has primarily assumed controlled movements of agents in static environments. We address the issue of decision support for individual agents having involuntary movements in dynamic environments . For instance, in a taxi fleet serving …


Lagrangian Relaxation For Large-Scale Multi-Agent Planning, Geoff Gordon, Pradeep Varakantham, William Yeoh, Hoong Chuin Lau, Shih-Fen Cheng May 2013

Lagrangian Relaxation For Large-Scale Multi-Agent Planning, Geoff Gordon, Pradeep Varakantham, William Yeoh, Hoong Chuin Lau, Shih-Fen Cheng

Shih-Fen Cheng

Multi-agent planning is a well-studied problem with various applications including disaster rescue, urban transportation and logistics, both for autonomous agents and for decision support to humans. Due to computational constraints, existing research typically focuses on one of two scenarios: unstructured domains with many agents where we are content with heuristic solutions, or domains with small numbers of agents or special structure where we can provide provably near-optimal solutions. By contrast, in this paper, we focus on providing provably near-optimal solutions for domains with large numbers of agents, by exploiting a common domain-general property: if individual agents each have limited influence …


Lagrangian Relaxation For Large-Scale Multi-Agent Planning, Geoff Gordon, Pradeep Reddy Varakantham, William Yeoh, Ajay Srinivasan, Hoong Chuin Lau, Shih-Fen Cheng May 2013

Lagrangian Relaxation For Large-Scale Multi-Agent Planning, Geoff Gordon, Pradeep Reddy Varakantham, William Yeoh, Ajay Srinivasan, Hoong Chuin Lau, Shih-Fen Cheng

Shih-Fen CHENG

Multi-agent planning is a well-studied problem with applications in various areas. Due to computational constraints, existing research typically focuses either on unstructured domains with many agents, where we are content with heuristic solutions, or domains with small numbers of agents or special structure, where we can find provably near-optimal solutions. In contrast, here we focus on provably near-optimal solutions in domains with many agents, by exploiting influence limits. To that end, we make two key contributions: (a) an algorithm, based on Lagrangian relaxation and randomized rounding, for solving multi-agent planning problems represented as large mixed-integer programs; (b) a proof of …


Notes On Equilibria In Symmetric Games, Shih-Fen Cheng, Daniel M. Reeves, Yevgeniy Vorobeychik, Michael P. Wellman May 2013

Notes On Equilibria In Symmetric Games, Shih-Fen Cheng, Daniel M. Reeves, Yevgeniy Vorobeychik, Michael P. Wellman

Shih-Fen CHENG

In a symmetric game, every player is identical with respect to the game rules. We show that a symmetric 2strategy game must have a pure-strategy Nash equilibrium. We also discuss Nash’s original paper and its generalized notion of symmetry in games. As a special case of Nash’s theorem, any finite symmetric game has a symmetric Nash equilibrium. Furthermore, symmetric infinite games with compact, convex strategy spaces and continuous, quasiconcave utility functions have symmetric pure-strategy Nash equilibria. Finally, we discuss how to exploit symmetry for more efficient methods of finding Nash equilibria.


Distributing Complementary Resources Across Multiple Periods With Stochastic Demand, Shih-Fen Cheng, John Tajan, Hoong Chuin Lau May 2013

Distributing Complementary Resources Across Multiple Periods With Stochastic Demand, Shih-Fen Cheng, John Tajan, Hoong Chuin Lau

Shih-Fen CHENG

In this paper, we evaluate whether the robustness of a market mechanism that allocates complementary resources could be improved through the aggregation of time periods in which resources are consumed. In particular, we study a multi-round combinatorial auction that is built on a general equilibrium framework. We adopt the general equilibrium framework and the particular combinatorial auction design from the literature, and we investigate the benefits and the limitation of time-period aggregation when demand-side uncertainties are introduced. By using simulation experiments, we show that under stochastic conditions the performance variation of the process decreases as the time frame length (time …


Designing The Market Game For A Commodity Trading Simulation, Shih-Fen Cheng May 2013

Designing The Market Game For A Commodity Trading Simulation, Shih-Fen Cheng

Shih-Fen CHENG

In this paper, we propose to design a market game that (a) can be used in modeling and studying commodity trading scenarios, and (b) can be used in capturing human traders' behaviors. Specifically, we demonstrate the usefulness of this commodity trading game in a single-commodity futures trading scenario. A pilot experiment was run with a mixture of human traders and an autonomous agent that emulates the aggregatedmarket condition, with the assumption that this autonomous agent would hint each of its action through a public announcement. We show that the information collected from this simulation can be used to extract the …


Decision Support For Assorted Populations In Uncertain And Congested Environments, Pradeep Reddy Varakantham, Asrar Ahmed, Shih-Fen Cheng May 2013

Decision Support For Assorted Populations In Uncertain And Congested Environments, Pradeep Reddy Varakantham, Asrar Ahmed, Shih-Fen Cheng

Shih-Fen Cheng

This research is motivated by large scale problems in urban transportation and labor mobility where there is congestion for resources and uncertainty in movement. In such domains, even though the individual agents do not have an identity of their own and do not explicitly interact with other agents, they effect other agents. While there has been much research in handling such implicit effects, it has primarily assumed deterministic movements of agents. We address the issue of decision support for individual agents that are identical and have involuntary movements in dynamic environments. For instance, in a taxi fleet serving a city, …


An Analysis Of Extreme Price Shocks And Illiquidity Among Trend Followers, Bernard Lee, Shih-Fen Cheng, Annie Koh May 2013

An Analysis Of Extreme Price Shocks And Illiquidity Among Trend Followers, Bernard Lee, Shih-Fen Cheng, Annie Koh

Shih-Fen CHENG

We construct an agent-based model to study the interplay between extreme price shocks and illiquidity in the presence of systematic traders known as trend followers. The agent-based approach is particularly attractive in modeling commodity markets because the approach allows for the explicit modeling of production, capacities, and storage constraints. Our study begins by using the price stream from a market simulation involving human participants and studies the behavior of various trend-following strategies, assuming initially that their participation will not impact the market. We notice an incremental deterioration in strategy performance as and when strategies deviate further and further from the …


A Mechanism For Organizing Last-Mile Service Using Non-Dedicated Fleet, Shih-Fen Cheng, Duc Thien Nguyen, Hoong Chuin Lau May 2013

A Mechanism For Organizing Last-Mile Service Using Non-Dedicated Fleet, Shih-Fen Cheng, Duc Thien Nguyen, Hoong Chuin Lau

Shih-Fen CHENG

Unprecedented pace of urbanization and rising income levels have fueled the growth of car ownership in almost all newly formed megacities. Such growth has congested the limited road space and significantly affected the quality of life in these megacities. Convincing residents to give up their cars and use public transport is the most effective way in reducing congestion; however, even with sufficient public transport capacity, the lack of last-mile (from the transport hub to the destination) travel services is the major deterrent for the adoption of public transport. Due to the dynamic nature of such travel demands, fixed-size fleets will …


An Agent-Based Commodity Trading Simulation, Shih-Fen Cheng, Yee Pin Lim May 2013

An Agent-Based Commodity Trading Simulation, Shih-Fen Cheng, Yee Pin Lim

Shih-Fen CHENG

In this paper, an event-centric commodity trading simulation powered by the multiagent framework is presented. The purpose of this simulation platform is for training novice traders. The simulation is progressed by announcing news events that affect various aspects of the commodity supply chain. Upon receiving these events, market agents that play the roles of producers, consumers, and speculators would adjust their views on the market and act accordingly. Their actions would be based on their roles and also their private information, and collectively they shape the market dynamics. This simulation has been effectively deployed for several training sessions. We will …


Iterated Weaker-Than-Weak Dominance, Shih-Fen Cheng, Michael P. Wellman May 2013

Iterated Weaker-Than-Weak Dominance, Shih-Fen Cheng, Michael P. Wellman

Shih-Fen CHENG

We introduce a weakening of standard gametheoretic δ-dominance conditions, called dominance, which enables more aggressive pruning of candidate strategies at the cost of solution accuracy. Equilibria of a game obtained by eliminating a δ-dominated strategy are guaranteed to be approximate equilibria of the original game, with degree of approximation bounded by the dominance parameter. We can apply elimination of δ-dominated strategies iteratively, but the for which a strategy may be eliminated depends on prior eliminations. We discuss implications of this order independence, and propose greedy heuristics for determining a sequence of eliminations to reduce the game as far as possible …


Multi-Period Combinatorial Auction Mechanism For Distributed Resource Allocation And Scheduling, Hoong Chuin Lau, Shih-Fen Cheng, Thin Yin Leong, Jong Han Park, Zhengyi Zhao May 2013

Multi-Period Combinatorial Auction Mechanism For Distributed Resource Allocation And Scheduling, Hoong Chuin Lau, Shih-Fen Cheng, Thin Yin Leong, Jong Han Park, Zhengyi Zhao

Shih-Fen CHENG

We consider the problem of resource allocation and scheduling where information and decisions are decentralized, and our goal is to propose a market mechanism that allows resources from a central resource pool to be allocated to distributed decision makers (agents) that seek to optimize their respective scheduling goals. We propose a generic combinatorial auction mechanism that allows agents to competitively bid for the resources needed in a multi-period setting, regardless of the respective scheduling problem faced by the agent, and show how agents can design optimal bidding strategies to respond to price adjustment strategies from the auctioneer. We apply our …


Heuristic Algorithms For Balanced Multi-Way Number Partitioning, Jilian Zhang, Kyriakos Mouratidis, Hwee Hwa Pang Jul 2012

Heuristic Algorithms For Balanced Multi-Way Number Partitioning, Jilian Zhang, Kyriakos Mouratidis, Hwee Hwa Pang

Kyriakos MOURATIDIS

Balanced multi-way number partitioning (BMNP) seeks to split a collection of numbers into subsets with (roughly) the same cardinality and subset sum. The problem is NP-hard, and there are several exact and approximate algorithms for it. However, existing exact algorithms solve only the simpler, balanced two-way number partitioning variant, whereas the most effective approximate algorithm, BLDM, may produce widely varying subset sums. In this paper, we introduce the LRM algorithm that lowers the expected spread in subset sums to one third that of BLDM for uniformly distributed numbers and odd subset cardinalities. We also propose Meld, a novel strategy for …


Incremental Dcop Search Algorithms For Solving Dynamic Dcop Problems, William Yeoh, Pradeep Varakantham, Xiaoxun Sun, Sven Koenig Mar 2012

Incremental Dcop Search Algorithms For Solving Dynamic Dcop Problems, William Yeoh, Pradeep Varakantham, Xiaoxun Sun, Sven Koenig

Dr Xiaoxun Sun

Distributed constraint optimization problems (DCOPs) are well-suited for modeling multi-agent coordination problems. However, most research has focused on developing algorithms for solving static DCOPs. In this paper, we model dynamic DCOPs as sequences of (static) DCOPs with changes from one DCOP to the next one in the sequence. We introduce the ReuseBounds procedure, which can be used by any-space ADOPT and any-space BnB-ADOPT to find cost-minimal solutions for all DCOPs in the sequence faster than by solving each DCOP individually. This procedure allows those agents that are guaranteed to remain unaffected by a change to reuse their lower and upper …


Adaptive Algorithms For Coverage Control And Space Partitioning In Mobile Robotic Networks, Jerome Le Ny, George J. Pappas Mar 2012

Adaptive Algorithms For Coverage Control And Space Partitioning In Mobile Robotic Networks, Jerome Le Ny, George J. Pappas

George J. Pappas

We consider deployment problems where a mobile robotic network must optimize its configuration in a distributed way in order to minimize a steady-state cost function that depends on the spatial distribution of certain probabilistic events of interest. Three classes of problems are discussed in detail: coverage control problems, spatial partitioning problems, and dynamic vehicle routing problems. Moreover, we assume that the event distribution is a priori unknown, and can only be progressively inferred from the observation of the location of the actual event occurrences. For each problem we present distributed stochastic gradient algorithms that optimize the performance objective. The stochastic …


Adaptive Algorithms For Coverage Control And Space Partitioning In Mobile Robotic Networks, Jerome Le Ny, George J. Pappas Mar 2012

Adaptive Algorithms For Coverage Control And Space Partitioning In Mobile Robotic Networks, Jerome Le Ny, George J. Pappas

George J. Pappas

We consider deployment problems where a mobile robotic network must optimize its configuration in a distributed way in order to minimize a steady-state cost function that depends on the spatial distribution of certain probabilistic events of interest. Three classes of problems are discussed in detail: coverage control problems, spatial partitioning problems, and dynamic vehicle routing problems. Moreover, we assume that the event distribution is a priori unknown, and can only be progressively inferred from the observation of the location of the actual event occurrences. For each problem we present distributed stochastic gradient algorithms that optimize the performance objective. The stochastic …


Adaptive Algorithms For Coverage Control And Space Partitioning In Mobile Robotic Networks, Jerome Le Ny, George J. Pappas Mar 2012

Adaptive Algorithms For Coverage Control And Space Partitioning In Mobile Robotic Networks, Jerome Le Ny, George J. Pappas

George J. Pappas

We consider deployment problems where a mobile robotic network must optimize its configuration in a distributed way in order to minimize a steady-state cost function that depends on the spatial distribution of certain probabilistic events of interest. Three classes of problems are discussed in detail: coverage control problems, spatial partitioning problems, and dynamic vehicle routing problems. Moreover, we assume that the event distribution is a priori unknown, and can only be progressively inferred from the observation of the location of the actual event occurrences. For each problem we present distributed stochastic gradient algorithms that optimize the performance objective. The stochastic …


Selective Recursive Kernel Learning For Online Identification Of Nonlinear Systems With Narx Form, Yi Liu, Haiqing Wang, Jiang Yu, Ping Li Feb 2010

Selective Recursive Kernel Learning For Online Identification Of Nonlinear Systems With Narx Form, Yi Liu, Haiqing Wang, Jiang Yu, Ping Li

Dr. Yi Liu

Online identification of nonlinear systems is still an important while difficult task in practice. A general and simple online identification method, namely Selective Recursive Kernel Learning (SRKL), is proposed for multi-input–multi-output (MIMO) systems with the nonlinear autoregressive with exogenous input form. A two-stage RKL online identification framework is first formulated, where the information contained by a sample (i.e., the new arriving or old useless one) can be introduced into and/or deleted from the model, recursively. Then, a sparsification strategy to restrict the model complexity is developed to guarantee all the output channels of the MIMO model accurate simultaneously. Specially, a …


Modeling Of Fermentation Processes Using Online Kernel Learning Algorithm, Yi Liu Jul 2008

Modeling Of Fermentation Processes Using Online Kernel Learning Algorithm, Yi Liu

Dr. Yi Liu

No abstract provided.


Adaptive Control Of A Class Of Nonlinear Discrete-Time Systems With Online Kernel Learning, Yi Liu Jul 2008

Adaptive Control Of A Class Of Nonlinear Discrete-Time Systems With Online Kernel Learning, Yi Liu

Dr. Yi Liu

No abstract provided.