Systems And Methods For Markdown Optimization When Inventory Pooling Level Is Above Pricing Level

• US 20100250329A1
• Filed: 03/26/2009
• Published: 09/30/2010
• Est. Priority Date: 03/26/2009
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Yao, Xiaodong, Sanli, Tugrul
• Granted Patent: US 8,271,318 B2
• Time in Patent Office: Days
• US Class Current: 705/10
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders
• CPC Class Codes: G06Q 30/0283 Price estimation or determination
• CPC Class Codes: G06Q 40/08 Insurance

Abstract

Computer-implemented systems and methods generate a near-optimum product markdown plan for a plurality of uniform pricing levels having a required inventory sell-through target over all of the plurality of uniform pricing levels. A plurality of feasible markdown schedules are generated for the uniform pricing level, where each of the plurality of feasible markdown schedules meets all individual constraints for the uniform pricing level. All dominated feasible markdown schedules are removed for the uniform pricing level to generate one or more candidate markdown schedules for the uniform pricing level. A near-optimum product markdown plan is generated, where generating the near-optimum product markdown plans includes executing a limited exact algorithm solver for a plurality of iterations, and executing a dynamic programming solver if no product markdown plan generated by the limited exact algorithm solver is within the threshold percentage of the revenue upper bound.

Claims

1. A computer-implemented method for generating a near-optimum product markdown plan for a plurality of uniform pricing levels having a required inventory sell-through target over all of the plurality of uniform pricing levels, the method comprising,

executing instructions on a processor to receive uniform pricing level data for a uniform pricing level from a computer-readable data store;

executing instructions on a processor to generate a plurality of feasible markdown schedules for the uniform pricing level, wherein each of the plurality of feasible markdown schedules meets all individual constraints for the uniform pricing level;

executing instructions on a processor to remove all dominated feasible markdown schedules for the uniform pricing level to generate one or more candidate markdown schedules for the uniform pricing level;

executing instructions on a processor to generate the near-optimum product markdown plan of one candidate markdown schedule for each of the plurality of uniform pricing levels, wherein generating the near-optimum product markdown plan includes;

executing instructions on a processor to execute a limited exact algorithm solver for a plurality of iterations to generate a product markdown plan on each iteration;

wherein a product markdown plan is selected as the near-optimum product markdown plan if the product markdown plan generates an expected revenue within a threshold percentage of a revenue upper bound;

executing instructions on a processor to execute a dynamic programming solver to generate the near-optimum product markdown plan if no product markdown plan generated by the limited exact algorithm solver is within the threshold percentage of the revenue upper bound;

executing instructions on a processor to store the near-optimum product markdown plan in a computer-readable medium.

2. The method of claim 1, wherein the uniform pricing level data includes a list price of product/location pair, a price response coefficient, and a base forecast;

wherein an inventory is liquidated based upon the stored near-optimum product markdown plan.

3. The method of claim 1, wherein a uniform pricing level identifies a member of a product/location hierarchy having children members that are all priced according to a same product markdown schedule.

4. The method of claim 1, wherein a feasible markdown schedule is dominated if another feasible markdown schedule for the uniform pricing level generates a higher expected revenue and lower expected inventory totals for the uniform pricing level.

5. The method of claim 1, wherein the revenue upper bound value is calculated by relaxing a 0,1 integer constraint for all candidate markdown schedules and solving for an exact optimum markdown plan.

6. The method of claim 1, wherein the limited exact algorithm selects one candidate markdown schedule from the one or more candidate markdown schedules for each of the plurality of uniform pricing levels on each iteration, wherein a combination of selected candidate markdown schedules forms the product markdown plan that meets the required inventory sell through target over all of the plurality of uniform pricing levels.

7. The method of claim 6, wherein the one candidate markdown schedule for each of the plurality of uniform pricing levels for an iteration is selected based on a gradient calculation that identifies most promising sets of candidate markdown schedules for each of the plurality of uniform pricing levels.

8. The method of claim 1, wherein a product markdown plan is selected as the near-optimum product markdown plan if the product markdown plan generates an expected revenue within a user specified percentage of the revenue upper bound.

9. The method of claim 1, wherein the dynamic programming solver operates on a reduced set of candidate markdown schedules, wherein the reduced set of candidate markdown schedules includes only candidate markdown schedules that offer better expected inventory and expected revenue than a best product markdown plan generated by the limited exact algorithm.

10. The method of claim 9, wherein the dynamic programming solver implements an iterative calculation to calculate the near-optimum product markdown plan from the reduced set of candidate markdown schedules.

11. The method of claim 10, wherein the iterative calculation iterates over each of the uniform pricing levels and over each of a revised ending inventory constraint value.

12. The method of claim 11, wherein for each of the z uniform pricing levels i and for each of the j revised ending inventory constraint B′

a revenue value π

is calculated such that;

π

(z,j)=R′

_i,j+v<sub>i−

1</sub>(z−

I′

_i,j)

where R′

_i,j=R_i,j−

R_i,si,

where R_i,j is a revenue value for the j^th feasible markdown schedule for the i^th uniform pricing level, where R_i,si is a revenue value for the feasible markdown schedule for the i^th uniform pricing level included in the best product markdown plan generated by the limited exact algorithm,

where I′

_i,j=I_i,j−

I_i,si,

where I_i,j is an unsold inventory value for the j^th feasible markdown schedule for the i^th uniform pricing level, where I_i,si is an unsold inventory value for the feasible markdown schedule for the i^th uniform pricing level included in the best product markdown plan generated by the limited exact algorithm,

where v_i(z)=max{π

(z,j)}

where v₀(z)=0.

13. The method of claim 1, wherein the computer-readable data store is hierarchically arranged.

14. A computer-implemented system for generating a near-optimum product markdown plan for a plurality of uniform pricing levels having a required inventory sell-through target over all of the plurality of uniform pricing levels, the system comprising:

a computer-readable data store containing uniform pricing level data for a uniform pricing level;

computer-readable instructions for a feasible markdown schedule generator configured to generate a plurality of feasible markdown schedules for the uniform pricing level, wherein each of the plurality of feasible markdown schedules meets all individual constraints for the uniform pricing level;

computer-readable instructions for a dominated markdown schedule remover configured to remove all dominated feasible markdown schedules for the uniform pricing level to generate one or more candidate markdown schedules for the uniform pricing level;

computer readable instructions for a markdown heuristic solver configured to generate the near-optimum product markdown plan of one candidate markdown schedule for each of the plurality of uniform pricing levels, wherein the markdown heuristic solver further includes;

computer-readable instructions for a limited exact algorithm solver configured to execute for a plurality of iterations to generate a product markdown plan on each iteration, where a product markdown plan is selected as the near-optimum product markdown plan if the product markdown plan generates an expected revenue within a threshold percentage of a revenue upper bound;

computer-readable instructions for a dynamic programming solver configured to generate the near-optimum product markdown plan if no product markdown plan generated by the limited exact algorithm solver is within the threshold percentage of the revenue upper bound;

computer-readable instructions for storing the near-optimum product markdown plan in a computer-readable medium.

15. The system of claim 14, wherein a feasible markdown schedule is dominated if another feasible markdown schedule for the uniform pricing level generates a higher expected revenue and lower expected inventory totals for the uniform pricing level.

16. The system of claim 14, wherein the revenue upper bound is calculated by relaxing a 0,1 integer constraint for all candidate markdown schedules and solving for an exact optimum markdown plan.

17. The system of claim 14, wherein the limited exact algorithm solver selects one candidate markdown schedule from the one or more candidate markdown schedules for each of the plurality of uniform pricing levels on each iteration, wherein a combination of selected candidate markdown schedules forms the product markdown plan that meets the required inventory sell through target over all of the plurality of uniform pricing levels.

18. The system of claim 17, wherein the one candidate markdown schedule for each of the plurality of uniform pricing levels for an iteration is selected based on a gradient calculation that identifies most promising sets of candidate markdown schedules for each of the plurality of uniform pricing levels.

19. The system of claim 14, wherein the dynamic programming solver operates on a reduced set of candidate markdown schedules, wherein the reduced set of candidate markdown schedules includes only candidate markdown schedules that offer better expected inventory and expected revenue than a best product markdown plan generated by the limited exact algorithm.

20. The system of claim 14, wherein the computer-readable data store containing uniform pricing level data for a uniform pricing level is a hierarchically arranged data store.