Schedule for: 24w2021 - Combinatorial Optimization for Online Platforms

Note: the Lecture rooms are available after 16:00.

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building. Note that BIRS does not pay for meals for 2-day workshops.

Beverages and a small assortment of snacks are available in the lounge on a cash honour system at BIRS Lounge (PDC second floor).

A buffet breakfast is served daily between 7:00am and 9:00am in the Vistas Dining Room, the top floor of the Sally Borden Building. Note that BIRS does not pay for meals for 2-day workshops.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

Assortment optimization is an important problem that arises in many practical applications such as retailing and online advertising. In this talk, we propose a new data-driven approach to assortment optimization that leverages recent advances in learning machine learning pipelines with combinatorial optimization layers. Under the MNL model, the optimal assortment is revenue ordered. Instead, our approach can be interpreted as a smart greedy algorithm that returns a score ordered assortment, where the scores are learned from data. Since the scores are learned offline, our approach is as fast as a greedy algorithm. Moreover, we conduct extensive numerics and show that it returns near optimal solutions for a variety of choice models and constrained settings.

Consider-then-choose models have received increasing attention in the literature because of their ability to better predict consumer choices. These models suppose that customers follow a two-step procedure when making choices. In the first step, they screen products to filter out undesirable ones and form the so-called consideration set. In the second step, they evaluate all the products in the consideration set and choose their most preferred product. In this work, we study the joint assortment and price optimization problem under the mixture of boundary logit (MBL) choice model, a consider-then-choose model introduced in recent literature (Jagabathula et al. 2020, Jagabathula et al. 2022). The MBL model extends the latent class MNL (LC-MNL) model by incorporating a consideration set layer that is motivated by customers' choice process in online retail platforms. Specifically, the model posits that customers first associate a ​"consideration utility" with each offered product based on inspecting only a small set of key features (e.g., price, avg. rating, etc.), and consider only the products with the highest consideration utility in the assortment. Subsequently, customers re-evaluate their utility from purchasing any product in the consideration set, termed "purchasing utility", by inspecting additional information about each product (e.g., detailed specification, customer reviews, answered questions, etc.). Finally, the customer decides to buy the product with the largest purchasing utility or leaves without making a purchase if the purchasing utility is deemed too small. We first characterize the optimal solution for a single boundary logit type by establishing similarity to the assortment problem under the MNL choice model. Solving the problem in the general case, however, is challenging due to the combinatorial nature of feasible consideration sets across multiple customer types and the non-convexity of the revenue function. Therefore, we analyze the setting where the consideration utility from non-price features is type-independent and show that the optimal solution can be obtained by solving O(N^K) separable optimization problems subject to linear constraints, where $N$ is the number of products and $K$ is the number of customer types. We also show that the pricing problem for a particular case of the MBL model in which customers opt to make a purchase so long as their consideration set is non-empty can be formulated as a MILP. Our numerical analysis provides insights into the structure of the optimal assortment and prices determined by the MBL model. Joint work with Prof. Sajad Modaresi (UNC Kenan-Flagler) and Mohammad Amin Farzaneh (UT Dallas)

We study an assortment optimization problem under a multi-purchase choice model in which customers choose a bundle of up to one product from each of two product categories. Different bundles have different utilities and the bundle price is the summation of the prices of products in it. For the uncapacitated setting where any set of products can be offered, we prove that this problem is strongly NP-hard. We show that an adjusted-revenue-ordered assortment provides a ½-approximation. Furthermore, we develop an approximation framework based on a linear programming relaxation of the problem and obtain a 0.74-approximation algorithm. This approximation ratio almost matches the integrality gap of the linear program, which is proven to be at most 0.75. For the capacitated setting, we prove that there does not exist a constant-factor approximation algorithm assuming the Exponential Time Hypothesis. The same hardness result holds for settings with general bundle prices or more than two categories. Finally, we conduct numerical experiments on randomly generated problem instances. The average approximation ratios of our algorithms are over 99%.

This paper presents the multinomial logit model with repeated customer interactions. In each period, the same customer selects a product from the assortment recommended in that period or opts out. It captures the essence of an increasingly popular business model called the subscription box, exemplified by Stitch Fix and Wantable. From the seller's perspective, the choice probability is updated based on the purchase history. We study the adaptive assortment recommendation strategy for all the periods. Although the problem is generally NP-hard as we show, when the customer interacts with the seller for two periods, we discover the structures of the optimal assortment when the available products in the two periods are identical and develop approximation algorithms in other cases. For more than two periods, although the optimal assortments are intractable, we find that the optimal fixed assortments that are not adapted to the purchase history can achieve 68.47% or 50% of the optimal expected revenue, respectively, when the available products across periods are disjoint or not. Using two public datasets, we demonstrate that the model with repeated customer interactions can better predict the purchase behavior and generates higher revenues.

The ease of online shopping, combined with lenient return policies, has significantly increased the frequency of product returns. According to Guha (2023), about 16.5% of online sales, which equates to $200 billion, were returned in the same year. Beyond the loss of revenue, these returns impose additional costs on retailers, including inspection, refurbishing, and restocking of returned items, compounding the complexity of managing online retail operations. Given these dynamics, managing product returns has become a pivotal challenge within retail operations. Critical questions, such as how to optimize product recommendations in light of return behaviors and determining which types of return behaviors to encourage/discourage, are essential for enhancing revenue and customer experience. Our work tackles these challenges by providing theoretical and empirical insights, notably through a novel comparison of the Sequential Returns model, developed by Wagner and Martinez-de Albeniz (2020), with our newly proposed Bulk Returns model. In the Sequential Returns model, customers are assumed to purchase products one at a time. After each purchase, the consumer engages in a short trial period to familiarize herself with the product. Following this, they may either keep the product, exchange it – thus continuing her search process – or return it and abandon the search process. Conversely, the Bulk Returns model represents a new perspective tailored to convenience-driven consumers who lack the time or patience for sequentially ordering the products that interest them. Under the Bulk Returns model customers simultaneously order multiple products, try them each on, and then keep the one they most prefer, while returning the rest. We primarily focus on the assortment optimization problem under the two returns models, where the goal here is to select a subset of products to make available for purchase aiming to maximize expected profits. We first provide new hardness results and approximation algorithms for both assortment problem, before diving into a theoretical comparison between the profits generated by the two returns models. Ultimately, this comparison reveals that profits are higher under sequential search, which has important implications for how to design returns programs.

In this work, we introduce a general framework for two-sided assortment optimization under general choice preferences. The goal is to maximize the expected number of matches by deciding which assortments are displayed to the agents and the order in which they are shown. In this setting, we identify a wide range of policy classes that matching platforms can use in their design. Our goals are: (1) to measure the value that one class of policies has over another one, and (2) to approximately solve the optimization problem itself for a given class. For (1), we define the adaptivity gap as the worst-case ratio between the optimal values of two different policy classes. We show tight constant gaps between several classes of policies and that the worst policies (relative to the rest) are those who simultaneously show assortments to everyone. For (2), we separately show constant-approximation guarantees for two policy classes which sit in opposite ends of the policy spectrum. This is joint work with Omar El Housni and Ulysse Hennebelle.

A buffet lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building. Note that BIRS does not pay for meals for 2-day workshops.

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!

We consider a sequential assortment selection problem under the MNL choice model, where the universe of items is unknown apriori and we only have distributional information of item features. We observe the items sequentially and upon observing each item, we must decide irrevocably whether to include it in our assortment, or forfeit it forever. The goal is to construct an online policy to select the assortment that maximizes the total expected revenue. We provide simple optimal online selection policies for both unconstrained and cardinality constrained versions of the above setting. Our policies give assortments that are provably competitive even with respect to the optimal-in-hindsight (prophet) benchmark. This is joint work with Salal Humair, Orestis Papadigenopoulos and Assaf Zeevi

We consider a multiclass, multiserver queueing system, in which customers of different types have heterogeneous preferences over the many servers available. The goal of the service provider is to design a menu of service classes that balances two competing objectives: (1) maximize customers’ average matching reward and (2) minimize customers’ average waiting time. A service class corresponds to a single queue served by a subset of servers under a first come, first served–assigned longest idle server service discipline. Customers, acting as rational, self-interested agents aiming to maximize their utility, choose the service class that maximizes their expected ex-ante net utility. This net utility is the difference between the service reward, which depends on the server, and a disutility that reflects the mean steady-state waiting time of the service class they join. We explore this problem under conventional heavy-traffic conditions and demonstrate that any bipartite matching system can be divided into a collection of Complete Resource Pooling (CRP) subsystems, interconnected through a directed acyclic graph (DAG). We prove that this structure, along with the aggregate service capacity of each CRP, determines the vector of steady-state waiting times. We present mixed-integer linear programming formulations for optimizing the delay-reward trade-off and approximating the efficient frontier of Pareto optimal service menus. (Joint work with Lisa Hillas and Varun Gupta)

Online retailers and department stores function as marketplaces for millions of sellers, and consumers rely on the platform's assortment and display decisions to examine different sellers (product) and make purchase decisions. Traditionally, the primary objective of these marketplaces for assortment planning is to maximize revenue, which may create unfairness among sellers. To address this issue, we propose fairness constraints that ensure fair market exposures for all sellers. These constraints ensure each seller to have a minimum market exposure, which may depend on the seller's reputation, product quality, and price, among other features. We show that the optimal solution with fairness constraints is to randomize over at most n nested assortments, where n is the number of sellers (or products), and the optimal solution can be found in polynomial time. When there are business constraints including cardinality constraint on the assortments and limit on the number of different assortments, we first characterize the structure of the optimal solution and then propose efficient heuristics. We further explore the impact of fairness constraints on consumer welfare, we show that consumer welfare always increases when those constraints are imposed. We also show when fairness constraints induce new sellers enter the platform, all involved parties may benefit resulting in a win-win-win situation. Even when there is no new seller entry, we identify cases in which the total welfare improves.

The joint replenishment problem is a classical inventory management problem, where we seek to balance the fixed ordering costs with the cost of maintaining on-hand inventory: specifically, we have a set of item types, for which there is specified demand over a finite, discrete-time horizon; placing any order at a given time incurs a general ordering cost and item-specific ordering costs (independent of the total demand serviced); in addition, there is a corresponding item-specific holding cost incurred that is a function of the length of time that each item is held in inventory; the aim is to minimize the total cost. In practice, not all demand can be met, and some orders are rejected. Our motivation is to study algorithms where these rejections are handled fairly. We consider a setting in which there are C colors (corresponding to markets) and we constrain the solutions to a given total rejection bound for each color class. We give the first constant approximation algorithms for this class of problems (and even a generalization in which there a notion of a C-dimensional feature vector associated with each demand point, and we upper bound the sum of these feature vectors for the rejected orders). As a by-product, we also improve upon known constants achievable for the case with C=1, when we simply bound the number of rejections allowed. This is joint work with Varun Suriyanarayana, Varun Sivashankar, and Siddharth Gollapudi.

Panelists: David Shmoys, Rene Caldentey, Huseyin Topaloglu, Xin Chen. Moderator: Srikanth Jagabathula

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building. Note that BIRS does not pay for meals for 2-day workshops.

Breakfast in Vistas BIRS requires participants to checkout of the guest rooms by 11 M. Since this is in the middle of a session we recommend everyone to check out before the start of the first session and keep their bags at the reception desk. There is no coffee break service on Sunday afternoon, but self-serve coffee and tea are always available in the 2nd floor lounge, Corbett Hall.

In this talk, I consider a natural dynamic staffing problem in which a decision-maker sequentially hires staff over a finite time horizon to meet an unknown target demand at the end. The decision-maker also receives a sequence of predictions about the demand that become increasingly more accurate over time. Consequently, the decision-maker prefers to delay hiring decisions to avoid overstaffing. However, workers' availability decreases over time, resulting in a fundamental trade-off between securing staff early (thus risking overstaffing) versus hiring later based on more accurate predictions (but risking understaffing). This problem is primarily motivated by the staffing challenges that arise in last-mile delivery operations. A company such as Amazon has access to flexible gig economy workers (through Amazon Flex) whose availability decreases closer to the target operating day, but they can be hired at any time before that day if they are available. We study the above problem when predictions take the form of uncertainty intervals that encompass the true demand. The goal of the decision-maker is to minimize the staffing imbalance cost at the end of the horizon against any sequence of prediction intervals being chosen by an adversary. Our main result is the characterization of a simple and computationally efficient online algorithm that obtains the optimal worst-case imbalance cost; said differently, it is minimax optimal. At high level, our algorithm relies on identifying a restricted adversary against which we can characterize the minimax optimal cost by solving a certain offline LP. We then using novel technique show how to "emulate" the LP solution in a general instance (i.e., when facing an unrestricted adversary) to obtain a cost bounded above by the LP's objective. As our base model, we consider staffing for one target demand. We also consider generalizations to multiple target demands with either an egalitarian cost objective (i.e. the worst cost across demands) or a utilitarian cost objective (i.e. sum of costs), and to the case where the hiring decisions can be reversed at given discharging costs. We show how to extend our LP-based emulator minimax optimal policy to these settings. The talk is based on a joint work with Yiding Feng and Vahideh Manshadi (working paper): https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4732158

In the Network Revenue Management (NRM) problem, products composed of up to L resources are sold to stochastically arriving customers. We take a randomized rounding approach to NRM, motivated by developments in Online Contention Resolution Schemes (OCRS). The goal is to take a fractional solution to NRM that satisfies the resource constraints in expectation, and implement it in an online policy that satisfies the resource constraints in any state, while (approximately) preserving all of the sales that were prescribed by the fractional solution. OCRS cannot be naively applied to NRM or revenue management problems in general, because customer substitution induces a negative correlation in products being demanded. We start by deriving an OCRS that achieves a guarantee of 1/(1+L) for NRM with customer substitution, matching a common benchmark in the literature. We then show how to beat this benchmark for all integers L>1 assuming no substitution, i.e. in the standard OCRS setting. By contrast, we show that this benchmark is unbeatable using OCRS or any fractional relaxation if there is customer substitution, for all integers L that are the power of a prime number. Finally, we show how to beat 1/(1+L) even with customer substitution, if the products comprise one item from each of up to L groups. Our results have corresponding implications for Online Combinatorial Auctions, in which buyers bid for bundles of up to L items, and buyers being single-minded is akin to no substitution. Our final result also beats 1/(1+L) for Prophet Inequality on the intersection of L partition matroids. All in all, our paper provides a unifying framework for applying OCRS to these problems, delineating the impact of substitution, and establishing a separation between the guarantees achievable with vs. without substitution under general resource constraints parametrized by L. Joint work with Calum MacRury and Jingwei Zhang.

In the dynamic matching problem, customers arrive according to a Poisson process and must be matched to available servers within a network of queues. These servers independently replenish and renege from the market. Despite the expanding research on approximation algorithms for dynamic matching problems, previous literature often concentrates on static policies—where matching decisions are not fully adapted to the servers' varying queue lengths. In this work, we develop tighter linear programming (LP) relaxations, which prescribe adaptive matching policies, and yet can be approximated in polynomial time. We develop two applications of this LP framework that yield new approximation algorithms for the dynamic matching problem. First, we devise a bi-criteria approximation scheme for dynamic matching on Euclidian graphs. The goal is to find a matching policy that approaches any feasible target for the matching cost rate and throughput rate arbitrarily closely. The approximation scheme combines our new LP framework with an instance decomposition that allocates the cost-throughput rate targets across localized subproblems. Second, we devise a (1-1/e)-approximation for the reward maximization version of the dynamic matching problem. The algorithm relies on a new continuous-time LP rounding in tandem with a simple offline contention resolution scheme. The analysis is significantly simpler than the approach of Aouad and Saritaç (2022), and our new policy leverages queue length information to guide its randomized matching decisions. Joint work with Alireza AmaniHamediani (LBS) and Amin Saberi (Stanford U)

We consider a finite horizon online resource allocation/matching problem where the goal of the decision maker is to combine resources (from a finite set of resource types) into feasible configurations. Each configuration is specified by the number of resources consumed of each type and a reward. The resources are further subdivided into three types - offline, online-queueable (which arrive online and can be stored in a buffer), and online-nonqueueable (which arrive online and must be matched on arrival or lost). We prove the efficacy of a simple greedy algorithm when the corresponding static planning linear program (SPP) exhibits a non-degeneracy condition called the general position gap (GPG). In particular we prove that, (i) our greedy algorithm gets bounded any-time regret when no configuration contains both an online-queueable and an online-nonqueueable resource, and (ii) O(log t) expected any-time regret otherwise (we also prove a matching lower bound). By considering the three types of resources, our matching framework encompasses several well-studied problems such as dynamic multi-sided matching, network revenue management, online stochastic packing, and multiclass queueing systems.

Motivated by a behavioral health application, we study the problem of optimizing personalized interventions for patients to maximize a long-term outcome, where interventions are capacity-constrained. We assume there exists a dataset collected from an initial pilot study that we can learn from. We present a method that we dub DecompPI, which approximates one step of policy iteration. Implementing DecompPI simply consists of a single prediction task using the dataset, alleviating the need for online experimentation. DecompPI is a generic model-free algorithm that can be used irrespective of the underlying patient behavior model. We derive theoretical guarantees on a simple, special case of the model that is representative of our problem setting. We establish an approximation ratio for DecompPI with respect to the improvement beyond a null policy that does not allocate interventions. We conduct a rigorous empirical case study using real-world data from a mobile health platform for improving treatment adherence for tuberculosis. Using a validated simulation model, we demonstrate that DecompPI can provide the same efficacy as the status quo approach with approximately half the capacity of interventions.

A buffet lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building. Note that BIRS does not pay for meals for 2-day workshops.