# Modeling Revenue Optimization Without Degrading Customer Satisfaction: A Knapsack Problem

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

In today’s retail landscape, customer expectations have never been higher. No matter how or where they choose to shop, they expect in-stock products, fast-and-free delivery, as well as exceptional service. Retailers who get this right are able to transform their stores into fulfillment centers, leveraging their existing operations to offer more products for their customers via omnichannel programs like Ship-From-Store (SFS) and Buy-Online-Pick-Up-in-Store (BOPUS). Each unit of product that they can sell through these programs generates revenue for the retailer.

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.

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

Before introducing the problem itself, it is worth talking about *P *vs* NP*.

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

The Knapsack is a classic problem that is *NP-complete* and, in fact, was among the first problems shown to be NP-complete in the above-mentioned classic computer science paper.

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.