VI ALIO/EURO Workshop on Applied Combinatorial Optimization


December 15 - 17, 2008, Buenos Aires, Argentina




Using Combinatorial Optimization for Revenue Management

Gustavo Vulcano

Stern School of Business, New York University

Revenue Management is the collection of strategies and tactics firms use to scientifically manage demand for their products and services. The practice has grown from its origins in airlines to its status today as a mainstream business practice in a wide range of industry areas, including hospitality, energy, fashion retail, and manufacturing. Every seller of a product or service faces a number of fundamental decisions. You want the price to be right not so high that you put off potential buyers and not so low that you lose out on potential profits. You would like to know how much buyers value your product, but more often than not you must just guess at this number. Businesses face even more complex selling decisions. For example, how can a firm segment buyers by providing different conditions and terms of trade that profitably exploit their different buying behavior or willingness to pay? How can a firm design products to prevent cannibalization across segments and channels? Once it segments customers, what prices should it charge each segment? If the firm sells in different channels, should it use the same price in each channel? How should prices be adjusted over time based on seasonal factors and the observed demand to date for each product? If a product is in short supply, to which segments and channels should it allocate the products? How should a firm manage the pricing and allocation decisions for products that are complements (seats on two connecting airline flights) or substitutes (different car categories for rentals)? Revenue management is concerned with the methodology and systems required to make demand-management decisions, which can be categorized into:

(i) Structural decisions: Which selling format to use (such as posted prices, negotiations or auctions); which segmentation or differentiation mechanisms to use (if any); which terms of trade to offer (including volume discounts and cancelation or refund options); how to bundle products.

(ii) Price decisions: How to set posted prices, individual-offer prices, and reserve prices (in auctions); how to price across product categories; how to price over time; how to markdown (discount) over the product lifetime.

(iii) Quantity decisions: Whether to accept or reject an offer to buy; how to allocate output or capacity to different segments, products or channels; when to withhold a product from the market and sale at later points in time.

This talk will provide an introduction to this increasingly important subfield of operations research. In particular, we will focus on revenue management problems that belong to the arena of combinatorial optimization, and that have been solved using integer programming or heuristics arguments. We will also mention some of the new problems that are of interest nowadays, and where combinatorial optimization could provide answers of practical relevance.