Syntha Lab RU

Optimization of range and allocation: knapsack by budget and shelf, marginal stock allocation, the transport problem

Three problems that purchasing and logistics solve by eye or by rules: which models to take under a limited budget and shelf (knapsack), how to divide scarce stock between stores (marginal analysis) and which warehouse should ship to which store (the transport problem). The decision: replace the rule of thumb by a calculation and see the price of constraints.

Math and analytics Brand and retail Verified: 2026-11-14

Open interactively →

Why this document

The buyer, logistician and planner read this when resources are short: budget, shelf space and stock are all limited. The knapsack answers which models to take when budget and space are finite, rather than just picking the best by revenue. Marginal analysis splits scarce stock between stores so that each next unit goes where it earns more. The transport problem chooses which warehouse ships to which store. The rule of splitting in proportion to past sales performs worse than the calculation.

At a glance

What is this document and why is it needed?
Three problems that purchasing and logistics solve by eye or by rules: which models to take under a limited budget and shelf (knapsack), how to divide scarce stock between stores (marginal analysis) and which warehouse should ship to which store (the transport problem). The decision: replace the rule of thumb by a calculation and see the price of constraints.
Who owns the document and how often is it rebuilt?
Purchase and allocation planner, supply chain analyst; the calculation runs before season purchasing, at every allocation of a scarce lot and when tariffs change; read by purchasing, logistics and finance.
What mistakes are the most common?
Models are chosen by profit ranking ignoring shelf and budget → the set does not fit or leaves budget unused → compute the knapsack with both constraints. A lot is divided proportionally to past sales → unstable stores get too much while predictable ones go short → allocate by the probability of selling the next unit. The optimum is taken for the truth with inaccurate profit estimates → a “fragile” set → check stability under shifted estimates and keep a reserve list of models.

For whom

Brand
A brand selects line models under the production budget and factory slots, divides output between partners and channels and chooses the shipping warehouse.
Retail
A retailer selects a range under the purchasing budget (OTB) and shelf, allocates an incoming lot across stores and plans moves from the warehouse and between stores.

What it consists of

What optimization is and why purchasing needs it

  • Optimization is a choice of decision values (which models to take, how much to ship to a store, by which route) so that an objective (profit, sales, cost) is the best under constraints (budget, shelf, stock, warehouse capacity). Rules like “take the most profitable” or “divide proportionally to sales” are special heuristics with no quality guarantee.
  • Each problem is written as a triple: decision variables, the objective and constraints. Figures in the objective are estimates (expected model profit, average store demand), so the optimum is exact relative to the model, not to reality; the result is checked for stability against changes in the estimates.
  • Constraints have a price: the shadow price shows how much the objective rises when a constraint is relaxed by one unit (one more rouble of budget, one more facing on the shelf). This is the main practical result: it answers where it is most profitable to add a resource.

Knapsack: range under purchase budget and shelf

  • Given 24 candidate models: each has a purchase c_i (RUB thousand), expected season profit v_i and shelf use w_i (facings). The task is to choose the set with the maximum total profit under a budget of RUB 4 million and a shelf of 28 facings. The candidates total RUB 5.81 million and 61 facings, so the constraints are active.
  • Greedy rules: by profit per rouble of purchase gives RUB 1.499 million, by model profit 2,101, by profit per sum of budget and shelf shares 2,150. The exact dynamic programming solution is RUB 2.15 million on 13 models. The best greedy rule gives 100% of the optimum, the worst 70%: a rule chosen without checking can lose a noticeable part of the result.
  • Shadow prices: an extra RUB 500 thousand of budget adds RUB 106 thousand of profit (0.21 per rouble), an extra facing RUB 27 thousand. With a shelf of 28, money above RUB 5 million adds nothing: the shelf limits, not the budget.
  • The model is extended by range conditions: a minimum number of models in each category, no more than a set share of one supplier, mutual exclusion of close models; each condition becomes one more constraint and lowers the optimum, so its price is shown too.
  • Brand: constraints include factory slots and minimum lots and fabric with a minimum order: a model with a high profit but a lot above the slot is left out of the set or needs a combined order.
  • Retailer: the shelf is divided by zones and categories, and the total facing does not replace the zonal one: the constraint is entered separately for each zone, otherwise the set turns out infeasible.

Allocation of scarce stock across stores

  • Given 680 units for 6 stores at expected demand of 850 units: stock covers 80% of demand. Expected store sales at stock q equal μ − σ·L(z), z = (q − μ)/σ; this is a concave function, so the optimum is found by marginal analysis: a unit goes to the store where the probability of selling it P(D > q) is higher.
  • Result: proportional division by average demand gives 593.1 units sold, marginal 601.4, that is 1.4% more at the same stock. The gain grows with the spread of uncertainty between stores: stores with predictable demand get less “in reserve”, unstable ones less than their share of average demand. At the optimum the probability of selling the last unit is equalized (on average 67%).
  • A practical rule: the allocation target is not a share of the average but a store demand quantile by the critical ratio limited by actual stock; at a shortage the shortfall is taken from stores with the lowest probability of selling the next unit.
  • Brand: when allocating between partners the contract priority and the return risk are added to the probability of sale: a partner with a high return rate gets less even if its demand is higher.
  • Retailer: between stores the cost of a move and the display minimum are added to the probability of sale: a store does not get a lot below the minimum, and moves are justified only if the gain exceeds the cost.

The transport problem: from where to where

  • Three warehouses with stock of 400, 300, 200 and five stores with demand of 200, 150, 250, 180, 120 units at a unit delivery cost of 25 to RUB 76. The aim is to minimize total cost while meeting demand without exceeding stock. The problem is solved as a minimum cost flow or by the simplex method.
  • The “cheapest route first” heuristic gives RUB 32,530, the exact solution RUB 31,270, so the greedy method is 4% more expensive. The reason: a cheap route can use up limited stock that a store without alternatives needs.
  • Constraints are added to cost: a minimum shipment size, delivery windows, receiving capacity; with discrete constraints the problem becomes integer and is solved by a dedicated solver, not by hand.

Brand and retailer: what is optimized

  • Brand: the knapsack for choosing models for the line under the production budget, factory slots and minimum lots; the objective is the expected line margin and the model count limit reflects production complexity.
  • Retailer: the knapsack for choosing a range under the OTB budget and store shelf; the objective is gross profit net of the price of unsold stock.
  • Brand: allocation of a scarce lot between partners and channels allowing for priorities and contractual commitments; the price of a violated priority enters the objective.
  • Retailer: allocation of a lot between stores by the probability of selling the next unit and transfers between stores with stock at one and a shortage at another.
  • Brand: the transport problem for choosing the shipping point (own warehouse, fulfillment, factory) under tariffs and delivery times to partners.
  • Retailer: the transport problem for supply from warehouses and distribution centers to stores and pick-up points; the price of a shortage and the delivery time enter the route cost.

Where the data comes from

Data sourceFields
Purchasing and forecastModel purchase cost, expected profit and demand with spread (σ), liquidation price of leftovers, minimum lots.
Space and warehouseStore shelf in facings and by category, stock by warehouse and store, receiving capacity.
LogisticsTariffs by warehouse-store routes, delivery times, restrictions on lots and windows.

How to build it step by step

  1. Step 1. Write the problem as a triple: decision variables, objective, constraints; check the units (RUB thousand, units, facings).
  2. Brand: Step 2. Assemble candidate models with purchase cost, expected margin and a factory slot; drop models that violate minimum lots.
  3. Retailer: Step 3. Assemble candidate models with purchase cost, expected profit and shelf use; add a minimum for each category.
  4. Step 4. Solve the knapsack exactly (dynamic programming with integer data) and compare it with the greedy rule in use now.
  5. Step 5. Compute shadow prices: the optimum at a budget of +RUB 500 thousand and a shelf of +1 facing; show which resource limits.
  6. Brand: Step 6. For a scarce lot set partner and channel priorities and find the allocation with the maximum expected sale while honoring contractual commitments.
  7. Retailer: Step 7. For a lot across stores give a unit to the store with the highest probability of selling the next unit (normal demand μ, σ) until stock runs out.
  8. Step 8. For routes build the tariff matrix, find the minimum cost flow and compare it with the current supply scheme.
  9. Step 9. Check stability: recompute with profit and demand estimates changed by ±10-20% and see whether the set and allocation change.
  10. Step 10. Fix the rules: who runs the calculation, which assumptions are recorded, when the decision is reviewed; a decision that cannot be explained is adjusted by hand with the reason recorded.

Formulas

MeasureFormulasNote
Knapsack with two constraintsmax Σ v_i·x_i subject to Σ c_i·x_i ≤ B, Σ w_i·x_i ≤ W, x_i ∈ {0, 1}x_i = 1 if the model is included; costs are integers in step units (here RUB 10 thousand).
Dynamic programmingV_k(b, w) = max{ V_(k−1)(b, w), V_(k−1)(b − c_k, w − w_k) + v_k }Exact, work of N·B·W; with thousands of models a solver is needed.
Shadow priceλ_B ≈ [V(B + ΔB, W) − V(B, W)] / ΔB; λ_W ≈ V(B, W + 1) − V(B, W)A finite-difference estimate; for an integer problem it is an approximation.
Expected salesE[min(q, D)] = μ − σ·L(z), L(z) = φ(z) − z·(1 − Φ(z)), z = (q − μ)/σA normal approximation of demand; at small μ/σ negative demand values distort the estimate.
Marginal allocation conditionP(D_i > q_i) ≈ λ for all stores i, Σ q_i = Qλ is the price of a scarce stock unit in shares of the selling price.
Transport problemmin Σ_ij c_ij·x_ij subject to Σ_j x_ij ≤ s_i, Σ_i x_ij = d_j, x_ij ≥ 0The solution is integer for integer s_i and d_j; total stock is at least total demand.

Formulas in notation

Knapsack
max Σ v_i·x_i; Σ c_i·x_i ≤ B; Σ w_i·x_i ≤ W; x_i ∈ {0, 1}
Choosing a set of models.
Recursion
V_k(b, w) = max{ V_{k−1}(b, w), V_{k−1}(b − c_k, w − w_k) + v_k }
Dynamic programming over models.
Marginal condition
P(D_i > q_i) ≈ λ; Σ q_i = Q
Probabilities of selling the last unit are equal.

Worked example

Choosing models under budget and shelf: four methods

MethodProfit, RUB thousandPurchase, RUB thousandShelf, facingsOf optimum, %
Greedy by profit per rouble of purchase1,4992,3702869.7
Greedy by model profit2,1013,9602897.7
Greedy by profit per share of budget and shelf2,1503,91027100
Exact (dynamic programming)2,1503,91027100

24 candidate models are generated in code (fixed seed): purchase 80-RUB 450 thousand, margin 20-75%, 1-4 facings. Budget RUB 4 million, shelf 28 facings. The data is illustrative; the gap between rules on real data differs.

Figures

Set profit by selection method
Bar chart: Profit per rouble 1,499, Model profit 2,101, Budget and shelf shares 2,150, Exact 2,15005001,0001,5002,0002,500Profit per roubleProfit per roubleSet profit: 1,4991,499Model profitModel profitSet profit: 2,1012,101Budget and shelf sharesBudget and shelfsharesSet profit: 2,1502,150ExactExactSet profit: 2,1502,150RUB thousand
Data as a table
MeasureSet profit
Profit per rouble1,499
Model profit2,101
Budget and shelf shares2,150
Exact2,150

Set profit by selection method. The exact solution is RUB 2.15 million; greedy rules give 1,499 to RUB 2.15 million: a rule that is best on one data set need not be best on another.

Possibility frontier: profit against purchase budget
Line chart: Optimal profit: 1,291 → 2,2561,2001,4001,6001,8002,0002,2002,4002000300040005000600070008000current budgetOptimal profit, 2000: 1,291Optimal profit, 3000: 1,793Optimal profit, 4000: 2,150Optimal profit, 5000: 2,256Optimal profit, 6000: 2,256Optimal profit, 7000: 2,256Optimal profit, 8000: 2,256RUB thousand
Data as a table
MeasureOptimal profit
20001,291
30001,793
40002,150
50002,256
60002,256
70002,256
80002,256

Possibility frontier: profit against purchase budget. Profit grows with the budget up to RUB 5 million and then stops: with a shelf of 28 facings the shelf limits. The slope of the curve is the shadow price of the budget. Axis: purchase budget, RUB thousand.

Profit against shelf at a fixed budget
Bar chart: 16 1,717, 20 1,925, 24 2,067, 28 2,150, 32 2,205, 40 2,25005001,0001,5002,0002,5001616Optimal profit: 1,7171,7172020Optimal profit: 1,9251,9252424Optimal profit: 2,0672,0672828Optimal profit: 2,1502,1503232Optimal profit: 2,2052,2054040Optimal profit: 2,2502,250RUB thousand
Data as a table
MeasureOptimal profit
161,717
201,925
242,067
282,150
322,205
402,250

Profit against shelf at a fixed budget. Facings give diminishing returns: from 16 to 20 facings profit rises by RUB 208 thousand, from 32 to 40 by RUB 45 thousand. Axis: shelf, facings.

Stock allocation across stores
Bar chart: 1 260, 2 180, 3 140, 4 120, 5 90, 6 6005010015020025030011Average demand: 260260Proportional: 208208Marginal: 19119122Average demand: 180180Proportional: 144144Marginal: 16916933Average demand: 140140Proportional: 112112Marginal: 949444Average demand: 120120Proportional: 9696Marginal: 11311355Average demand: 9090Proportional: 7272Marginal: 585866Average demand: 6060Proportional: 4848Marginal: 5555units
  • Average demand
  • Proportional
  • Marginal
Data as a table
MeasureAverage demandProportionalMarginal
1260208191
2180144169
314011294
412096113
5907258
6604855

Stock allocation across stores. Marginal allocation departs from proportional: store 1 with a high demand spread gets less than its share of the average (191 against 208), stores with predictable demand get more. Axis: store number.

Share of demand met by store
Bar chart: 1 65.6, 2 79.5, 3 60.4, 4 79.7, 5 58, 6 78.302040608010011Proportional: 65.665.6Marginal: 61.361.322Proportional: 79.579.5Marginal: 90.990.933Proportional: 60.460.4Marginal: 52.152.144Proportional: 79.779.7Marginal: 91.691.655Proportional: 5858Marginal: 484866Proportional: 78.378.3Marginal: 87.287.2%
  • Proportional
  • Marginal
Data as a table
MeasureProportionalMarginal
165.661.3
279.590.9
360.452.1
479.791.6
55848
678.387.2

Share of demand met by store. Marginal allocation equalizes the return of a unit rather than the shares: 601.4 against 593.1 units sold in total; stores with a low spread have a higher share. Expected sales ÷ average store demand.

Optimal supply plan from warehouses to stores. The optimal plan costs RUB 31,270 against RUB 32,530 for the greedy method; the warehouses serve 3, 2, 1 stores respectively, arrow labels are units.

  1. Warehouse 1: 400 → Store 3: 250; Store 4: 180; Store 5: 120
  2. Warehouse 2: 300 → Store 2: 150; Store 3: 250
  3. Warehouse 3: 200 → Store 1: 200
  4. Store 1: 200
  5. Store 2: 150
  6. Store 3: 250
  7. Store 4: 180
  8. Store 5: 120

Specifics by category

Apparel
Many models and colors: the knapsack is computed by model-color with a condition on width and depth by size runs; the shelf constraint in facings by group and seasonal zone.
Footwear
The constraint is size runs and the warehouse, not only the shelf: stock is divided by size, so allocation goes by size within a model and the knapsack by model.
Accessories
Low prices and many items: the shelf and a cap on item count matter more than the budget; a knapsack with a cap on item count and cross-sell within the range.
Kids
Sizes go obsolete within a season: the price of unsold leftovers is high, so leftover losses enter the objective and allocation is held by age group.
Men
Stable demand and smaller spread: the gain of marginal allocation over proportional is small, rules are enough; the knapsack matters more for the basic line.
Women
High demand spread and fast turnover: marginal allocation and moves between stores give a visible gain; model profit estimates are uncertain, so checking decision stability is mandatory.

Common mistakes

  • Models are chosen by profit ranking ignoring shelf and budget → the set does not fit or leaves budget unused → compute the knapsack with both constraints.
  • A lot is divided proportionally to past sales → unstable stores get too much while predictable ones go short → allocate by the probability of selling the next unit.
  • The optimum is taken for the truth with inaccurate profit estimates → a “fragile” set → check stability under shifted estimates and keep a reserve list of models.
  • Shadow prices are not shown → what limits is not visible → the decision to “add budget” fails if the shelf limits.
  • A route is chosen by the cheapest tariff ignoring warehouse stock → expensive supplies to stores without alternatives → minimum cost flow.

Russian specifics

  • Retailer: transfers between stores and lot allocation are documented as goods movement; labeled goods move with a transfer of marking codes, so labeling constraints are part of the feasible routes. Rule: Decree 1956 of 31.12.2019: Government Decree of 31.12.2019 No. 1956 (marking rules for light-industry goods) (rule check not completed).
  • Brand: partner priorities under shortage are set by contract; an allocation that breaks contract or exclusivity terms must not be selected by optimization, so the constraint is entered explicitly.

Open interactively →