VISITS/EXTERNAL SEMINAR:
Santanu Dey from Georgia Institute of Technology gave a talk on 6th April 2010.
Title: The Chvatal-Gomory closure of an Ellipsoid is a Polyhedron.
Abstract: It is well-know that the Chvatal-Gomory (CG) closure of a rational polyhedron is a rational polyhedron. In this talk, we show that the CG closure of an bounded full-dimensional ellipsoid, described by rational data, is a rational polytope. To the best of our knowledge, this is the first extension of the polyhedrality of the CG closure to a non-polyhedral set. A key feature of the proof is to verify that all non-integral points on the boundary of ellipsoids can be separated by some CG cut. Given a point u on the boundary of an ellipsoid that cannot be trivially separated using the CG cut parallel to its supporting hyperplane, the proof constructs a sequences of CG cuts that eventually separate u. The polyhedrality of the CG closure is established using this separation result and a compactness argument.
Bio:
Santanu Dey finished his Ph.D. from the School of Industrial Engineering at Purdue Univerity. He worked as a research fellow at the Center for Operations Research and Econometrics (CORE) of the Catholic University of Louvain in Belgium. He is currently an assistant professor in Stewart School of Industrial and Systems Engineering at Georgia Institute of Technology. His research interests are in the areas of large-scale optimization, mixed integer programming, and various applications of discrete optimization.
Gautam Gupta (NASA Ames Research Centre, Moffettfield, “Scheduled Vs. Chartered Airlines” on 30th March 2010)gave a seminar
Title: Scheduled Vs. Chartered Airlines
Abstract:By their very nature, scheduled airlines cause delays to passengers. A high value of time coupled with extended delays might warrant the use of an unscheduled or charter service by passengers. Recent advances in communication technology and introduction of new aircraft fuel the possibility of such on-demand air travel.
The entry of a charter service in any market would result in price and/or service frequency competition between the charter and scheduled service. Further, strategic planning of the charter service would also incorporate elements of competition. A charter service could make strategic operational decisions using existing models of scheduled airline operations. But in light of the effects of competition and inherent "on-demand" nature, charter planning would differ from scheduled planning. Thus, various aspects of charter planning such as selection of demand to be served, scheduling, routing need to be studied, along with price and frequency competition.
In this research, we analyze the competition between a charter and scheduled airline, and study some aspects of charter planning in a competitive setting. For analyzing the competition, we build models of various scenarios of price and frequency change, and analyze the equilibrium. These are followed by numerical examples of the theoretical results. For strategic planning, we develop a mixed integer program (MIP) to build a schedule for the charter airline as a direct competitor to existing scheduled service. The MIP further determines optimal routes for the charter fleet, and has the capability to impose some simplified maintenance constraints. Along with discussion of some computational aspects of the MIP, we demonstrate the application in a case study.
Bio:
Dr Gautam Gupta got his bachelors in Civil Engineering from IIT Bombay in 2003, and a MS and PhD in Transportation Engineering from University of California, Berkeley in 2008. He is currently a Research Scientist at UARC-NASA Ames Research Center, researching methods of improving airport efficiency. His research interests include airline operations and planning, airline economics and large scale optimization problems in transportation.
Seminar talk by R. Gopalakrishnan
R. Gopalakrishnan, Senior Divisional Commercial Manager, Mumbai Central Division, Western Railways (Indian Railways) gave a talk "Operations Research Applications in the Railway Industry" on 29th January 2010.
The talk featured a variety of potential applications of O.R. to railway operations, spanning commercial, facility planning and scheduling aspects. One case study on ticketing for Passenger Business was discussed in detail and other applications were outlined, including the freight yard layout problem.
A talk by Ankur A. Kulkarni on 19th January 2010.
Title: Refinement of the Generalized Nash Equilibrium
Abstract of talk: We are concerned with generalized Nash games in which the players' strategy sets are coupled by a shared constraint. A widely employed solution concept for these games is the generalized Nash equilibrium (GNE), which is the natural generalization of the Nash equilibrium. The variational equilibrium (VE) is a specific kind of GNE given by a solution of the variational inequality formed from the common constraint and the mapping of the gradients of player objectives. Our contribution is in providing conditions under which the existence of a GNE is necessary and sufficient for the existence of a VE; in such an instance, the VE is said to be a "refinement" of the GNE. Establishment of this result is seen to be of relevance to pure, applied and computational game theorists. We present a theory that gives sufficient conditions for the VE to be a refinement of the GNE. For certain games these conditions are shown to be necessary. This theory rests on a result showing that the GNE and the VE are equivalent upto the Brouwer degree of certains functions whose zeros are the GNE and VE respectively. In the primal space we show equality between the Brouwer degrees of the natural maps of the quasi-variational inequality and the variational inequality, whose solutions are the GNE and VE respectively. Using a novel equation reformulation of the VE, this result is extended to the primal-dual space. These degree theoretic relationships pave the way for the aforesaid sufficient conditions. Our results unify some known results about shared constraint games and provide mathematical justification for ideas that were known to be appealing to economic intuition.
Speaker Bio: Ankur Kulkarni is a doctoral student at the University of Illinois at Urbana-Champaign (UIUC), USA. He received his B.Tech. in Aerospace Engineering from Indian Institute of Technology, Bombay in 2006 and M.S. in General Engineering from UIUC in 2008. He was a visiting scholar at the Tata Institute of Fundamental Research, Mumbai in 2008
Dr Rituparna Sen gave a talk on 15th January 2010 for IEOR group.She is currently working as Assistant Professor at the Department of Statistics, University of California - Davis.
Title: Option Pricing and Hedging in the Incomplete Market.
Abstract of talk: An important aspect of the stock price process, which has often been ignored in the financial literature, is that prices on organized exchanges are restricted to lie on a grid. We consider continuous-time models for the stock price process with random waiting times of jumps and discrete jump size. We consider a class of pure jump processes that are ``close'' to the Black-Scholes model in the sense that as the jump size goes to zero, the jump model converges to geometric Brownian motion. We study the changes in pricing caused by discretization. Upper and lower bounds on option prices are developed. We show that it is possible to hedge options if one restricts to jumps of size one, that is, if one models the stock price process as a birth and death process. One needs the stock and another market traded derivative to hedge an option in this setting. We obtain parameter estimates using Generalized Method of Moments. We use filtering equations for inference in the stochastic intensity setting. We present real data applications to study the performance of our modeling and estimation techniques.
Anand kulkarni a young scientist and mathematician in graduate school at the Department of Industrial Engineering and Operations Research at UC Berkeley gave a technical talk on 6th January 2010 for IEOR group.
Title: An Inductive Approach to Hirsch's Conjecture (and other open problems on polytopal graphs).
Abstract of the talk: A number of long-standing open questions exist about polytopes and their edge-vertex graphs, such as their diameter, edge expansion, and the number of distinct polytopes with a given number of facets. The most famous of these unsolved problems, the polynomial Hirsch conjecture, is one of the most important open questions in both the theory of polytopes and the theory of optimization, with implications for producing strongly polynomial-time algorithms for linear programming. The problem is easy to state: can the diameter of a polytopal graph polynomially or linearly bounded? Despite its apparent simplicity, surprisingly modest progress has been made in the fifty-two years since the problem's inception.
In this talk, He presented a new "gemcutting" strategy that can be used to prove properties of polytopal graphs, enabling a novel approach to the Hirsch conjecture and its relatives. Showed that any combinatorial type of simple polytope may be generated from the simplex by applying a sequence of cutting planes and constraint perturbations, allowing inductive proofs of its combinatorial properties by verifying that they are invariant under these operations. He demonstrate the use of this strategy to resolve most cases of the Hirsch conjecture via an inductive argument, suggesting that a resolution to the Hirsch conjecture may be near. Main result reduces proof or disproof of the overall Hirsch conjecture to a new, tightly-constrained special case.
He also discussed the application of this method to the problem of enumerating the class of combinatorially distinct polytopes; the extreme size of this class motivates some interesting open questions about reducing the complexity of this algorithm.
Prof H.S.Jacob Tsao, Professor from San Jose State University, U.S.A., visited the IEOR group on 9 December 2009. Prof Tsao works in the area of Optimization and Operations Research and has also contributed to numerous applications to Transportation Systems, both in the road and aviation sectors.
Visit by Mr Rakesh Kulkarni, Xerox Corporation
Mr Rakesh Kulkarni, Research Scientist at the Xerox Innovation Group (the research arm of Xerox Corporation), visited the IEOR group on 30-11-2009 and had discussions with the faculty with a view to explore possible associations of the group with the Xerox India Innovation Hub, including joint research activities and student projects.
D. Yogeshwaran, Research Scholar at ENS (Ecole Normale Superieure)/INRIA, Paris, France, gave a seminar talk on "Percolation and Connectivity in AB Random Geometric Graphs" on August 27, 2009.
Visit and Lecture series by Prof Joydeep Dutta
Prof Joydeep Dutta (Department of Mathematics and Statistics, IIT Kanpur) visited the IEOR group between 27 and 30 July, 2009.
He delivered a series of lectures: (1) Fundamentals of Mathematical Programming (2) Variational Inequalities (3) Gap Functions and (4) Nonlinear Complementarity Functions during his visit. These lectures were attended by senior students, research scholars and faculty from IEOR and other parts of the institute.
Visit and a talk by R. K. Amit
R. K. Amit gave a technical talk on "Dynamic Contracts for Demand Management" on 28th May 2009 for IEOR group. He is currently a PhD candidate at the Department of Management Studies at IISc Bangalore.
Abstract of the talk: For necessary goods, under supply constraints, fairness considerations introduce negative externalities and lead to a market failure. One example of such a necessary good is water. In case of a market failure, it is necessary to design coordination mechanisms called contracts which provide the right incentives for coordination. As "repetition can yield coordination'', the aim in this presentation is to discuss the design of price based dynamic demand management contracts which, under supply constraints, mitigate the market failure. The contracts are designed, within the agency theory framework, where the agent (the consumer) is induced to consume at a specified consumption level based on the incentive mechanism offered by the principal (the producer). These contracts use the solution concept of subgame perfect Nash equilibrium (SPNE) to compute the price (mal-incentive) that acts as a credible threat for deviation from the specified consumption level. In these contracts, unlike the dynamic contracts with asymmetric information, the penalty for deviation is proportional to the amount of deviation. First, we consider a two-period demand management contract for a single consumer satisfying a fairness criterion (status quo proposition). In the finite horizon, a fair demand management contract is shown to be inefficient. Also, the efficiency can be achieved by making the consumer uncertain about the period of interaction. This possibility can be included in an infinite horizon contract. Hence, we design an infinite horizon contract for a single consumer. This contract is proved to be economically efficient and provides revenue sufficiency. The sensitivity analysis of the contract shows that the discounting rate measures the aversion to conservation characteristics of the consumer. Lastly, the infinite horizon contract is extended to two consumers case which internalizes the externality a consumer causes to another. In the two consumer case, consumers are strategically non interacting. These contracts are also shown to be economically efficient. The contracts designed in this part are homeomorphic to alternating bargaining process; and achieve both process and end-state fairness.
Visit and a talk by Prof. V.S. Borkar
Prof. V.S. Borkar, TIFR, Mumbai gave a talk on Reinforcement Learning Algorithms to the IEOR group on 23rd January 2008.
Title : Reinforcement Learning - A bridge between numerical methods and Monte Carlo
Visit and a Series of three talks on Evolutionary Game theory by Dr. A.J. Shaiju
Dr. A.J. Shaiju, Post-Doctoral Fellow - School of Information Technology and Electrical Engineering, University of New South Wales, Australian Defence Force Academy, Canberra, Australia gave a series of three talks to the IEOR group on 22nd, 23rd and 25th January 2008.
Title :Introduction to Evolutionary Game Theory
Abstract: In these talks, we plan to introduce the concept of `Evolutionarily Stable Strategy (ESS for short)' and some of its properties. The so-called `replicator dynamics' and the relationship of its stable equilibrim points with ESS will also be presented. The extension of these ideas to the infinite phenotype case will be discussed.
Click here to view the Technical Report
Visit and a talk by Dr. Sumit Raut
Dr. Sumit Raut, Tata Consultancy Services, Mumbai gave a talk to the IEOR group on 18th January 2008.
Title : Variable and Value Ordering Heuristics for HARD Problems
Abstract: Most of the real-life combinatorial optimization problems (such as, scheduling, network flows) are involved with very large search spaces and very few feasible solutions. These problems typically involve several hundred (or even several thousand) variables, each with up to several hundred possible values, only a very tiny fraction of which ultimately allows for a satisfying solution. It is well-known that the order in which variables are instantiated can make an enormous difference to the search effort in solving this kind of problems. This presentation will address the "issue of how to decide which variable to instantiate next (i.e. variable ordering heuristics), and which value to assign to that variable (i.e. value ordering heuristics) in order to reduce search for a solution.
Dr Anand Deshpande and Mr Mangesh Gharote from TRDDC (The Tata Research Development and Design Centre) Pune visited the IEOR group on Wednesday 5 September. They discussed joint research possibilities with the IEOR group. TRDDC already has an academic alliance with IIT Bombay.
Dr Santanu Dey, Purdue University, gave a talk to the IEOR group on 24 July 2007.
Title : Cutting Planes For Unstructured Mixed Integer Programs Using Multiple Constraints
Abstract : One of the most successful cutting planes used in commercial MIP softwares, the Gomory Mixed Integer Cut (GMIC), is derived using single constraint relaxation of a MIP. It is, in fact, a facet of the single-constraint infinite-group relaxation of a MIP. Numerical and theoretical studies suggest that 'group cuts', such as the GMIC, can be significantly improved by considering information from multiple constraints simultaneously. However, the discovery of facets of multiple-constraint infinite-group relaxations has remained an open problem for 35 years. We introduce an operation that we call sequential-merge and prove that this operator creates facets for multiple-constraint infinite-group problems. These new cutting planes exhibit properties that reflect the benefits of using facets of multiple- over single-constraint relaxations: the continuous variable coefficients of these cuts are undominated by those of GMIC and they can produce cuts that do not belong to the first split closure of MIPs.
About the speaker : Dr Santanu Dey has a M.S. and Ph.D. in Industrial Engineering from Purdue University. He is about to take up a research position at CORE (Centre for Operations Research and Econometrics), University of Louvain, Belgium.
His areas of recent work are in theory and computation in mixed integer programming. He has also worked in some application areas in aircraft operations, protein analysis and bioinformatics.
Visit and talk by Prof. Sunderesh S. Heragu
Prof Sunderesh Heragu, Mary Lee and George F. Duthie Chair in Engineering Logistics, Department of Industrial Engineering, University of Louisville, gave a talk titled "Solution of Semi-open Queuing Networks with Applications in Manufacturing and Distribution" on 9 July, 2007.
Abstract: In this talk, we present semi-open queuing networks (SOQNs) and their applications in manufacturing and distribution. We also present analytical matrix geoemetric method based solution techniques for very efficient solution of SOQNs for single-class as well as multi-class networks. Based on a comparison of the methods with simulation, it appears they outperform all existing techniques for solving single-class SOQNs.
Visit by group from Mathematical and Information Sciences Division of CSIRO, Australia
A group from the Mathematical and Information Sciences Division of CSIRO (Commonwealth Scientific and Industrial Research Organisation) Australia, Dr Mohan Krishnamoorthy, Dr Frank de Hoog and Mr Kevin Cryan, visited the IEOR group on 22 March, to discuss possible research collaborations. CSIRO is a large, multi-divisional government research organization in Australia, roughly equivalent to India's CSIR (Council of Scientific and Industrial Research) labs.
Seminar Talk by Prof. Vijay Kannan
Date & Location: Tuesday, 6th March 2007, 2:30 p.m., ME Seminar Hall (ME 201 )
Speaker: Prof. Vijay Kannan, Professor of Operations Management, College of Business, Utah State University, U.S.A. Currently visiting IIM Lucknow as a Fulbright scholar.
Topic: Service operations strategy - Keys to success
Abstract: As both the size of the service sector as well as competition within it continues to grow, creating value that can endure, and dominating one's competitive space, becomes more important. In the U.S. air transportation industry, one of the few success stories in recent years has been Southwest Airlines. Southwest Airlines serves as the model upon which many new, low cost carriers in India and elsewhere, have based their operations strategy. Using Southwest Airlines as an illustration of a dominant service organization, this presentation highlights some of the keys to success in the service sector, and some of the challenges organizations face in achieving this success.
Visit by Supply Chain Management and Logistics team from Dow Chemicals
A senior management team from Dow Chemicals, including Mr. Peter Halloran, Director - Supply Chain, of the Mumbai Services Centre, and Mr. Don Weintritt, Jr., Director Supply Chain Expertise Centre in Michigan, USA, visited IIT Bombay and the IEOR group on 2 March, 2007. There were presentations by Dow as well as by IIT B and IEOR, followed by discussions with students and faculty from IEOR on possible research and other interactions. A team from Tata Consultancy Services, led by Dr. S. Sen Gupta also participated in the meeting.
Prof. K. P. K. Nair gives talk
Date : Friday, 23rd February, 9.30. a.m.
Speaker: K. P. K. Nair, Professor and Dean Emeritus,
Faculty of Business Administration, University of New Brunswick, Canada
Topic: Optimal Transmitter-Receiver System in a Network
(A presentation based on a collaborative work in progress by Y.P. Aneja, R. Chandrasekaran and K.P.K. Nair)
Abstract:
Consider an undirected network with n nodes and m edges. Each edge is assigned a capacity. If we desire mutual communication between two nodes x and y using edge(x,y) alone, then the transmitter capacity rquired at x and y each is the capacity of edge (x,y). The capacities of the receivers at all nodes are assumed to be identical. The problem is one of determining the transmitter capacity at each node such that all pairs of nodes are able to communicate mutually allowing relays and the sum of transmitter capacities is minimum. A polynomial scheme is envisaged and certain properties relevant are established.
Seminar Talk by Dr. Rahul Marathe
Date & Location: Monday, 12th February 2007, 10:00am, ME Seminar Hall (ME 201 )
Speaker: Dr. Rahul Marathe
Topic: Capacity expansion for uncertain demand
Abstract:
We assume that demand for service follows a geometric Brownian motion process, and that substantial leadtime exists for expansion to be realized. The service provider must maintain certain levels of service and we solve for timings & sizes of future expansion such that an infinite horizon expansion cost is minimized.
Dr Kavita Ramanan from the Department of Mathematical Sciences at Carnegie Mellon University, Pittsburgh, U.S.A. gave a seminar talk on "Optimization and Analysis of Stochastic Networks" on January 23, 2007.
Rajiv Dandotiya, Dual degree student from IIT Kharagpur and Jacques Burrus, Master's student from University of California, Berkeley are spending two months each at IIT Bombay, visiting the IEOR group.
Accenture Technology Labs India meets with IEOR
A team of visitors from Accenture met with the faculty of IEOR, SIT and others to explore the possibility of collaborative R & D with IIT Bombay. The meeting took place on May 15th 2006. The visiting team comprised of-
1. Dr. Anatole Gershman (Global CTO).
2. Dr. Kishore Swaminathan.
3. Dr. Lin I Chase (Bangalore Lab director).
The discussion explored the possibilities of floating scholarships, and starting sponsored project activities. Some of the technical areas for possible collaboration included:
1. Software architecture and modeling, Service oriented architecture, enterprise computing and system integration, etc
2. Data mining, Analytics statistical methods and predictive methods. Supply chain management and OR based studies, etc
3. AI based methods, distributed knowledge based systems, distributed computing architectures, etc.
Seminar Talk by Dr. Debasis Mishra on Shapley Value in Queues
Date & Location: 8th February 2006, 11:20am, ME Seminar Hall (ME 201 )
Speaker: Dr. Debabsis Mishra
Topic: On Computing the Shapley Value in Queues
Abstract: We study fair division with money using the Shapley value solution in two queue settings: (i) every agent is interested in at most one position and his value of a position depends on the agents served before him and (ii) every agent may be interested in more than one position and his value for a bundle of positions is independent of the allocations to other agents. Computing the Shapley value of an agent in these settings requires computing marginal values of that agent to exponential number of coalitions (marginal value problem). Also, every agent needs to know an exponential-sized valu- ation function (valuation problem). We propose a network representation of the queue for setting (i). Finding the longest path in such a graph gives marginal values of every agent to every possible coalition. We propose an auction-like algorithm to find the longest path in this graph and discuss how this reduces the valuation problem. For setting (ii), we show that existing combinatorial auctions reduce both the marginal value problem and the valuation problem for concave games.
About the speaker: Debasis Mishra obtained his Ph.D. from University of Wisconsin-Madison in Industrial Engg and BTech from IITKgp in Industrial Engg. He has held post-doctoral positions at Center for Operations Research and Economtrics (CORE), Belgium, and (currently) at Indian Institute of Science. His research interests are in game theory, auction design, applying discrete optimization ideas to game theoretic problems, and supply chain management.
Taiwanese delegation visits IEOR
Dr. Chun-Hsuing Fang (Dean of Engineering) and Dr. Chengter Ted Ho (Associate Professor, Department of Industrial Engineering and Management) from National Kaohsiung University of Applied Science Taiwan, visited IIT Bombay and met with the faculty of IE & OR. Prof. N. Hemachandra made a presentation about IEOR, emphasising their research activities. Possible modes of collaboration between the two unversities including faculty visits, student exchange and joint projects were discussed.