Stock-Sales Strategy in a Simplified Market

This example finds a stock-selling strategy for a simplified market model to demonstrate using a Leap hybrid CQM solver on a constrained problem with integer and binary variables.

In this very simple market, you have some number of shares that you want to sell in daily blocks over a defined interval of days. Each sale of shares affects the market price of the stock,

\[p_i = p_{i-1} + \alpha s_{i-1},\]

where \(p_i\) and \(s_i\) are, respectively, the price and the number of shares sold on day \(i\), and \(\alpha\) is some multiplier.

The goal of this problem is to find the optimal number of shares to sell per day to maximize revenue from the total sales.

The Market with Taxation section adds a tax to the market model to demonstrate the incorporation of binary variables into the CQM.

Example Requirements

The code in this example requires that your development environment have Ocean software and be configured to access SAPI, as described in the Initial Set Up section.

Solution Steps

Section Workflow Steps: Formulation and Sampling describes the problem-solving workflow as consisting of two main steps: (1) Formulate the problem as an objective function in a supported model and (2) Solve your model with a D-Wave solver.

This example formulates this problem as a constrained quadratic model and uses the LeapHybridCQMSampler to find good solutions.

Formulate the Problem

First, define the market parameters.

• max_days is the period over which you should sell all your shares.

• total_shares is the number of shares you own (equal to \(\sum_i s_i\)).

• price_day_0 is the stock price on the first day of the period.

• alpha is a multiplier, \(\alpha\), that controls how much the stock price increases for each share sold into the market.

>>> max_days = 10
>>> total_shares = 100
>>> price_day_0 = 50
>>> alpha = 1

Instantiate a CQM.

>>> from dimod import ConstrainedQuadraticModel
>>> cqm = ConstrainedQuadraticModel()

You can now formulate an objective function to optimize and constraints any feasible solution must meet, and set these in your CQM.

Objective Function

The objective function to maximize is the revenue from selling shares. Because you own an integer number of shares, it is convenient to use integer variables to indicate the number of shares sold each day, shares. For simplicity, this model assumes stock prices, price, are also integers[1].

[1]

One could use integer variables to model stock prices in dollars and cents by multiplying the values by 100; however, this greatly increases the search space. One could also create a compromise model with somewhat greater resolution and search space by rounding to the nearest dime and multiplying prices by 10, for example.

Bounds on the range of values for integer variables shrink the solution space the solver must search, so it is helpful to set such bounds; for many problems, you can find bounds from your knowledge of the problem. In this case,

• On any day, you cannot sell more than the total number of shares you start with.

• The maximum share price is the sum of the initial price and the total price increase that would result from selling all your shares,

  \[\max(p) = p_0 + \alpha * \sum_i s_i.\]

>>> from dimod import Integer
>>> max_p = price_day_0 + alpha*total_shares
>>> shares = [Integer(f's_{i}', upper_bound=total_shares) for i in range(max_days)]
>>> price = [Integer(f'p_{i}', upper_bound=max_p) for i in range(max_days)]

Daily revenue is the number of shares sold multiplied by the price on each sales day.

>>> revenue = [s*p for s, p in zip(shares, price)]

To maximize the total revenue, \(\sum_i s_ip_i\), is to minimize the negative of that same revenue:

>>> cqm.set_objective(-sum(revenue))

Note

As noted in the Bin Packing example, keep in mind that these “variables” are actually class dimod.QuadraticModel objects,

>>> price[0]
QuadraticModel({'p_0': 1.0}, {}, 0.0, {'p_0': 'INTEGER'}, dtype='float64')

with a single variable with the requested label, p_0 or s_0. This means, for example, that multiplying these models to create a revenue[0] “variable” actually creates a new quadratic model,

>>> revenue[0]                               
QuadraticModel({'s_0': 0.0, 'p_0': 0.0},
...            {('p_0', 's_0'): 1.0},
...            0.0,
...            {'s_0': 'INTEGER', 'p_0': 'INTEGER'}, dtype='float64')

with a quadratic bias between p_0 and s_0.

Constraints

The simplified market in this problem has the following constraints:

1. In total you can sell only the number of shares you own, no more, \(\sum_i s_i \le\) total_shares.

>>> cqm.add_constraint(sum(shares) <= total_shares, label='Sell only shares you own')
'Sell only shares you own'

2. On the first day of the selling period, the stock has a particular price \(p_0 =\) price_day_0.

>>> cqm.add_constraint(price[0] == price_day_0, label='Initial share price')
'Initial share price'

3. The stock price increases in proportion to the number of shares sold the previous day:

   \(p_i = p_{i-1} + \alpha s_{i-1}\).

>>> for i in range(1, max_days):
...    pricing = cqm.add_constraint(price[i] - price[i-1] - alpha*shares[i-1] == 0, label=f'Sell at the price on day {i}')

For a sales period of ten days, this CQM has altogether 11 constraints:

>>> len(cqm.constraints)
11

Solve the Problem by Sampling

Instantiate a LeapHybridCQMSampler class sampler,

>>> from dwave.system import LeapHybridCQMSampler
>>> sampler = LeapHybridCQMSampler()     

and submit the CQM to the selected[2] solver.

[2]

You can see the selected solver using the name property; for example,

>>> sampler.solver.name                          
'hybrid_constrained_quadratic_model_version1'

and use feature-based solver selection to select a particular solver.

For one particular execution, with a maximum allowed runtime of a minute, the CQM hybrid solver returned 41 samples, out of which 24 were solutions that met all the constraints:

>>> sampleset = sampler.sample_cqm(cqm,
...                                time_limit=60,
...                                label="SDK Examples - Stock-Selling Strategy")  
>>> print("{} feasible solutions of {}.".format(
...       sampleset.record.is_feasible.sum(), len(sampleset)))   
24 feasible solutions of 41.

The small function below extracts from the returned sampleset the best feasible solution and parses it.

>>> def parse_best(sampleset):
...    best = sampleset.filter(lambda row: row.is_feasible).first
...    s = [val for key, val in best.sample.items() if "s_" in key]
...    p = [val for key, val in best.sample.items() if "p_" in key]
...    r = [p*s for p, s in zip(p, s)]
...    return r, s, best

Parse and print the best feasible solution:

>>> r, s, _ = parse_best(sampleset)                
>>> print("Revenue of {} found for daily sales of: \n{}".format(sum(r), s))     
Revenue of 9499.0 found for daily sales of:
[10.0, 10.0, 10.0, 10.0, 10.0, 10.0, 10.0, 10.0, 9.0, 11.0]

Market with Taxation

The previous sections made use of only integer variables. Quadratic models also accept binary variables. This section models a market in which you pay an additional tax on early sales and uses a binary variable to incorporate that update into the CQM created in the previous sections.

Consider a market in which you pay a tax in amount, tax_payment, for selling shares during the first taxed_period days of the period in which you can sell your shares.

>>> taxed_period = 3
>>> tax_payment = 225

Because you either pay this tax or do not pay it, you can use a binary variable, t, to indicate payment. You can update the previous objective by reducing the revenue from share sales by the tax payment (adding it to the negative revenue) if the t binary variable is 1:

>>> from dimod import Binary
>>> t = Binary('t')
>>> cqm.set_objective(tax_payment*t - sum(revenue))

Binary variable t should be True (1) if sales in the first taxed_period days of the period are greater than zero; otherwise it should be False (0):

\[ \begin{align}\begin{aligned}\sum_{i < \text{taxed_period}} s_i > 0 \longrightarrow t=1\\\sum_{i < \text{taxed_period}} s_i = 0 \longrightarrow t=0\end{aligned}\end{align} \]

One way to set such an indicator variable is to create a pair of linear constraints:

\[\frac{\sum_{i < \text{taxed_period}} s_i}{\sum_i s_i} \le t \le \sum_{i < \text{taxed_period}} s_i\]

To show that this pair of inequalities indeed sets the desired binary indicator, the table below shows, bolded, the binary values \(t\) must take to simultaneously meet both inequalities for \(\sum_{i < \text{taxed_period}} s_i\) with sample values 0, 1, and 5 for the previous configured total_shares = 100.

Binary Indicator Variable \(t\) for \(\sum_i s_i = 100\)

\(\frac{\sum_{i < \text{taxed_period}} s_i}{\sum_i s_i}\)	\(\sum_{i < \text{taxed_period}} s_i\)	\(\pmb{t}\)	\(\frac{\sum_{i < \text{taxed_period}} s_i}{\sum_i s_i} \le \pmb{t} \le \sum_{i < \text{taxed_period}} s_i\)
0	0	\(\pmb{0}\)	\(0 = \pmb{0} = 0\)
\(\frac{1}{100}\)	1	\(\pmb{1}\)	\(\frac{1}{100} < \pmb{1} = 1\)
\(\frac{5}{100}\)	5	\(\pmb{1}\)	\(\frac{5}{100} < \pmb{1} < 5\)

Add these two constraints to the previously created CQM:

>>> cqm.add_constraint(t - sum(shares[:taxed_period]) <= 0, label="Tax part 1")
'Tax part 1'
>>> cqm.add_constraint(1/total_shares*sum(shares[:taxed_period]) - t <= 0, label="Tax part 2")
'Tax part 2'

Submit the CQM to the selected solver. For one particular execution, with a maximum allowed runtime of a minute, the CQM hybrid sampler returned 50 samples, out of which 33 were solutions that met all the constraints:

>>> sampleset = sampler.sample_cqm(cqm,
...                                time_limit=60,
...                                label="SDK Examples - Stock-Selling Strategy")  
>>> print("{} feasible solutions of {}.".format(
...       sampleset.record.is_feasible.sum(), len(sampleset)))   
33 feasible solutions of 50.

Parse and print the best feasible solution:

>>> r, s, best = parse_best(sampleset)                  
>>> income = sum(r) - best.sample['t']*tax_payment      
>>> print("Post-tax income of {} found for daily sales of: \n{}".format(income, s))     
Post-tax income of 9283.0 found for daily sales of:
[0.0, 0.0, 0.0, 13.0, 14.0, 14.0, 14.0, 16.0, 15.0, 14.0]

Notice that the existence of this tax, though avoided in the sales strategy found above, has reduced your income by a little less than the tax fee (the maximum income if you had paid the tax would be 9275). If the tax is slightly reduced, it is more profitable to sell during the taxation period and pay the tax:

>>> tax_payment = 220
>>> cqm.set_objective(tax_payment*t - sum(revenue))
>>> sampleset = sampler.sample_cqm(cqm,
...                                time_limit=60,
...                                label="SDK Examples - Stock-Selling Strategy")  
>>> r, s, best = parse_best(sampleset)                        
>>> income = sum(r) - best.sample['t']*tax_payment            
>>> print("Post-tax income of {} found for daily sales of: \n{}".format(income, s))     
Post-tax income of 9276.0 found for daily sales of:
[10.0, 10.0, 10.0, 11.0, 9.0, 10.0, 12.0, 9.0, 10.0, 9.0]