Modeling Revenue Optimization Without Degrading Customer Satisfaction: A Knapsack Problem

Abhishek Das
Oct 30, 2019 · 5 min read

In this write-up, we unpack how Onera can model, optimize and increase the revenue (or gross margins) for its retail clients while maintaining a superior level of customer service.

Optimizing the Retail Landscape

Onera’s typical clients are very large retailers and brands. These companies have hundreds, if not thousands, of stores and sell millions of different products. Traditional retail stores, however, do not operate like fulfillment centers. While fulfillment centers are built to support pick, pack, and ship services, stores are more complex fulfillment environments — subject to shrinkage, inventory inaccuracy, human error, as well as in-store traffic demanding superior level of customer satisfaction. Such environments introduce unpredictability and risk that inventory may not be found to fulfill an omnichannel order, leading to canceled and degraded customer satisfaction.

Managing online availability when stores act as fulfillment centers requires a careful balance.

How Onera determines and models customer satisfaction is an entirely different, complex topic for another day. For simplicity’s sake, each unit of product that a retailer can sell can be thought to have an expected customer satisfaction rate. Retailers have the option of selling more of a certain product or less. Selling more of that product may increase revenue (or overall margin), but may bring down the customer satisfaction rate — and vice-versa. The paramount question is how to optimize a retailer’s overall revenue without degrading customer satisfaction. At Onera, we realized that we can model and solve this as a Knapsack problem.

A Brief Note on Problem Complexity

Broadly speaking, problems in computer science fall under many complexity classes, each of which characterize the hardness of solving a problem. At one end of of the spectrum are problems so hard that computers will never be able to solve them, called Undecidable Problems. P is the complexity class that modern day computers (no quantum computers needed) can solve efficiently, and so one will interchangeably hear the term tractable for these problems. NP is the class of problems that are harder (to be precise, not easier) than those in P.

NP-Complete is a complexity class that contains a collection of problems which are all ‘equally’ hard, such that a Nobel prize winning work (essentially) showed that if you prove one of them to be a tractable problem, then all of them are tractable. If none of them are known to be tractable, one will interchangeably hear the term intractable to refer to these problems.

Problems in this believed-to-be-intractable complexity class include many that are important for humans to solve — for example, simple characterizations of the protein folding problem. However, we have also leveraged this (likely) gap in tractability in good ways. For example, all of internet security by way of public key crypto-systems relies on the assumption that there are fundamentally intractable problems in NP-complete class that do not belong in P, specifically to create cryptographic one-way functions. If this assumption fails, then the entire fabric of public key crypto-systems fails and the world economy will crash completely.

Introducing the Knapsack Problem

It is a problem that every person has faced while packing a bag for vacation. You have I different items, each item i has a value v and size w. You want to pack the set of most valuable items, defined as the sum of all its values, while ensuring that the sum of their sizes do not exceed the size of the knapsack W. This is a deceptively simple problem—but if you can write a computer program to solve it fast provably, then you will bring down the world economy.

You may now see the relationship between the knapsack problem and the optimization that retailers have to perform. The set I is simply every product that the retailer sells. Each item i, has the value v(i), which is the expected revenue (or margin) that the retailer makes if they sell that item. Corresponding to that, there is w(i), which is the expected number of dissatisfied customers (the size of the item in the knapsack problem).

The retailer now needs to maximize the revenue, or pack as many valuable items into the knapsack, while ensuring that the customer satisfaction rate does not drop below threshold t. We note that customer satisfaction rate and number of (dis)satisfied customers (W) can be used interchangeably because of some simple normalization. And so, we have the following problem:

As you may have guessed, this would mean that solving this problem to optimize a retailer’s revenue would be impossibly hard since that would imply showing P=NP and bringing down the entire world economy. So how do we achieve this without the world changing forever? We explain that in a future blog post.

Engineering @ Onera

Powering limitless commerce.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store