Raghu RAGHAVAN - Robert H. Smith School of Business / University of Maryland, USA

February 11th 2020 - N405

Tageted Online Adversiting with Multi-Dimensional Bid Adjustments

Abstract: The year 2020 marks the 25th anniversary of online advertising. No other major advertising medium (radio, television, and cable) achieved the growth online advertising had in its first twenty-five years. With new ad delivery methods, platforms, and formats on the rise, the advertisers are now able to collect user characteristic data at an unprecedented level of granularity and harvest the data to gain insights on these characteristics. Online advertising platforms like Google and Bing allow for bid adjustments that permit advertisers to target desired demographics. In addition to bids, the advertisers submit bid adjustments for ad query features such as geographical location, time of day, device, and audience. We introduce the Bid and Bid Adjustment Problem in Online Advertising (BBAP) where an advertiser determines base bids and bid adjustments to maximize their return on investment. The BBAP can be modeled as a nonlinear mathematical program. However, the multiplicative nature of bid adjustments makes the problem very hard to solve optimally. We develop an approach where the mathematical programming formulation is reduced to two tractable subproblems. One to determine the base bids and one to determine the bid adjustments. We show that both subproblems can be modeled as Multiple-Choice Knapsack Problems (MCKPs) when the domain of base bids and bid adjustments are discretized. Furthermore, we show how the solution to the linear programming relaxation of the MCKP can be used to obtain a feasible solution to the BBAP. We iteratively create and solve subproblems, which we call the Iterative Adjustment Algorithm (IAA), to determine a high-quality solution to the BBAP. The IAA is a particularly attractive algorithm from a practical standpoint since the linear programming relaxation of the MCKP can be solved easily even for large problem sizes. To evaluate the quality of the IAA and the benefits of using bid adjustments, we performed computational experiments on simulated data generated based on sample data on Google Keyword Planner. We show the IAA provides near optimal solutions by comparing the revenue obtained from the IAA with an upper bound obtained from a MIP formulation in small instances. Our findings indicate the revenue benefit of using bid adjustments increases as the revenue-per-click variation across features increases and as the budget decreases. We observe the performance of the IAA is robust under varying problem sizes, budget amounts, and revenue-per-click variations.

Maria Grazia SPERANZA - University of Brescia , Italy

January 16th 2020 - N516

A General Heuristic Approach to MILP Problems

Abstract: The Kernel Search (KS) is a general and simple heuristic framework for the solution of Mixed Integer Linear Programming (MILP) problems. The basic idea of the KS is to solve a sequence of MILP sub-problems, each restricted to a subset of variables. The KS has been applied to a variety of problems, often taking advantage of the specific problem structure. The first applications of the KS have been to the multi-dimensional knapsack problem, to a portfolio selection problem and to an index tracking problem. Afterwards, the KS has been successfully applied to capacitated facility location problems, both in the multi-source version and in the single-source variant. More recently, the KS has been extended to the Adaptive Kernel Search (AKS), a heuristic framework for the solution of any MILP problem. The AKS solves a sequence of carefully constructed restricted MILP problems (using a commercial solver). The computational effort required to solve the first restricted MILP problem guides the construction of the subsequent MILP problems. The restricted MILP problems are constructed around a kernel, which contains the variables that are presumably non-zero in an optimal solution. Computational results, on a set of benchmark instances from the MIPLIB library, show that the AKS significantly outperforms other state-of-the-art heuristics for the solution of MILP problems. The AKS also compares favorably to CPLEX and offers more flexibility to trade-off solution quality and computing time. In this talk the KS and the AKS will be presented together with their most relevant applications. Research on the application of the KS to a routing problem will also be presented.

Roberto ROBERTI - School of Business and Economics, Netherlands

November 20th 2019 - N517

Exact Methods for the Traveling Salesman Problem with Drone

Abstract: Efficiently handling last-mile deliveries becomes more and more important nowadays. Using drones to support classical vehicles allows improving delivery schedules as long as efficient solution methods to plan last-mile deliveries with drones are available. We study exact solution approaches for some variants of the traveling salesman problem with drone (TSP-D) in which a truck and a drone are teamed up to serve a set of customers. This combination of truck and drone can exploit the benefits of both vehicle types: the truck has a large capacity but usually low travel speed in urban areas; the drone is faster and not restricted to street networks, but its range and carrying capacity are limited. We present a compact mixed-integer linear program (MILP) for several TSP-D variants that is based on timely synchronizing truck and drone flows; such a MILP is easy to implement but nevertheless leads to competitive results compared to the state-of-the-art MILPs. Furthermore, we introduce dynamic programming recursions to model several TSP-D variants. We show how these dynamic programming recursions can be exploited in an exact branch-and-price approach based on a set partitioning formulation and using ng-route relaxation, dual variable stabilization, and a three-level hierarchical branching. The proposed branch-and-price can solve instances with up to 39 customers to optimality outperforming the state-of-the-art by more than doubling the manageable instance size. Joint work with Mario Ruthmair.

Guillaume ROELS - INSEAD, France

November 7th 2019 - N305

Competitive Bundling in a Bertrand Duopoly

Abstract: In competitive industries, some firms bundle their products whereas others unbundle them; still other firms occupy a niche position and offer only a subset of products. No simple theory has been advanced to explain this variety of bundling strategies. We characterize the strategies of two symmetric firms competing (in a Bertrand fashion) with regard to two homogeneous components, where the firms' bundling and pricing decisions are modeled as a two-stage non-cooperative game. Firms in the first stage select their product offerings, which may include any single-component product and/or the bundle; in the second stage, firms simultaneously set their products prices. We show that, under pure bundling, there is always an equilibrium in which one firm bundles while the other offers only a single-component product. Such bundling serves to soften price competition via product differentiation, and the bundling firm earns more profit---indicative of a first-mover advantage. Under mixed bundling, almost any combination of offerings can be sustained in equilibrium when customer valuations are sufficiently homogeneous. Yet when those valuations are heterogeneous, only three types of equilibria emerge. Our analysis yields these main results: various strategies can be sustained in equilibrium; asymmetric bundling equilibria can emerge even when firms are symmetric; and the more homogeneous are customer valuations, the larger is the set of equilibria.

Saed ALIZAMIR - School of Management - Yale University, USA

October 7th 2019

Electricity Pricing with Limited Consumer Response

Abstract: Matching demand with supply has been a long-standing challenge in operating residential electricity markets. The utility firms often face stochastic demand functions that are affected by the unpredictable exogenous random shocks (e.g., outdoor weather condition). Although various Demand Response programs are in place to regulate electricity consumption, the effectiveness of these programs has been undermined, largely because the consumers have demonstrated limited capability in adjusting their household appliances' settings. In this paper, we construct a demand model to describe how consumers make consumption decisions in response to random external factors representing their ambient environment at a given price. To that end, we adopt the notion of "rational inattention" to capture the consumers' inertia in readjusting their decisions over time. Subsequently, we investigate an electricity firm’s pricing decision as well as its impact on social welfare and system reliability. Our findings highlight the nuanced implications of rationally inattentive consumers, and lead to guidelines for better regulating retail electricity markets.

Victor MARTINEZ DE ALBENIZ, IESE Business School - University of Navarra, Spain

October 3rd 2019 - N516

A model for Integrated Inventory and Assortment Planning

Abstract: Integrating inventory and assortment planning decisions is a challenging task that requires comparing the value of demand expansion through broader choice for consumers, with the value of higher product availability. We develop a model for trading off these values in a setting with limited store capacities and inventory replenishment, two features missing in the literature. The exact analysis of the single product case allows us to develop an accurate approximation for the multi-product case, which incorporates the cost of higher availability in a tractable manner, and hence can be embedded in an optimization framework. We provide algorithms to find optimal or near-optimal solutions. Joint work with Sumit Kunnumkal