Seminars for Spring 2012
05/03/12 RUTCOR Colloquium - 2:30PM
(PLEASE NOTE CHANGE OF TIME)
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.