28 April 2023
Price breaks, or volume discounts, are common when buying products in bulk. That is, the marginal cost of additional products falls as volume increases. In a linear program, price breaks are tricky to model because the break points are non-linear discontinuities.
In a spreadsheet, a natural way to model price breaks is to use functions like
MAX. However, those functions are discontinuous, so we can't use the Simplex linear method in Solver. We also can't use the OpenSolver solvers at all when our model includes those functions. We could use Solver's GRG non-linear or Evolutionary methods, but they are not always reliable.
Fortunately, there is a way to express price breaks linearly, by using some binary variables, as described in our article MIP formulations and linearizations.
In this article, we describe an example of how to represent price breaks in a linear programming model, built in Excel using Solver or OpenSolver.
Download the model
The model is available on GitHub
We own a small cranberry sauce manufacturing business. The recipe is an old, family secret – passed down from generation to generation. Of course, the main ingredient is cranberries.
We use only fresh cranberries. Given our current production, our demand for cranberries is 2,250 kg/week.
There are three local suppliers of fresh cranberries. As shown in Figure 1, two of the suppliers offer a price structure that has incremental price breaks, while the other supplier offers a flat price.
- Premium Fruits. Has an incremental price break structure, starting at \$2.00/kg for the first 50 kg, \$1.80/kg for the next 50 kg, etc. We have an existing contract to buy 250 kg per week. They can supply up to 2,000 kg per week.
- Joe's Cranberries. Sells cranberries with an incremental price break structure, starting at \$1.50/kg for the first 100 kg, \$1.00/kg for the next 200 kg, etc. They can supply up to 3,000 kg per week.
- Bulk Berries. Offers a flat price of \$0.75/kg for any quantity. They can supply up to 10,000 kg per week.
Our question is: Which supplier, or combination of suppliers, should we choose to minimize the total cost of our weekly order of cranberries?
Representing incremental price breaks
In our article MIP formulations and linearizations we refer to a document from FICO that includes, amongst other things, a linear formulation for representing incremental price breaks.
The structure of the price breaks is expressed in terms of quantity bands, each of which has a price. This structure is shown in Figure 2, which is just another way of showing the pricing structures in Figure 1.
That is, we have incremental price breaks, meaning that the unit cost for items between quantities 0 and $B_1$ (band 1) is $Cost_1$, quantities between $B_1$ and $B_2$ (band 2) cost $Cost_2$ each, etc. This type of incremental pricing structure is exactly the situation we have with two of our cranberry suppliers.
The document also includes a formulation for "all items discounts", meaning that when buying a certain number of items we get discounts on all items that we buy if the quantity is within certain price bands. That formulation is not of interest in this model, but it might be in other situations.
The formulation uses binary variables to represent each band of the price function, as shown in Figure 3. Note that we have generalized the document's formulation to have any number of price bands.
Note that Equation (4) is a special case for the last band. With careful construction of the formulae, we can collapse this constraint into Equation (3).
The rest of our model formulation is straightforward – it simply repeats the price band structure for each supplier and ensures that we meet demand at minimum cost. We also require that the existing contract quantity with Premium Fruits is fulfilled.
Price bands data
To implement the model in Excel, we start with the data, as shown in Figure 4.
For each supplier, we list the quantity break points for each band, along with the price for all quantity within that band. We've allowed up to 7 bands, though this could easily be extended.
The Bulk Berries supplier doesn't offer price breaks – they have a flat price for all quantities. This structure can be accommodated within our model by specifying their data to have just one band.
Equation (5) of the formulation starts with the second band, because it refers to the previous band. We can simplify construction of the model by introducing an empty dummy band zero, to avoid this special case. This dummy band has hard-coded quantities and prices all equal to zero.
Note that the suppliers can have different quantity break points and different numbers of bands. The model handles those differences automatically.
Variables we'll need
We need two sets of variables, as shown in Figure 5:
- Use. A binary variable to indicate whether we're using each band. These variables correspond to $b_i$ in the formulation, though we have an additional dimension to represent each supplier.
- Quantity (kg). The quantity of cranberries purchased within each price band. These variables correspond to $x_i$ in the formulation, though we have an additional dimension to represent each supplier.
Note that both Solver and OpenSolver may set some of the Use binary variables to 1, even when that band is not used. This occurs because our model has no penalty for setting those variables to a non-zero value, provided the quantity variables are zero. That is, this quirk does no harm. We could tidy up the model by forcing the stray Use variables to zero by giving them a very small penalty in the objective function, though it isn't necessary to do so.
Constraints to create price breaks
Figure 6 shows the two sets of constraints that represent:
- Equation (2): the lower bounds on the band quantities.
- Equations (3) and (4): the upper bounds on the band quantities.
In the spreadsheet, these two constraints are a direct translation of the formulation, simplified to consolidate the special cases.
We also have constraints that represent Equation (5), applied directly to the Use variables in Figure 5. Those constraints ensure that if we use a band, then we must also use all lower quantity bands. This is necessary because the prices decline as quantity increases. Therefore, the solver would prefer to use higher quantity bands first – because they are cheaper. But such a solution isn't allowed, so we need to forbid it.
The Solver model is shown in Figure 7. Our objective is to minimize the total cost of buying the required demand for cranberries.
The model has two sets of variables:
vUse. Binary variable indicating whether to use each price band for each supplier.
vQuantity. Purchase quantity in each price band for each supplier.
The constraints are:
fQty_Supplier >= dQty_Supplier_LB. Total quantity for each supplier must be at least the minimum quantity for that supplier. We use this to implement the existing contract with Premium Fruits.
fQty_Supplier <= dQty_Supplier_UB. Total quantity for each supplier must be no more than the maximum quantity available from that supplier.
fQty_Total >= dQty_Demand. Overall total quantity must be at least the required demand. Since we're minimizing cost, the model will exceed demand only if it must (i.e., if the minimum quantities from the suppliers sum to more than the demand).
vQuantity <= fBand_UB. The quantity in each band from each supplier must comply with Equation (2).
vQuantity >= fBand_LB. The quantity in each band from each supplier must comply with Equations (3) and (4).
vUse_i >= vUse_i_plus_1. Requires that lower band are used first, as specified in Equation (5).
All the model's relationships are linear, along with some binary variables, so we can use the Simplex method. This model is sufficiently small that either Solver or OpenSolver can be used.
The optimal solution for our Base Case (also known as Scenario A) is shown in Figure 8.
We purchase the contracted 250 kg from Premium Fruits, but nothing more. The remainder of our demand is met by Bulk Berries, with a quantity of 2,000 kg. The total cost is \$1,920.00.
The average cost for Premium Fruits is very high, at \$1.680/kg, compared with the cost of \$0.750/kg for our purchase from Bulk Berries – so it is easy to see why we limit our purchase from Premium Fruits to only the contracted quantity.
But why didn't we purchase anything from Joe's Cranberries? Given Joe's price breaks, the cost of 2,000 kg would be \$1,510 (\$10 more than from Bulk Berries). The average price would be \$0.755 – slightly more expensive than the \$0.750/kg for Bulk Berries. Therefore, the optimal solution is to not buy any quantity from Joe's Cranberries.
To explore how the optimal solution changes if we alter the demand, we consider some additional scenarios. That is, we vary the demand to see how that affects which suppliers to choose, given our other constraints. We also see how our choice of supplier(s) changes once the existing contract with Premium Fruits ends.
Detailed results are shown in Figures 9 and 10.
- 1. Base Case. We are required to buy at least 250 kg from Premium Fruits. The remainder of the demand is purchased from Bulk Berries, at a price of \$0.75/kg, as they are cheaper than Premium Fruits and Joe's Cranberries.
- 2. Increase demand to 2,500 kg. Increasing demand reduces the average cost for Joe's Cranberries to \$0.738, which is less than the \$0.75/kg cost for Bulk Berries. Therefore, we switch to buying from Joe (apart from the contracted quantity from Premium Fruits).
- 3. Increase demand to 3,500 kg. If the demand increases further, then Joe's Cranberries cannot supply our demand (because they have a capacity of 2,000 kg/week), so we buy from all three suppliers.
- 4. After Premium contract ends. After the Premium Fruits contract ends, Joe is the cheapest supplier for our current demand quantity. Premium Fruits is always more expensive than the other suppliers, so without the contract we would not choose to buy from Premium Fruits.
- 5. After Premium, demand 2,500 kg. Joe remains the cheapest supplier if demand increases slightly after the Premium Fruits contract ends.
- 6. After Premium, demand 3,500 kg. Like Scenario 3, if demand increases further, then Joe cannot meet all our demand. Therefore, we need to buy from both Joe and Bulk Berries – though not from Premium Fruits, who are too expensive.
- 7. After Premium, demand 2,067 kg. The crossover point between Joe and Bulk Berries occurs where the average cost for Joe equals the cost for Bulk Berries – i.e., at \$0.75/kg. When the demand is 2,067 kg, the average price for Joe is \$0.74998/kg, so Joe is very slightly cheaper than Bulk Berries. For demand more than 2,067 kg, Joe's marginal cost is \$0.60/kg, which is less than the \$0.75/kg for Bulk Berries, so we would buy from Joe.
- 8. After Premium, demand 2,066 kg. But if demand is 1 kg less, then the average price for Joe is \$0.75005/kg, so Bulk Berries is very slightly cheaper than Joe. Therefore, if demand is 2,066 kg or less, we would switch to buying all the demand from Bulk Berries.
In this article we've describe how to solve a linear programming model that includes incremental price breaks from multiple suppliers. The model formulation applies a linearization technique that uses binary variables to represent each of the price bands.
The model is built in Excel, though the same technique could easily be applied to a model built using other tools, such as Python.
We also solved several scenarios, to explore how the price breaks behave under a variety of assumptions. The key factor in determining which supplier to choose is the average cost over the allocated volume.
If you would like to know more about this model, or you want help with your own models, then please contact us.
FICO Xpress Optimization (2017). "MIP formulations and linearizations: Quick reference", PDF available from MIP formulations and linearizations. Online version also available at FICO Xpress optimization help.