R. Ravi
Professor of Business, and Professor of Operations Research and Computer Science Carnegie Mellon University
- Pittsburgh PA
Ravi's research is on models, methods and applications of discrete optimization.
Biography
Ravi has been at the Tepper School of Business since 1995 where he served as the Associate Dean for Intellectual Strategy from 2005-2008, and Chair of the Future Educational Delivery Committee that launched the online hybrid Tepper MBA in 2013. Ravi is currently Director of Analytics Strategy at the school as part of which he founded the Center for Intelligent Business. He has been an Amazon Scholar since 2021.
Ravi's research is on models, methods and applications of discrete optimization. He studies models and methods in combinatorial and network optimization, and their applications in the intersection of business and technology, specifically in the areas of supply chains and logistics in Operations, and online advertising in Marketing. His work has been supported by an NSF Career Award, and grants from Google, the NSF, the ONR and the AFOSR. His 1989 paper in the ACM STOC conference won the 30-year test of time award in 2023.
Ravi's research has been supported by the U.S. National Science Foundation Office of Naval Research and Air Force Office of Scientific Research. He has supervised over two dozen doctoral students and developed over half a dozen new graduate classes. He served as area editor for the INFORMS flagship journal Operations Research in charge of the discrete optimization area from 2012 to 2017, and was chair of the IEEE FOCS conference in 2008.
Ravi held the title of Andris A. Zoltners Professor of Business between 2014 and 2024, Rohet Tolani Distinguished Professor between 2014 and 2018, and Carnegie Bosch Professor between 2006 and 2013. He was elected a fellow of the INFORMS in 2017.
Q6
Areas of Expertise
Media Appearances
Display Advertising Switched to First-price Auctions After Adoption of Header Bidding, New Study Finds
CMU News online
2020-04-22
“The prevailing wisdom explaining the move was that first price auctions were more transparent since you pay what you bid,” says R. Ravi, Andris A. Zoltners Professor of Business and Professor of Operations Research and Computer Science at CMU’s Tepper School of Business, who coauthored the study with his two former doctoral advisees.
Tepper Faculty Member Tapped to Join Amazon Scholars Program
CMU News online
2022-01-11
“Joining the Amazon Scholars Program is an incredible opportunity for me,” Ravi stated. “It will allow me to apply my research on network optimization and omni-channel fulfillment to make an important impact on Amazon’s systems, business, and customer experience.”
Media
Social
Accomplishments
George Leland Bach Teaching Award for Excellence in the MBA Classroom, Tepper School of Business
2013
Education
Brown University
Ph.D.
Computer Science
1993
IIT Madras
B.Tech.
Computer Science and Engineering
1989
Languages
- English
- French
- German
- Tamil
Articles
Approximately Packing Dijoins via Nowhere-Zero Flows
Combinatorica2025
In a digraph, a dicut is a cut where all the arcs cross in one direction. A dijoin is a subset of arcs that intersects each dicut. Woodall conjectured in 1976 that in every digraph, the minimum size of a dicut equals to the maximum number of disjoint dijoins. However, prior to our work, it was not even known whether at least 3 disjoint dijoins exist in an arbitrary digraph whose minimum dicut size is sufficiently large. By building connections with nowhere-zero (circular) k-flows, we prove that every digraph with minimum dicut size contains disjoint dijoins if the underlying undirected graph admits a nowhere-zero (circular) k-flow.
Optimal Decision Tree and Adaptive Submodular Ranking with Noisy Outcomes
Journal of Machine Learning Research2024
In pool-based active learning, the learner is given an unlabeled data set and aims to efficiently learn the unknown hypothesis by querying the labels of the data points. This can be formulated as the classical Optimal Decision Tree (ODT) problem: Given a set of tests, a set of hypotheses, and an outcome for each pair of test and hypothesis, our objective is to find a low-cost testing procedure (ie, decision tree) that identifies the true hypothesis. This optimization problem has been extensively studied under the assumption that each test generates a deterministic outcome. However, in numerous applications, for example, clinical trials, the outcomes may be uncertain, which renders the ideas in the deterministic setting invalid.
A new integer programming formulation of the graphical traveling salesman problem
Mathematical Programming2023
In the Traveling Salesman Problem (TSP), a salesman wants to visit a set of cities and return home. There is a cost of traveling from city i to city j, which is the same in either direction for the Symmetric TSP. The objective is to visit each city exactly once, minimizing total travel costs. In the Graphical TSP, a city may be visited more than once, which may be necessary on a sparse graph. We present a new integer programming formulation for the Graphical TSP requiring only two classes of polynomial-sized constraints while addressing an open question proposed by Denis Naddef. We generalize one of these classes, and present promising preliminary computational results.
Order fulfillment under pick failure in omnichannel ship-from-store programs
Manufacturing & Service Operations Management2023
Problem definition: We consider the setting where a retailer with many physical stores and an online presence seeks to fulfill online orders using an omnichannel fulfillment program, such as buy-online ship-from-store. These fulfillment strategies try to minimize cost while fulfilling orders within acceptable service times. We focus on single-item orders. Typically, all online orders for the item are sent to a favorable set of locations to be filled. Failed trials are sent back for further stages of trial fulfillment until the process times out. The multistage order fulfillment problem is thus an interplay of the pick-failure probabilities at the stores where they may be shipped from and the picking, shipping, and cancellation costs from these locations.
Dynamic pricing with monotonicity constraint under unknown parametric demand model
Advances in Neural Information Processing Systems2022
We consider the Continuum Bandit problem where the goal is to find the optimal action under an unknown reward function, with an additional monotonicity constraint (or," markdown" constraint) that requires that the action sequence be non-increasing. This problem faithfully models a natural single-product dynamic pricing problem, called" markdown pricing", where the objective is to adaptively reduce the price over a finite sales horizon to maximize expected revenues. Jia et al'21 and Chen'21 independently showed a tight regret bound over rounds under* minimal* assumptions of unimodality and Lipschitzness in the reward (or," revenue") function.
Vertex downgrading to minimize connectivity
Mathematical Programming2023
We consider the problem of interdicting a directed graph by deleting nodes with the goal of minimizing the local edge connectivity of the remaining graph from a given source to a sink. We introduce and study a general downgrading variant of the interdiction problem where the capacity of an arc is a function of the subset of its endpoints that are downgraded, and the goal is to minimize the downgraded capacity of a minimum source-sink cut subject to a node downgrading budget. This models the case when both ends of an arc must be downgraded to remove it, for example. For this generalization, we provide a bicriteria (4, 2)-approximation that downgrades nodes with total weight at most 4 times the budget and provides a solution where the downgraded connectivity from the source to the sink is at most 2 times that in an optimal solution.
