Roll with the Demand

Published by strangeworks (07/10/2020)

Consider the following hypothetical problem.

For mysterious reasons, customers’ demand for toilet paper exceeds supply. Retailers are unable to maintain sufficient stock. Our challenge is to optimize the stocking of toilet papers at each grocery to best meet the demand. Maximizing the ease for the population to find toilet paper is the goal. In general, the population sees the markets as a network. If toilet paper is out of stock at their first choice of market, they will go to one of the neighboring markets. Here is a diagram showing the five markets selling toilet paper in one town.

The connections between markets represent the closest neighboring markets. For example, if someone goes to Market 4, and finds it has run out of toilet paper, they will check a neighboring market; Market 2 or Market 3. The more markets people have to check, the more frustrated they become. 

In this example we will use a quantum computing algorithm in QISKIT to simplify the number of visits to a market.

Let's add more details to define the problem better. There is not enough toilet paper to deliver to all the markets each day. Distributors decided to deliver toilet paper to two groups of markets on alternating days. Let us try to group the markets into two groups, odd-day deliveries and even-day deliveries, such that if one group doesn't have toilet paper today, there is a neighboring market that does. The generalization of this problem is known as the Max-Cut Problem. The goal of Max-Cut is to find an efficient way to determine the one continuous curvy line to divide (or cut) a network into two parts with the condition that the line maximizes the number of cut connections. 

Here is an example of what it means to cut the network.

The cut divides the network into two. Pink for markets that will get toilet paper on odd days, blue for those that get it on even days. The cut we depicted above, cuts a total of two connections. However, this doesn't solve the toilet paper problem as well as it could. If one goes to Market 4 and it is out of toilet paper, its neighboring markets, Market 2 and Market 3, are also out of stock. This could upset some people.

It is possible to find better cuts. For example, this one:

Here, every Pink Market has at least one neighbor that is a Blue Market, and vice versa. 

There are many other possible cuts. 

In fact, to be certain of finding the optimal solution, one has to try all possible cuts. This is very inefficient for large networks, and is why Max-Cut belongs to the complexity class of NP-Complete. It is currently thought that there is no way to find the best solution for any network with an efficient algorithm, not even with a quantum computer.

Although one cannot find an efficient algorithm that finds the optimal solution for every network, it is customary to redefine this problem with more modest goals. Complexity Theorists listened to Seneca the Elder said, “It is not the man who has too little that is poor, but the one who hankers after more.” The standard thing to do is to propose a more modest version of Max-Cut where one is content with finding pretty-good solutions with high probability.

Here, we do just that with a quantum algorithm. For this network, we use a Quantum Approximate Optimization Algorithm (QAOA) to do just that. The code here is based on the excellent tutorial in IBM's QISKIT Textbook. Please refer to the textbook to explore how the quantum algorithm works in detail.

Please run the code now.

I'll wait here. ⌛

Good job!

Now that you ran the algorithm, you have obtained one of the possible solutions. Remember, QAOA finds a solution that is pretty close to what is the expected best solution. This code displays the proposed solution as a binary string x∗x^*. To explain how to interpret this, if the answer was x∗=10110x^*=10110​, each binary digit corresponds to a market, 00​ being in the pink group, and 11​ in the blue group.

Which means that on odd days, the following Markets in the network get deliveries.

And on even days, the rest of the Markets in the network get deliveries.

After this proposed cut, the code also displays how many cut connections this solution achieves, C(x∗)C(x^*)​. For x∗=10110x^*=10110​​, it is 44​​ cut connections, which is quite good. Also, the code tells you at the end how good it was on average at finding solutions compared to the ideal average. In other ways, it tells you how close you were to the optimal solution. This algorithm should give you a result that is pretty close to it. But, remember what Epicurus once said “Do not spoil what you have by desiring what you have not; remember that what you now have was once among the things you only hoped for.”