Price and inventory optimization

In a previous post I described how one can implement pricing optimization and inventory control for a fashion retail business via mathematical programming. The mathematical program in the scenario allows the users to plan prices such that both the profit is maximized and the left-over stock is minimized. In this post I now present the corresponding model and its implementation in Python/PuLP.

Exemplary problem description

A pricing manager of a retail business wants to plan prices for the next week while considering both profit and inventory over the next 4 weeks.

In this simplified example there are only three articles: shirt, jeans and socks, and one store to handle. The plan covers 4 weeks, of which the first one, i.e. the next one at the time of planning, is going to be actually used.

There are therefore 3 articles x 4 weeks = 12 price points to decide.

Conceptual model description

I show here two models.

  1. a “natural”/”direct” greybox non-linear formulation that translates business requirements directly in mathematical formulas using expressive but complicating equations, e.g. involving functions that are non-linear, non-differentiable or “blackbox”, i.e. not directly representable as equations
  2. a technical whitebox mixed-integer linear reformulation where the complicating equations in the non-linear formulation are approximated using binary variables to yield an equivalent but fully-linear and transparent model.

Usually, in practice, linear models are preferred to more complex ones, even if they could require additional effort to write, because the algorithms for linear models tend to be much more stable and efficient than ones for the alternatives.

Non-linear model description

Sets:

  • T: set of weeks 0..3
  • A: set of articles on sale {“socks”, “jeans”, “shirts”}

Data for a \in A, t \in T:

  • {Q}_{at}(p): demand function for price p
  • L_{a}: initial stock available
  • c_a: cost
  • \underline{p}_a, \bar{p}_a: minimum and maximum price allowed

Variables, for a \in A, t \in T:

  • {S_{at}}: sold items
  • {l_{at}}: stock left at the end of the week
  • {p_{at}}: price

Constraints:

  • C1: prices are within the allowed bounds
    \underline{p}_a \le p_{at} \le \bar{p}_a  \forall a\in A, t\in T
  • C2: stock flows: last week’s stock is either sold or goes into the this week’s stock
    l_{a(t-1)} = S_{at} + l_{at} \quad \forall a \in A, t \in T
    where l_{a(-1)} = L_a
  • C3: every week sell all the stock available until demand is satisfied.
    In other words, the amount of items sold equals the demand if there’s enough stock or all the stock available otherwise, i.e. it is the minimum between the demand and the available stock
    S_{at} = \min({Q}_{at}(p_{at}), l_{a(t-1)}) \quad \forall a \in A, t \in T

Objectives:

  • O1: mazimize profit
    \max \sum_{a\in A, t\in T} ({p_{at}}-c_a) {S_{at}}
  • O2: minimize left-over stock
    \min \sum_{a\in A} {l_{a\bar{t}}}
    with \bar{t}=\max T=3

Linear model reformulation

The non-linear model has the following complicating elements:

  • product between price and sales variables in profit definition
  • constraint C3, where the following appear:
    • a max expression
    • a demand function, possibly a black-box ML model

In the next section I will show how to simplify both elements.

Linearizing profit and demand function

Price discretization and uniform discount notation

The price range \underline{p} \ldots \bar{p} of each article is discretized , i.e. partitioned in n equidistant prices p_1, p_2\dots p_n such that p_i=p_{i-1} + \delta_p according to step-size \delta_p.

For example, prices in the range between 30 and 50 € can be discretized with a 5€ step, yielding 5 different prices: 30, 35, 40, 45, 50.

More precisely, to allow a uniform and interpretable notation, price steps are represented across different articles using a “uniform discount notation” where the price of an article is represented as a “discount” from its base price \bar{p}.

E.g. socks and shirts could have a base price of 15€ and 80€ respectively and the actual price planned for a week could be 10% discount for socks and 20% for shirts, meaning the socks would be sold at 13.5€ and shirts at 64€ respectively.

The notation allows to evaluate the prices easily, as “discounts” represent the amount of profit margin foregone in a given context, e.g. on the sale each article or, in aggregate, for a category or a month.

In this example I use 10 5% discount steps from 0% (base price) to 50%.

Reformulation with discretized prices

Then for each article a and week t:

  • the demand function Q_{at}(p) is replaced in the model with the constants q_{ati}=Q_{at}(p_i) for i \in 1..n, computed querying the forecast at each price point i.
  • the price variable {p_{at}} is replaced by n binary variables {x_{ati}}, one for each price step, such that {x_{ati}}=1 if price p_{ati} is chosen.
  • for each price step a new “price-sale” variable {s_{ati}} is defined which represents the amount sold at that price

The following constraints are also added to the model for each article and week

  • CL1 choose only one of the allowed discrete prices
    \sum_{i\in I} x_{ati} = 1 \quad \forall a\in A, t\in T
  • CL2 reformulates constraint C3 using price-sale and price-choice variables
    {s_{ati}} \le q_{ati} {x_{ati}}
    {S_{at}} = \sum_{i\in I} {s_{ati}}
    {S_{at}} = \min(\sum_{i\in I} q_{ati} {x_{ati}}, {l_{a(t-1}})
    Finally, profit objective can be rewritten as a linear function
    \max \sum_{i\in I} (p_{ati} - c_a) {s_{ati}}

Linearizing “min” operation with big-M formulation

Linearizing the “min” operation is a well-known “trick” in mathematical programming called “Big-M” reformulation.

Consider the constraint
{S_{at}} = \min(\sum_{i\in I} q_{ati}{x_{ati}}, {l_{a(t-1)}})

The idea is add a binary variable {y_{at}} that is 1 if the sold items {S_{at}} are equal to the first argument of the min function and zero otherwise.
In business terms, the flag {y_{at}} is 1 if there’s enough stock to satisfy the demand at the current price, meaning {S_{at}}=\sum_{i\in I} q_{ati}{x_{ati}}, and zero otherwise, meaning {S_{at}}={l_{at}}, i.e. all the available stock is sold.

I then introduce the constraints
{S_{at}} \ge \sum_{i\in I} q_{ati}{x_{ati}} - (1-{y_{at}}) M^1_{at} \quad (*)
{S_{at}} \ge {l_{a(t-1)}} - {y_{at}} M^2_{at}  \quad (**)
where M^1 and M^2 are constants “large enough” that the rest of the right-hand side of the inequality becomes zero or negative when {y_{at}} is 0 and 1 respectively , making the corresponding constraint ineffective.

For example, when {y_{at}}=0 constraint (*) should not have effect, hence M_{at}^1 > \sum_{i\in I}q_{ati}{x_{ati}} for any possible value of the variables {x_{ati}}.

For this example I set:
M^1_{at} = \max_{i \in } q_{ati}
as demand cannot be higher than the maximum demand, and
M^2_{at} = L_{a}
as no stock can be higher than the stock available at the beginning (as there’s no replenishment in the model).

The 2 sets of “big-M” constraints together with the other constraints in CL2 guarantee that {S_{at}} is indeed equal to the minimum of current demand at the current price \sum_{i\in I} q_{ati}{x_{ati}} or to the available stock l_{a(t-1)}.

Python price and inventory optimization

import pandas as pd
import numpy as np
from pulp import *

from typing import NamedTuple, Dict, Any, Tuple
from itertools import product

Model = NamedTuple(
    "Model",
    (
        ("model", LpProblem),  # PuLP model
        ("vars", Dict[str, Dict[Any, LpVariable]]),  # problem variables indexed by name
        (
            "objs",
            Dict[str, LpAffineExpression],
        ),  # objectives indexed by name
    ),
)

def create_model(
    articles_df: pd.DataFrame,
    initial_stock_df: pd.DataFrame,
    demand_df: pd.DataFrame,
) -> Model:
    model = LpProblem("Pricing", LpMaximize)

    # Sets & Parameters
    Time = demand_df["week"].unique()
    DiscountsLevels = dict(enumerate(np.sort(demand_df["discount"].unique())))
    Articles = articles_df["article"]

    demand = demand_df.set_index(["article", "week", "discount_level"])["demand"]
    initial_stock = initial_stock_df.set_index(["article"])["initial_stock"]

    profit_coef = get_profit_revenue_coefficients(articles_df, demand_df)
    profit_coef = profit_coef.set_index(["article", "discount_level"])["profit"]

    # Variables
    discounts = LpVariable.dicts(
        "x", product(Articles, Time, DiscountsLevels.keys()), cat=LpBinary
    )
    stock = LpVariable.dicts("l", product(Articles, Time), lowBound=0)
    sales = LpVariable.dicts("S", product(Articles, Time), lowBound=0)
    sales_discounts = LpVariable.dicts(
        "s", product(Articles, Time, DiscountsLevels), lowBound=0
    )
    stock_dem_sel = LpVariable.dicts("y", product(Articles, Time), cat=LpBinary)

    profit = LpVariable.dicts("prof", product(Articles, Time))

    # Constraints
    for (a, t) in product(Articles, Time):
        model.addConstraint(
            lpSum(discounts[a, t, d] for d in DiscountsLevels) == 1,
            f"select_discount_{a}_{t}",
        )

    for (a, t, d) in product(Articles, Time, DiscountsLevels):
        model.addConstraint(
            sales_discounts[a, t, d] <= demand.loc[a, t, d] * discounts[a, t, d],
            f"sales_demand_{a}_{t}_{d}",
        )

    for (a, t) in product(Articles, Time):
        model.addConstraint(
            sales[a, t] == lpSum(sales_discounts[a, t, d] for d in DiscountsLevels),
            f"def_sales_{a}_{t}",
        )

    for (a, t) in product(Articles, Time):
        model.addConstraint(
            stock[a, t]
            == (initial_stock.loc[a] if t == 0 else stock[a, t - 1]) - sales[a, t],
            f"stock_flow_{a}_{t}",
        )

    # big-M constraint for demand selection constraint
    max_demands = demand.groupby(["article", "week"]).max()
    # small epsilon for big M constants
    eps = 0.5
    for (a, t) in product(Articles, Time):
        model.addConstraint(
            sales[a, t]
            >= lpSum(demand.loc[a, t, d] * discounts[a, t, d] for d in DiscountsLevels)
            - (max_demands.loc[a, t] + eps) * (1 - stock_dem_sel[a, t]),
            f"sales_ge_dem_{a}_{t}",
        )
    for (a, t) in product(Articles, Time):
        model.addConstraint(
            sales[a, t]
            >= (initial_stock.loc[a] if t == 0 else stock[a, t - 1])
            - (initial_stock.loc[a] + eps) * stock_dem_sel[a, t],
            f"dem_ge_sales_{a}_{t}",
        )

    # profit definition
    for (a, t) in product(Articles, Time):
        model.addConstraint(
            profit[a, t]
            == lpSum(
                profit_coef.loc[a, d] * sales_discounts[a, t, d]
                for d in DiscountsLevels
            ),
            f"def_profit_{a}_{t}",
        )

    # Objectives
    profit_function = lpSum(profit[a, t] for (a, t) in product(Articles, Time))

    t_max = max(Time)
    left_stock = lpSum(stock[a, t_max] for a in Articles)

    # Setting default objective
    model.setObjective(profit_function)

    return Model(
        model=model,
        vars=dict(
            discounts=discounts,
            stock=stock,
            sales=sales,
            sales_discounts=sales_discounts,
            stock_dem_sel=stock_dem_sel,
            profit=profit
        ),
        objs=dict(profit=profit_function, left_stock=left_stock),
    )


def get_profit_revenue_coefficients(
    articles: pd.DataFrame, demand: pd.DataFrame
) -> pd.DataFrame:
    discount_levels = pd.DataFrame(
        [(i, d) for i, d in enumerate(np.sort(demand["discount"].unique()))],
        columns=["discount_level", "discount"],
    )

    discounted_prices = articles[["article", "base_price", "cost"]].join(
        discount_levels, how="cross"
    )
    discounted_prices["price"] = discounted_prices["base_price"] * (
        1 - discounted_prices["discount"]
    )
    discounted_prices["profit"] = discounted_prices["price"] - discounted_prices["cost"]

    return discounted_prices[["article", "discount_level", "profit"]].copy()

Price and inventory optimization data

The tables listed data summarize the data used for executing the optimization run, i.e. for parametrizing the price and inventory optimization model.

Articles base prices

articlebase_pricecost
socks105
jeans2515
shirts4025

Initial stock

articleinitial_stock
socks290
jeans250
shirts280

Demand curve

articleweekpricediscountdiscount_leveldemand
socks010.00.00044
socks09.50.05148
socks09.00.10252
socks08.50.15357
socks08.00.20461
shirts326.00.35782
shirts324.00.40887
shirts322.00.45995
shirts320.00.501097

Profit maximization model in Python

The first step or Scenario of the optimization process is to optimize for profit, which is the default objective of the model. Hence, first I create the basic model

model = create_model(article_df, initial_stock_df, demand_df)

then call solve() on the PuLP model

model.model.solve()
Welcome to the CBC MILP Solver 
Version: 2.10.3 
Build Date: Dec 15 2019 

command line - /home/ataverna/pyvenv/pricing-scda/lib/python3.10/site-packages/pulp/apis/../solverdir/cbc/linux/64/cbc /tmp/d0a41743ad5b4cad8606ce0c4a1d2841-pulp.mps max timeMode elapsed branch printingOptions all solution /tmp/d0a41743ad5b4cad8606ce0c4a1d2841-pulp.sol (default strategy 1)
At line 2 NAME          MODEL
At line 3 ROWS
At line 257 COLUMNS
At line 1840 RHS
At line 2093 BOUNDS
At line 2298 ENDATA
Problem MODEL has 252 rows, 408 columns and 1186 elements
Coin0008I MODEL read with 0 errors
Option for timeMode changed from cpu to elapsed
Continuous objective value is 5228.77 - 0.00 seconds
Cgl0004I processed model has 228 rows, 384 columns (192 integer (192 of which binary)) and 984 elements
Cbc0038I Initial state - 12 integers unsatisfied sum - 3.78927
Cbc0038I Pass   1: suminf.    1.64775 (5) obj. -5228.77 iterations 119
Cbc0038I Solution found of -5228.77
Cbc0038I Relaxing continuous gives -5228.77
Cbc0038I Before mini branch and bound, 180 integers at bound fixed and 168 continuous
Cbc0038I Mini branch and bound did not improve solution (0.02 seconds)
Cbc0038I After 0.02 seconds - Feasibility pump exiting with objective of -5228.77 - took 0.00 seconds
Cbc0012I Integer solution of -5228.7666 found by feasibility pump after 0 iterations and 0 nodes (0.02 seconds)
Cbc0001I Search completed - best objective -5228.766562804411, took 0 iterations and 0 nodes (0.02 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Cuts at root node changed objective from -5228.77 to -5228.77
Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Gomory was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Knapsack was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Clique was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
FlowCover was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
ZeroHalf was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

Result - Optimal solution found

Objective value:                5228.76656280
Enumerated nodes:               0
Total iterations:               0
Time (CPU seconds):             0.02
Time (Wallclock seconds):       0.03

Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.03   (Wallclock seconds):       0.03

1

The profit-optimal solution has then the following objectives:

  • total profit: 5229 €
  • stock left: 226 units

Inventory optimization in Python

The second step/scenario of the optimization process consists of minimizing the left-over stock while keeping the overall profit “close” to the optimum.
More specifically, I allow a 2.75% loss at most from the theoretical (i.e. extremely unlikely to be obtained in practice) optimal profit computed in the first scenario to provide the solver enough slack to find an effective stock-minimizing solution in reasonable time.

Given the simplicity of the current problem, an even smaller slack could have been allowed without worsening the left-stock reduction.

In the code I then add the constraint that the profit must be within 100%-2.75% = 97.5% of the optimal profit

model.model.addConstraint(model.objs["profit"]>= 0.975 * model.objs["profit"].value())

, set the left-over stock as the new objective to minimize

model.model.setObjective(model.objs["left_stock"])
model.model.sense = LpMinimize

and finally call solve() on the PuLP model

model.model.solve()
Welcome to the CBC MILP Solver 
Version: 2.10.3 
Build Date: Dec 15 2019 

command line - /home/ataverna/pyvenv/pricing-scda/lib/python3.10/site-packages/pulp/apis/../solverdir/cbc/linux/64/cbc /tmp/544e8a41484d4d4e9d8a9fc3f5ed4304-pulp.mps timeMode elapsed branch printingOptions all solution /tmp/544e8a41484d4d4e9d8a9fc3f5ed4304-pulp.sol (default strategy 1)
At line 2 NAME          MODEL
At line 3 ROWS
At line 258 COLUMNS
At line 1844 RHS
At line 2098 BOUNDS
At line 2303 ENDATA
Problem MODEL has 253 rows, 408 columns and 1198 elements
Coin0008I MODEL read with 0 errors
Option for timeMode changed from cpu to elapsed
Continuous objective value is 111.636 - 0.00 seconds
Cgl0004I processed model has 229 rows, 384 columns (192 integer (192 of which binary)) and 1156 elements
Cbc0038I Initial state - 14 integers unsatisfied sum - 3.76888
Cbc0038I Pass   1: suminf.    1.58139 (8) obj. 112.209 iterations 43
Cbc0038I Pass   2: suminf.    0.00000 (0) obj. 133.436 iterations 152
Cbc0038I Solution found of 133.436
Cbc0038I Relaxing continuous gives 133.436
Cbc0038I Before mini branch and bound, 176 integers at bound fixed and 166 continuous
Cbc0038I Full problem 229 rows 384 columns, reduced to 11 rows 10 columns
Cbc0038I Mini branch and bound improved solution from 133.436 to 114.944 (0.03 seconds)
Cbc0038I Freeing continuous variables gives a solution of 114.944
Cbc0038I Round again with cutoff of 114.613
Cbc0038I Reduced cost fixing fixed 145 variables on major pass 2
Cbc0038I Pass   3: suminf.    1.61787 (8) obj. 111.763 iterations 4
Cbc0038I Pass   4: suminf.    0.66518 (3) obj. 114.613 iterations 104
Cbc0038I Pass   5: suminf.    0.94754 (2) obj. 113.247 iterations 43
Cbc0038I Pass   6: suminf.    0.94754 (2) obj. 113.247 iterations 0
Cbc0038I Pass   7: suminf.    1.58902 (6) obj. 114.613 iterations 85
Cbc0038I Pass   8: suminf.    1.26499 (4) obj. 113.294 iterations 44
Cbc0038I Pass   9: suminf.    0.42748 (4) obj. 114.613 iterations 106
Cbc0038I Pass  10: suminf.    0.68311 (3) obj. 114.613 iterations 85
Cbc0038I Pass  11: suminf.    1.85027 (11) obj. 114.613 iterations 17
Cbc0038I Pass  12: suminf.    1.10259 (8) obj. 114.613 iterations 23
Cbc0038I Pass  13: suminf.    0.21183 (2) obj. 114.027 iterations 59
Cbc0038I Pass  14: suminf.    0.05738 (3) obj. 114.613 iterations 59
Cbc0038I Pass  15: suminf.    1.26492 (5) obj. 114.198 iterations 53
Cbc0038I Pass  16: suminf.    0.37675 (4) obj. 114.613 iterations 25
Cbc0038I Pass  17: suminf.    1.31377 (6) obj. 114.198 iterations 35
Cbc0038I Pass  18: suminf.    0.51615 (5) obj. 114.613 iterations 37
Cbc0038I Pass  19: suminf.    0.90693 (5) obj. 114.198 iterations 26
Cbc0038I Pass  20: suminf.    0.69802 (6) obj. 114.613 iterations 32
Cbc0038I Pass  21: suminf.    0.21183 (2) obj. 114.027 iterations 57
Cbc0038I Pass  22: suminf.    0.05738 (3) obj. 114.613 iterations 59
Cbc0038I Pass  23: suminf.    0.62276 (3) obj. 114.325 iterations 39
Cbc0038I Pass  24: suminf.    0.05738 (3) obj. 114.613 iterations 45
Cbc0038I Pass  25: suminf.    0.62844 (6) obj. 114.613 iterations 13
Cbc0038I Pass  26: suminf.    0.49877 (5) obj. 114.613 iterations 11
Cbc0038I Pass  27: suminf.    1.64977 (6) obj. 114.027 iterations 57
Cbc0038I Pass  28: suminf.    1.08784 (7) obj. 114.613 iterations 33
Cbc0038I Pass  29: suminf.    0.21183 (2) obj. 114.027 iterations 58
Cbc0038I Pass  30: suminf.    1.58568 (5) obj. 112.799 iterations 5
Cbc0038I Pass  31: suminf.    1.11549 (3) obj. 112.799 iterations 2
Cbc0038I Pass  32: suminf.    0.37450 (3) obj. 114.613 iterations 66
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 157 integers at bound fixed and 151 continuous
Cbc0038I Full problem 229 rows 384 columns, reduced to 43 rows 51 columns
Cbc0038I Mini branch and bound improved solution from 114.944 to 113.6 (0.09 seconds)
Cbc0038I Freeing continuous variables gives a solution of 113.6
Cbc0038I Round again with cutoff of 113.207
Cbc0038I Reduced cost fixing fixed 149 variables on major pass 3
Cbc0038I Pass  32: suminf.    1.66426 (8) obj. 111.763 iterations 2
Cbc0038I Pass  33: suminf.    0.93358 (3) obj. 113.207 iterations 70
Cbc0038I Pass  34: suminf.    0.97581 (2) obj. 112.863 iterations 54
Cbc0038I Pass  35: suminf.    0.97581 (2) obj. 112.863 iterations 0
Cbc0038I Pass  36: suminf.    1.94824 (5) obj. 113.207 iterations 27
Cbc0038I Pass  37: suminf.    1.47157 (4) obj. 113.207 iterations 7
Cbc0038I Pass  38: suminf.    0.17932 (4) obj. 113.207 iterations 29
Cbc0038I Pass  39: suminf.    0.49343 (4) obj. 113.207 iterations 93
Cbc0038I Pass  40: suminf.    0.28741 (4) obj. 113.207 iterations 52
Cbc0038I Pass  41: suminf.    1.71595 (4) obj. 113.207 iterations 50
Cbc0038I Pass  42: suminf.    1.15551 (4) obj. 113.207 iterations 85
Cbc0038I Pass  43: suminf.    1.00905 (4) obj. 113.207 iterations 50
Cbc0038I Pass  44: suminf.    0.74832 (3) obj. 113.207 iterations 73
Cbc0038I Pass  45: suminf.    2.20863 (7) obj. 113.207 iterations 47
Cbc0038I Pass  46: suminf.    0.79703 (5) obj. 113.207 iterations 29
Cbc0038I Pass  47: suminf.    0.29820 (2) obj. 112.799 iterations 49
Cbc0038I Pass  48: suminf.    0.15360 (3) obj. 113.207 iterations 70
Cbc0038I Pass  49: suminf.    1.11561 (6) obj. 113.207 iterations 3
Cbc0038I Pass  50: suminf.    0.15360 (3) obj. 113.207 iterations 3
Cbc0038I Pass  51: suminf.    1.44008 (5) obj. 112.496 iterations 48
Cbc0038I Pass  52: suminf.    0.59760 (5) obj. 113.207 iterations 46
Cbc0038I Pass  53: suminf.    1.24528 (6) obj. 113.207 iterations 47
Cbc0038I Pass  54: suminf.    0.85442 (6) obj. 113.207 iterations 16
Cbc0038I Pass  55: suminf.    0.34233 (2) obj. 112.863 iterations 57
Cbc0038I Pass  56: suminf.    0.25171 (3) obj. 113.207 iterations 57
Cbc0038I Pass  57: suminf.    1.77001 (5) obj. 113.207 iterations 27
Cbc0038I Pass  58: suminf.    0.56079 (4) obj. 113.207 iterations 28
Cbc0038I Pass  59: suminf.    0.29820 (2) obj. 112.799 iterations 48
Cbc0038I Pass  60: suminf.    0.15360 (3) obj. 113.207 iterations 65
Cbc0038I Pass  61: suminf.    1.33300 (6) obj. 113.207 iterations 28
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 162 integers at bound fixed and 154 continuous
Cbc0038I Full problem 229 rows 384 columns, reduced to 34 rows 43 columns
Cbc0038I Mini branch and bound improved solution from 113.6 to 112.116 (0.13 seconds)
Cbc0038I Freeing continuous variables gives a solution of 112.116
Cbc0038I Round again with cutoff of 111.972
Cbc0038I Reduced cost fixing fixed 154 variables on major pass 4
Cbc0038I Pass  61: suminf.    1.72999 (8) obj. 111.636 iterations 4
Cbc0038I Pass  62: suminf.    0.66893 (3) obj. 111.972 iterations 86
Cbc0038I Pass  63: suminf.    0.27119 (2) obj. 111.636 iterations 132
Cbc0038I Pass  64: suminf.    0.67335 (4) obj. 111.972 iterations 76
Cbc0038I Pass  65: suminf.    0.37376 (3) obj. 111.636 iterations 126
Cbc0038I Pass  66: suminf.    1.41352 (6) obj. 111.972 iterations 46
Cbc0038I Pass  67: suminf.    0.69305 (5) obj. 111.972 iterations 67
Cbc0038I Pass  68: suminf.    0.38467 (4) obj. 111.972 iterations 50
Cbc0038I Pass  69: suminf.    0.25329 (3) obj. 111.972 iterations 110
Cbc0038I Pass  70: suminf.    0.79158 (5) obj. 111.972 iterations 78
Cbc0038I Pass  71: suminf.    0.41506 (3) obj. 111.972 iterations 31
Cbc0038I Pass  72: suminf.    0.05771 (3) obj. 111.972 iterations 85
Cbc0038I Pass  73: suminf.    0.00787 (2) obj. 111.972 iterations 45
Cbc0038I Pass  74: suminf.    1.16702 (5) obj. 111.972 iterations 3
Cbc0038I Pass  75: suminf.    0.00787 (2) obj. 111.972 iterations 3
Cbc0038I Pass  76: suminf.    0.30593 (2) obj. 111.636 iterations 73
Cbc0038I Pass  77: suminf.    0.18519 (3) obj. 111.972 iterations 42
Cbc0038I Pass  78: suminf.    0.35284 (4) obj. 111.972 iterations 49
Cbc0038I Pass  79: suminf.    1.32921 (6) obj. 111.779 iterations 51
Cbc0038I Pass  80: suminf.    0.68945 (5) obj. 111.972 iterations 42
Cbc0038I Pass  81: suminf.    1.09325 (4) obj. 111.972 iterations 110
Cbc0038I Pass  82: suminf.    0.68945 (5) obj. 111.972 iterations 92
Cbc0038I Pass  83: suminf.    1.13903 (5) obj. 111.636 iterations 32
Cbc0038I Pass  84: suminf.    1.22882 (5) obj. 111.636 iterations 5
Cbc0038I Pass  85: suminf.    0.99144 (6) obj. 111.972 iterations 39
Cbc0038I Pass  86: suminf.    1.78307 (7) obj. 111.972 iterations 51
Cbc0038I Pass  87: suminf.    0.99144 (6) obj. 111.972 iterations 108
Cbc0038I Pass  88: suminf.    0.35284 (4) obj. 111.972 iterations 50
Cbc0038I Pass  89: suminf.    0.18519 (3) obj. 111.972 iterations 114
Cbc0038I Pass  90: suminf.    1.90103 (7) obj. 111.972 iterations 53
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 167 integers at bound fixed and 159 continuous
Cbc0038I Full problem 229 rows 384 columns, reduced to 27 rows 31 columns
Cbc0038I Mini branch and bound did not improve solution (0.18 seconds)
Cbc0038I After 0.18 seconds - Feasibility pump exiting with objective of 112.116 - took 0.15 seconds
Cbc0012I Integer solution of 112.11639 found by feasibility pump after 0 iterations and 0 nodes (0.19 seconds)
Cbc0038I Full problem 229 rows 384 columns, reduced to 15 rows 14 columns
Cbc0031I 4 added rows had average density of 7.75
Cbc0013I At root node, 5 cuts changed objective from 111.63555 to 112.11639 in 2 passes
Cbc0014I Cut generator 0 (Probing) - 10 row cuts average 2.6 elements, 8 column cuts (8 active)  in 0.001 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 2 (Knapsack) - 2 row cuts average 7.0 elements, 0 column cuts (0 active)  in 0.001 seconds - new frequency is 1
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 1 row cuts average 7.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is 1
Cbc0014I Cut generator 5 (FlowCover) - 1 row cuts average 3.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is 1
Cbc0014I Cut generator 6 (TwoMirCuts) - 11 row cuts average 5.5 elements, 0 column cuts (0 active)  in 0.001 seconds - new frequency is -100
Cbc0001I Search completed - best objective 112.11638707256, took 22 iterations and 0 nodes (0.21 seconds)
Cbc0035I Maximum depth 0, 154 variables fixed on reduced cost
Cuts at root node changed objective from 111.636 to 112.116
Probing was tried 2 times and created 18 cuts of which 0 were active after adding rounds of cuts (0.001 seconds)
Gomory was tried 2 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Knapsack was tried 2 times and created 2 cuts of which 0 were active after adding rounds of cuts (0.001 seconds)
Clique was tried 2 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 2 times and created 1 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
FlowCover was tried 2 times and created 1 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 2 times and created 11 cuts of which 0 were active after adding rounds of cuts (0.001 seconds)
ZeroHalf was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

Result - Optimal solution found

Objective value:                112.11638707
Enumerated nodes:               0
Total iterations:               22
Time (CPU seconds):             0.20
Time (Wallclock seconds):       0.22

Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.20   (Wallclock seconds):       0.22

1

The stock-minimizing solution has then:

  • total profit: 5100 €
  • stock left: 112 units

Price and inventory optimization results

The table below summarizes the final results of this optimization project. The objectives are shown for each scenario. The relative change from Scenario 1 to Scenario 2 is reported in the last column.

ObjectivesScenario 1:
max profit
Scenario 2:
max profit/min left stock
change from
Scenario 1 to
Scenario 2 [%]
Total profit [€]52295100-2.5
Stock left [units]226 112-50.4

As described in the previous article, the “multi-objective” approach of optimizing for profit first and then for left-over stock allows to significantly reduce the left-over stock with minimum profit loss.

Both scenarios share the same “core” model, i.e. code implementation. Compared to the first scenario, the second scenario has just a different objective, from profit maximization to left-stock minimization, and an additional constraint to keep the total profit close to the optimal value computed in Scenario 1. Both changes are implemented in a couple of lines of code.

More on price and inventory optimization

If you are interested in inventory optimization and optimal pricing you might want to read some other related SCDA articles. Find the list below.

As this article applies multi-objective optimization you might furthermore also be interested in the following articles:

You May Also Like

Leave a Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.