Seminars for Spring 2012

05/03/12 RUTCOR Colloquium - 2:30PM

Speaker: Gyorgy Turan
Affiliation: University of Illinois at Chicago
Title: On the combinatorics and complexity of Horn formulas

Abstract: We discuss two problems motivated by the general problems of minimizing and updating propositional Horn knowledge bases.

Given an undirected graph G, a hydra for G is a directed hypergraph with hyperedges of the form a,b --> c, where (a,b) is an edge of G, such that forward chaining started at any edge of G marks every vertex. The hydra number of a graph is the minimal number of hyperedges in a hydra for G. Determining the hydra number is a special case of the minimization problem for Horn formulas. We give various bounds for the hydra number.

A set of truth assignments can be represented by a Horn formula iff the set is closed under componentwise `and'. The closure of an arbitrary set under intersection gives the Horn envelope, or Horn least upper bound (LUB) of an arbitrary Boolean function. In particular, the Horn envelope of a Horn function and a single additional truth assignment comes up in the context of belief revision for Horn formulas. We show that the Horn envelope may be exponentially larger than the original formula.

We will also mention several open problems related to these topics. Joint work with Kira Adaricheva, Robert Sloan, Despina Stasi and Balazs Szorenyi.

05/03/12  Special MSIS/RUTCOR Joint Seminar - 1:00PM

Speaker: Yuri G. Levin
Queen's School of Business,Kingston, Ontario,Canada
Location: 1 Washington Park #1027, Newark Campus
Title: Quantity Premiums and Discounts in Dynamic Pricing

Abstract: We consider a dynamic pricing problem for a monopolistic company selling a perishable product when customer demand is uncertain and occurs in batches which must be fulfilled as a whole. The seller can price discriminate between the batches of different size by setting different unit prices. The problem is modeled as a stochastic optimal control problem to find an inventory-contingent dynamic pricing policy to maximize the expected total revenues. We find the optimal pricing policy and prove several monotonicity results. First, we establish stochastic order conditions on the unit willingness-to-pay distributions that determine when quantity discounts or premiums take place as a batch purchase is broken up into a rapid sequence of smaller purchases. Second, we give a sufficient condition for prices to be monotonically decreasing in inventory when the maximum batch size is two. Third, we establish sufficient stochastic order and value function convexity conditions for the perceived quantity discounts and premiums which result from comparing unit prices for different batch sizes under a particular inventory level. Numerical experiments reveal further details of interactions between stochastic order and convexity conditions, and demonstrate that a company can generate significant additional revenues though explicit dynamic non-linear pricing.

Yuri Levin is a Professor of Management Science and Operations Management and Distinguished Faculty Professor of Operations Management at Queen's School of Business. He teaches business decision modeling, operations management and pricing courses in MBA, MS/PhD., B. Commerce, and Executive Education programs. He has been nominated for the MBA Instructor of the Year Award for the past 4 years. He holds a Ph.D. in Operations Research from Rutgers University in US where he taught in different MBA programs for 3 years before joining Queen’s in 2002. He has developed innovative approaches and published widely in the general area of revenue management and dynamic pricing. Yuri was the 2010 recipient of Queen’s School of Business Award for Research Achievement, 2003 New Researcher Achievement Award and a co-winner of 2009 INFORMS COIN-OR Cup for applications of COIN-OR technologies in development of novel techniques for cargo capacity management and dynamic pricing.

04/26/12 RUTCOR BrownBag - 12:00 Noon

Speaker: Martin Milanic
Affiliation: University of Primorska, Koper, Slovenia
Title: Hereditary efficiently dominatable graphs

Abstract: An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the graph's vertex set. It is NP-complete to determine whether a given graph contains an efficient dominating set. We study the class of hereditary efficiently dominatable graphs, that is, graphs every induced subgraph of which contains an efficient dominating set. Based on a decomposition theorem for (bull, fork, C_4)-free graphs, we derive the forbidden induced subgraph characterization of hereditary efficiently dominatable graphs. We also discuss some algorithmic consequences of the obtained characterization and decomposition theorems. In particular, we present a robust polynomial time algorithm for finding an efficient dominating set in a hereditary efficiently dominatable graph. Finally, we give a polynomial time algorithm for finding the maximum number of vertices that can be efficiently dominated, if the given graph belongs to the class of (claw,net)-free graphs, a class of graphs properly containing the class of hereditary efficiently dominatable graphs. This result is obtained by reducing the problem to the maximum weight independent set problem in claw-free graphs.

04/19/12 RUTCOR Seminar - 1:30 PM

Speaker: Jon Lee
Affiliation: The University of Michigan
Title: Submodular-function Maximization

ABSTRACT: Submodular-function maximization is a central unifying model in combinatorial optimization. Applications range from practical problems such as reconfiguring an environmental monitoring network, to more stylized problems such as the graph max-cut problem. I will describe some of the motivating applications, survey some different methodologies for maximizing a submodular function subject to side constraints, and describe computational results on environmental-monitoring problem instances for some of the more practical algorithms. Interestingly, while some of the algorithms are aimed at practical computation via an Operations Research / Mathematical Optimization approach, and others are driven by the Computer Science theory of approximation algorithms, there is significant common ground.

03/28/12  Special MSIS/RUTCOR Joint Seminar - 1:00PM

Speaker: Nesim K. Erkip
Affiliation: Bilkent University, Turkey
Location: 1 Washington Park #1027, Newark Campus
             Videoconference at Levin 130
Title: Spare Part Management: A Life-Cycle Approach

Abstract: The spare part problem we consider is for a planning environment where a component used in products such as automobiles and other expensive equipment. The purpose of the research is to establish the foundation for analyzing the inventory problem of the component that includes use of the component in the assembly of the product, and as a spare part until its life-cycle is complete.
There are two parts of the talk: In the first part a summary of challenges in the life-cycle analyses of spare parts will be presented. Problems that are off academic interest will be outlined. In the second part of the talk, an approach for a version of the problem will be presented. Specifically: (1) We show the effect of the described situation in item 2. above on the OEM, which is the spare part distributor, as well; (2) We offer two different ways of compensating the supplier that will make the spare part distributor better off with respect to the original situation; (3) We finally formalize the efforts of the spare part distributor by designing a reasonable contract. We give some computational results using data from real-life examples, as well as generated data.

Nesim K. Erkip is a professor in Department of Industrial Engineering at Bilkent University, located in Ankara, Turkey. Prof. Erkip received his M.S. and Ph.D. from Stanford University and his B.S. from METU. He has been teaching since 1979 and has held visiting and research positions at Cornell, UC Berkeley, Stanford, and Eindhoven. He is currently visiting NYU Stern. He was a Fulbright Scholar in 1995. He has long served higher education in Ankara, at METU and at Bilkent where he joined in 2005. He has mentored dozens of M.S. and Ph.D. students, and served as an associate editor in a few journals. Currently, he serves in the editorial board of Flexible Services and Manufacturing Journal, a new journal by Springer. His research interests are Multi-echelon Inventory Systems, Supply Chain Management, and Inventory Theory and Production Planning.

03/21/12 RUTCOR BrownBag - 12:00 Noon

Speaker: Yao Zhao, Ph.D.
Affiliation: Department of Supply Chain Management and Marketing Science, Rutgers University
Title: Why Boeing 787 slips were inevitable?

Abstract: Boeing 787, the so-called dreamliner, was the fastest-selling plane ever in the commercial aviation industry. However, its development was a nightmare -- the first flight was delayed by 26 months and the first delivery by 40 months with a cost overrun of at least $10 Billion. In this talk, we identify the root cause for a majority of the delays to be moral hazard in development chain by reconciling empirical evidence with a game theoretical model of prisoners' dilemma. We also show how to align the incentives in the development chain to avoid such delays next time.

03/19/12  Special MSIS/RUTCOR Joint Seminar - 1:00PM

Speaker: Sheldon M. Ross
Affiliation: University of Southern California
Location: 1 Washington Park #1027, Newark Campus
              Videoconference at Levin 130
Title: A Hazard Based Credit Risk Default Model

Abstract: We consider a portfolio of n entities, each of which is subject to default, and suppose that the default of entity increases the instantaneous default rate of the not yet defaulted entity j by the amount λ(i,j),i ≠ j.. We derive the joint density function of the default times and use it to show that the total amounts of hazard that each of the n entities experience before defaulting are independent exponential exponential random variables with common mean 1. We show the default times are associated. We also present efficient ways to simulate the default times. We then generalize the model to allow for "outside shocks".

Sheldon M. Ross is the Daniel Epstein Chair professor in the Department of Industrial and Systems Engineering at the University of Southern California. He received his Ph.D. in statistics at Stanford University in 1968 and he served as a Professor at the University of California, Berkeley from 1976 until 2004. Dr. Ross is the author of Introduction to Mathematical Finance: Options and Other Topics, Simulation, A First Course in Probability, Probability Models for Computer Science and many more titles and articles in the areas of statistics and applied probability. He is the founding and continuing editor of the journal Probability in the Engineering and Informational Sciences, a fellow of the Institute of Mathematical Statistics, and a recipient of the Humboldt U.S. Senior Scientist Award.

02/20/12  Special MSIS/RUTCOR Joint Seminar - 1:00PM

Speaker: Stathis Tompaidis
Affiliation: University of Texas at Austin
Location: 1 Washington Park #1027, Newark Campus
             Videoconference at Levin 130
Title: Transmission of Risk in a Supply Chain

Abstract: We present an equilibrium model of price dynamics for the transmission of shocks in a supply chain. Starting with exogenous factors for the net supply of the upstream input and the demand for the downstream output, we construct the equilibrium process for the input and output prices, and the spread between input and output prices. We specify and calibrate our model for the case of crude oil and a mix of refined products that includes gasoline and heating oil, in the context of oil refineries and estimate the structural parameters of the model.

This is joint work with Hamed Ghoddusi and Sheridan Titman.

Stathis Tompaidis is an associate professor in Department of Information, Risk, and Operations Management at the McCombs School of Business at the University of Texas at Austin. Prof. Erkip received his Ph.D. from the University of Texas at Austin, and his B.Sc. from Aristotle’s University of Thessaloniki, in Greece. He has held visiting and research positions at the University of Toronto, Instituto Tecnologico Autonomo de Mexico, Columbia University, and Duke University. His research interests are in Computational Finance, Energy Finance, Real Options, Allocation under Constraints, and Enterprise-wide Risk Management.

01/25/12  Special MSIS/RUTCOR Joint Seminar - 1:00PM

Speaker: Marvin K. Nakayama
Affiliation: New Jersey Institute of Technology
Location: 1 Washington Park #1027, Newark Campus
              Videoconference at Levin 130
Title: Constructing Confidence Intervals for Quantiles and Values-at-Risk When Applying Variance-Reduction Techniques

Abstract: The p-quantile of a random variable is the constant for which exactly p of the mass of its distribution lies to the left of that value. An example is the median, which is the 0.5-quantile. Quantiles are widely used in practice to measure risk. In project planning, a planner may want to determine a time t such that the project has a 95% chance of completing by t, which is the 0.95-quantile. In finance, where a quantile is known as a value-at-risk, an analyst may be interested in the 0.99-quantile of the loss of a portfolio over a certain time period (e.g., two weeks), so there is a 1% chance that the loss over this period will be greater than this value. For complex stochastic models, analytically computing a quantile may not be possible, so simulation is often used to estimate it. In addition to providing a point estimate for a quantile, it is also important to give a measure of the estimate's error, which is typically done by giving a confidence interval for the quantile. Indeed, the U.S. Nuclear Regulatory Commission specifies that safety levels for the operation of nuclear power plants be computed in terms of a 95% confidence interval for a 0.95-quantile, which is known as the “95/95 criterion.”

In this talk we present two methods for constructing an asymptotically valid confidence interval for a quantile estimated via simulation using a variance-reduction technique (VRT). We establish the validity of the first method within a general framework for VRTs, encompassing antithetic variates, control variates, Latin hypercube sampling, and a combination of importance sampling and stratified sampling as special cases. This approach relies on showing the quantile estimator satisfies a so-called Bahadur representation, which we also prove. The second technique, developed for the case of importance sampling, uses kernel methods. We present some empirical results comparing the methods.

Marvin K. Nakayama is a professor of computer science at the New Jersey Institute of Technology. He received a Ph.D. in operations research from Stanford University. He won second prize in the 1992 George E. Nicholson Student Paper Competition sponsored by INFORMS and received a CAREER Award from the National Science Foundation. He is the Simulation Analysis and Stochastic Modeling Area Editor for the ACM Transactions on Modeling and Computer Simulation, and the Simulation Area Editor for the INFORMS Journal on Computing. His research interests include simulation, applied probability, statistics, and modeling of cascading failures.

01/19/12  Special MSIS/RUTCOR Joint Seminar - 11:00AM

Speaker: Jian Yang
New Jersey Institute of Technology
Location: Levin Hall 103,New Brunswick Campus
              Videoconference at 1 WP #1027
Title: Analyzing Dynamic Pricing Competition using Nonatomic Games

Abstract: We study a dynamic pricing problem involving competing firms. Over a fixed time horizon, every contestant attempts dynamic pricing to optimally influence demand arrival, which is random and susceptible also to prices offered by other firms. As it possesses features from both game theory and Markov decision processes, the problem is extremely difficult to analyze. We thus first study a nonatomic-game (NG) version of the problem, which instead deals with a continuum of infinitesimal firms. Under reasonable assumptions, we identify a well-behaved equilibrium pricing policy. We then develop a general theory concerning the suitability of NG equilibria to their finite-game counterparts. As numbers of players increase, we show that such equilibria, necessarily insensitive to players’ observations about external conditions, would become ever more suitable for their corresponding finite-player situations. For the original dynamic pricing problem, we can conclude that, when there are enough firms and all of them adopt the NG equilibrium pricing policy, none of them would strongly desire any one-time unilateral deviation.

Jian Yang is an associate professor in Department of Mechanical and Industrial Engineering at New Jersey Institute of Technology (NJIT). Prof. Yang received his B.S. in physics from the University of Science and Technology in China, and his Ph.D. in management science from the University of Texas at Austin. He has been teaching at NJIT since 2000. Prof. Yang’s research interests are in production planning, inventory control, revenue management, stochastic modeling, and game-theoretic applications. He has published about 30 peer reviewed scholarly articles, and he has received research funding from New Jersey Department of Transportation and National Science Foundation.

We have two Seminar Series: Brown Bag Talks and RUTCOR Colloquia.

Brown Bag Talks are usually on Thursdays, 12:00-1:00, in the RUTCOR lounge. Pizza is served but feel free to bring your own lunch. The Brown Bag Series usually host speakers from the RUTCOR community.

RUTCOR Colloquia are usually held Thursdays, 1:30-2:30 PM, in the Seminar Room or Room 139. The RUTCOR Colloquia feature speakers from outside the RUTCOR community.

Special Joint MSIS/RUTCOR Seminar Series are held at
One Washington Park #1027
Video conference Levin #130

Research Areas

Discrete and Combinatorial Optimization
Linear and Nonlinear Programming
Stochastic Optimization
Boolean methods in Operations Research
Queuing Theory
Logical Analysis of Data

Contact Information

If you would like to be one of our speakers, please contact:
Terry Hart