ERATO感謝祭 SeasonIV 2017.8.3@NII

Large-Scale Price Optimization
via Network FlowShinji Ito, Ryohei Fujimaki

1© NEC Corporation 2017

Our goal: profit maximization by optimizing prices▌What is the best pricing strategy?
Strategy 1: $ 1.3

Strategy 2
Price: $ 1.0

Sales quantity?

2© NEC Corporation 2017Profit?

Our goal: profit maximization by optimizing prices▌What is the best pricing strategy?
Strategy 1: $ 1.3

Strategy 2
Price×: $ 1.0×
Sales quantity

3© NEC Corporation 2017==$ 5.2Profit<$ 6.0Complicated structure in price optimization▌Changing the price of one product affects other’s sales
Sales- Cannibalization:

Demand ofGrowing the sales of
makes the sales ofdown

Demand ofDiscount ofPrice

ProfitProduct 1$1.3  $1.0+200+ $80

Product 2$1.2-100- $120Gross profit

4Quantity© NEC Corporation 2017

- $40

Predictive price optimization and its difficulty▌Recent advanced ML reveals relationship between
prices and sales quantities
Input:
pos data

Price

Price

Sales

Sales

⋯

Day 1

$1.3

$1.022

⋯

Day 2
⋮

$1.2
⋮

$1.0⋮

4⋮2⋮

⋯

Machine learning
Predictive model:

5© NEC Corporation 2017

sales = 𝑓(prices)Predictive price optimization and its difficulty▌Recent advanced ML reveals relationship between
prices and sales quantities
Input:
pos dataPricePriceSales

Sales

⋯

Day 1

$1.3

$1.0

2

2

⋯

Day 2
⋮

$1.2
⋮

$1.0
⋮

4
⋮

2
⋮

⋯

Machine learning
Predictive model:

sales = 𝑓(prices)

Optimization (NP-hard)
Output:optimal prices
6© NEC Corporation 2017

[This work]Our contribution▌Scalable algorithm for price optimization
Based on:
1. Submodularity behind pricing
2. Network flow algorithm
3. Supermodular relaxation

7© NEC Corporation 2017

Our contribution▌Scalable algorithm for price optimization
Based on:
1. Submodularity behind pricing
2. Network flow algorithm
3. Supermodular relaxation
Achieved:- Can deal with thousands of products- High accuracy for real-data problem
8© NEC Corporation 2017

Table of contents
1. Introduction
2. Problem definition
3. Scalable price optimization algorithm
4. Experiments

Objective function of price optimization▌Want to maximize is the gross profit ℓ

Gross profit:𝑀ℓ 𝑝1 , 𝑝2 , … , 𝑝𝑀 = ෍(𝑝𝑖 −𝑐𝑖 )𝑞𝑖𝑖=1
price

product id10

© NEC Corporation 2017

cost sales quantity
Unknown, butpredictable

Predictive model for sales quantity▌Sales quantity 𝑞𝑖 is a function in prices 𝑝𝑖
𝑞1 𝑝, 𝑟 = 𝑓11 𝑝1 + 𝑓12 𝑝2 + ⋯salesquantity

priceprice$$+ 𝑔11 𝑟1 + 𝑔12 𝑟2 + ⋯weathercalendar
Sat▌Use historical data to infer 𝑓𝑖𝑗 , 𝑔𝑖𝑗

Ex: 𝑓𝑖𝑗 𝑝𝑗 = 𝑎𝑖𝑗 𝑝𝑗2 + 𝑏𝑖𝑗 𝑝𝑗 + 𝑐𝑖𝑗 (polynomial model)
𝑓𝑖𝑗 𝑝𝑗 = exp(𝛼𝑖𝑗 𝑝𝑗 + 𝛽𝑖𝑗 ) , (generalized linear model)

11© NEC Corporation 2017

Predictive model for sales quantity▌Sales quantity 𝑞𝑖 is a function in prices 𝑝𝑖
𝑞1 𝑝, 𝑟 = 𝑓11 𝑝1 + 𝑓12 𝑝2 + ⋯sales
quantity

priceprice$$+ 𝑔11 𝑟1 + 𝑔12 𝑟2 + ⋯WeathercalendarSat

𝑓11 : Price elasticity of demand

𝑴 products
1: orange

sales
quantity
2: apple

𝑓12 : Cross price effectsales
quantity・・・

Priceof orange
𝑀: milk
12© NEC Corporation 2017$

Price of apple$

Substitute goods in price optimization▌Many substitute goods in price optimization
𝑞1 𝑝, 𝑟 = 𝑓11 𝑝1 + 𝑓12 𝑝2 + ⋯and: Substitute goods+ 𝑔11 𝑟1 + 𝑔12 𝑟2 + ⋯𝑓12 : Cross price effect⇔defDiscounting applemakes

the sales of orange

down(cannibalization)$13© NEC Corporation 2017

Optimization problem▌Optimization is NP-hard
Gross profit
𝑀Maximizeℓ 𝑝 = ෍(𝑝𝑖 −𝑐𝑖 )𝑞𝑖 (𝑝)𝑖=1…
Subject to𝑝𝑖∈{ 𝑃𝑖1 , 𝑃𝑖2 , … , 𝑃𝑖𝑘 }Discrete price candidates

A commercial solver takes >24[h] for 50 products
14© NEC Corporation 2017

Table of contents
1. Introduction
2. Problem definition
3. Scalable price optimization algorithm
4. Experiments

Our contribution▌Scalable algorithm for price optimization
Based on:
1. Submodularity behind pricing
2. Network flow algorithm3. Supermodular relaxation

16© NEC Corporation 2017

Idea 1: Substitute goods and supermodular▌Connection between substitute goods and submodular

Substitute goods:
Discounting⇒ less sales ofDemand of B

Demand of A
price of A

Theorem [Substitute goods ⇒ supermodular]

If all pairs of products are substitute goods
or independent⇒ ℓ(𝑝) is a supermodular function

17© NEC Corporation 2017

Idea 1: Substitute goods and supermodular▌Connection between substitute goods and submodular

Substitute goods:
Discounting

Demand of B

⇒ less sales ofDemand of A
price of A

Theorem [Substitute goods ⇒ supermodular]

If all pairs of products are substitute goods
or independent⇒ ℓ(𝑝) is a supermodular function
maximized in polynomial time
[Iwata, Fleischer, Fujishige (2001)]
18© NEC Corporation 2017

Two issues in Key idea 1▌If all products are substitute goods or independent,
profit can be maximized in polynomial time19

© NEC Corporation 2017

Two issues in Key idea 1▌If all products are substitute goods or independent,profit can be maximized in polynomial time

▌This approach is still impractical because of two issues
Issue 1: General supermodular maximization is slow
∼ 𝑂(𝑛5 )Issue 2: Substitute goods assumption is too restrictive

20© NEC Corporation 2017

Two issues in Key idea 1▌If all products are substitute goods or independent,
profit can be maximized in polynomial time

▌This approach is still impractical because of two issues
Issue 1: General supermodular maximization is slow
∼ 𝑂(𝑛5 )Resolved by 2. network flow:
𝑂 𝑛2 ∼ 𝑂(𝑛3 )Issue 2: Substitute goods assumption is too restrictive
Resolved by 3. supermodular relaxation
Applicable for non-substitute21© NEC Corporation 2017

Two issues in Key idea 1▌If all products are substitute goods or independent,profit can be maximized in polynomial time▌This approach is still impractical because of two issues
Issue 1: General supermodular maximization is slow
∼ 𝑂(𝑛5 )Resolved by 2. network flow:
𝑂 𝑛2 ∼ 𝑂(𝑛3 )Issue 2: Substitute goods assumption is too restrictive
Resolved by 3. supermodular relaxation
Applicable for non-substitute22© NEC Corporation 2017

Substitute goods price optimization ⇔ Minimum Cut▌Maximizingℓ 𝑝 ⇔ Finding minimum s-t cut:solved efficiently by network flow
[Ford, Fulkerson (1956)], [Orlin (2013)]

Graph 𝐺s23

© NEC Corporation 2017t

Substitute goods price optimization ⇔ Minimum Cut▌Maximizingℓ 𝑝 ⇔ Finding minimum s-t cut:solved efficiently by network flow

𝑝1 =Graph 𝐺s24

© NEC Corporation 2017t

Substitute goods price optimization ⇔ Minimum Cut▌Maximizingℓ 𝑝 ⇔ Finding minimum s-t cut:solved efficiently by network flow

𝑝1 =𝑝2 =25© NEC Corporation 2017

Graph 𝐺st

Substitute goods price optimization ⇔ Minimum Cut▌Maximizingℓ 𝑝 ⇔ Finding minimum s-t cut:solved efficiently by network flow

𝑝1 =

𝑝2 =𝑝3 =26© NEC Corporation 2017

Graph 𝐺st

Substitute goods price optimization ⇔ Minimum Cut▌Maximizingℓ 𝑝 ⇔ Finding minimum s-t cut:solved efficiently by network flowℓ 𝑝 = constant − (capacity of st-cut of graph 𝐺)

𝑝1 =

𝑝2 =
𝑝3 =

27

© NEC Corporation 2017

Graph 𝐺st

Two issues in Key idea 1▌If all products are substitute goods or independent,
profit can be maximized in polynomial time

▌This approach is still impractical because of two issues
Issue 1: General supermodular maximization is slow
𝑂(𝑛5 )
Resolved by 2. network flow:
𝑂 𝑛2 ∼ 𝑂(𝑛3 )Issue 2: Substitute goods assumption is too restrictive
Resolved by 3. supermodular relaxation
Applicable for non-substitute28© NEC Corporation 2017

Non-SGP case: supermodular relaxation▌∃ non-substitute goods⇒ approximate ℓ by supemodular functionℓ 𝑝 = ℓ− 𝑝 + ℓ+ (𝑝)supermodularsubmodularℓ𝑝2ℓ+ (𝑝)ℎΓ (𝑝)≤ ℓ− 𝑝 + ℎΓ (𝑝)modularsupermodular⇒ maximized via network flow29© NEC Corporation 2017𝑝1

Non-SGP case: supermodular relaxation▌Many possibilities of relaxation function
Better relaxation is chosen automaticallysupermodular
supermodular
Relaxation
changes depending on Γ ∈ 0,1 𝑛×𝑛ℓ

Γ𝑖𝑗 = 0

Γ𝑖𝑗 = 0.7

Γ𝑖𝑗 = 1𝑝2

𝑝2

𝑝2ℓ

𝑝130

© NEC Corporation 2017

ℓ𝑝1ℓ+ (𝑝)ℎΓ (𝑝)

𝑝1

Simulation experiments▌Proposed approximation algorithm:
fast and give solution with only <1% loss

Existing methods

Past data
Computing Time
Achieved Profit
Upper bound1.40 M

Proposed

QPBO

Others36 [s]

964 [s]> 1day1.88 M

1.25 M

Nan

1.90 M

1.89 M

Nan- Real-world retail data* of a supermarket*provided by KSP-SP Co., LTD.

- 1000 products- Compared with SDP, QPBO, QPBOI [Rother et.al (2007)]
31© NEC Corporation 2017

Conclusion▌Constructed a scalable price optimization algorithm by- Associating substitute goods
with supermodularity

Demand of B

Demand of A
price of A

- Using network flow andsupermodular relaxation▌Future work: how to cope with the errors in objective?
e.g., by robust optimization?
32© NEC Corporation 2017