Systems and methods for markdown optimization when inventory pooling level is above pricing level

• US 8,271,318 B2
• Filed: 03/26/2009
• Issued: 09/18/2012
• Est. Priority Date: 03/26/2009
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Sanli, Tugrul, Yao, Xiaodong
• Primary Examiner(s): Allen, Akiba
• Application Number:
  US12/412,046
• Publication Number:
  US 20100250329A1
• Time in Patent Office: 1,272 Days
• Field of Search: 705/7.35, 705/1.1, 705/7.27, 705/7.29, 705/7.31
• US Class Current: 705/7.35
• 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 selecting a product markdown plan, comprising:

receiving, by one or more data processors, candidate data corresponding to a plurality of candidate markdown sets that detail schedules for marking down prices of one or more products;

receiving, by the one or more data processors, constraints data, wherein the constraints data includes individual constraints that apply to a single candidate markdown set, and wherein the constraints data includes a linking constraint that applies to the plurality of candidate markdown sets;

generating, by the one or more data processors, candidate markdown schedules for each of the candidate markdown sets, wherein each candidate markdown schedule conforms to applicable individual constraints;

generating, by the one or more data processors, one or more class sets, wherein each class set includes a candidate markdown schedule, and wherein each class set conforms to the linking constraint;

evaluating, by the one or more data processors, the one or more class sets, wherein the evaluations are iterative, and wherein each evaluation iteration includes computing an expected revenue value for a class set;

computing, by the one or more data processors, a revenue upper bound using the candidate markdown schedules and the linking constraint;

terminating, by the one or more data processors, the evaluation when a threshold number of iterations is reached, wherein the terminating includes determining a class set with a highest expected revenue value within a threshold of the revenue upper bound; and

selecting, by the one or more data processors, a product markdown plan, wherein the product markdown plan includes the class set with the highest expected revenue value.

2. The method of claim 1, wherein terminating further includes:

determining a class set with an expected revenue value that conforms to the revenue upper bound.

3. The method of claim 1, wherein terminating further includes:

selecting a product markdown plan using a dynamic programming solver when no product markdown plan is selected.

4. The method of claim 1, further comprising:

identifying, using the one or more data processors, dominated markdown schedules among the candidate markdown schedules, wherein the dominated markdown schedules are removed.

5. The method of claim 1, further comprising:

ranking, using the one or more data processors, the one or more class sets according to a revenue generation likelihood, wherein the one or more class sets are evaluated according to rank.

6. The method of claim 1, wherein the threshold of the revenue upper bound is based upon a percentage of the revenue upper bound.

7. The method of claim 6, wherein the percentage is a predetermined percentage.

8. The method of claim 1, wherein inventory is liquidated based upon the selected product markdown plan.

9. The method of claim 1, wherein computing further comprises:

relaxing a 0,1 integer constraint for all candidate markdown schedules; and

solving for an exact optimum product markdown plan.

10. The method of claim 1, wherein generating one or more class sets includes using a gradient calculation to identify promising sets of the candidate markdown schedules.

11. The method of claim 3, wherein the dynamic programming solver operates on a reduced set of candidate markdown schedules.

12. The method of claim 11, wherein the reduced set of candidate markdown schedules includes only candidate markdown schedules that offer better expected inventory and higher expected revenue than the selected product markdown plan.

13. The method of claim 12, wherein the dynamic programming solver implements an iterative calculation to select the product markdown plan from the reduced set of candidate markdown schedules.

14. The method of claim 13, wherein the iterative calculation uses each of a plurality of uniform pricing levels and each of a plurality of revised ending inventory constraint values.

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

, a revenue value π

is calculated such that;

π

(z,j)=R′

_i,j+v_i-1(z−

I′

_i,j)

where R′

_i,j=R_i,j−

R_i,si,

where R_i,j is an expected revenue value for the j^th candidate markdown schedule for the i^th uniform pricing level, where R_i,si is an expected revenue value for the candidate markdown schedule for the i^th uniform pricing level included in the class set with the highest expected revenue value,

where I′

_i,j=I_i,j−

I_i,si,

where I_i,j is an unsold inventory value for the j^th candidate markdown schedule for the i^th uniform pricing level, where I_i,si is an unsold inventory value for the candidate markdown schedule for the i^th uniform pricing level included in the class set with the highest expected revenue value,

where v_i(z)=max{π

(z,j)}, and

where v₀(z)=0.

16. The method of claim 1, wherein the candidate data is hierarchically arranged.

17. A system for selecting a product markdown plan, comprising:

one or more processors;

one or more computer-readable storage mediums containing instructions configured to cause the one or more processors to perform operations including;

receiving candidate data corresponding to a plurality of candidate markdown sets that detail schedules for marking down prices of one or more products;

receiving constraints data, wherein the constraints data includes individual constraints that apply to a single candidate markdown set, and wherein the constraints data includes a linking constraint that applies to the plurality of candidate markdown sets;

generating candidate markdown schedules for each of the candidate markdown sets, wherein each candidate markdown schedule conforms to applicable individual constraints;

generating one or more class sets wherein each class set includes a candidate markdown schedule, and wherein each class set conforms to the linking constraint;

evaluating the one or more class sets, wherein the evaluations are iterative, and wherein each evaluation iteration includes computing an expected revenue value for a class set;

computing a revenue upper bound using the candidate markdown schedules and the linking constraint;

terminating the evaluation when a threshold number of iterations is reached, wherein the terminating includes determining a class set with a highest expected revenue value within a threshold of the revenue upper bound; and

selecting a product markdown plan, wherein the product markdown plan includes the class set with the highest expected revenue value.

18. A computer-program product for selecting a product markdown plan, tangibly embodied in a machine-readable storage medium, including instructions configured to cause a data processing apparatus to:

receive candidate data corresponding to a plurality of candidate markdown sets that detail schedules for marking down prices of one or more products;

receive constraints data, wherein the constraints data includes individual constraints that apply to a single candidate markdown set, and wherein the constraints data includes a linking constraint that applies to the plurality of candidate markdown sets;

generate candidate markdown schedules for each of the candidate markdown sets, wherein each candidate markdown schedule conforms to applicable individual constraints;

generate one or more class sets wherein each class set includes a candidate markdown schedule, and wherein each class set conforms to the linking constraint;

evaluate the one or more class sets, wherein the evaluations are iterative, and wherein each evaluation iteration includes computing an expected revenue value for a class set;

compute a revenue upper bound using the candidate markdown schedules and the linking constraint;

terminate the evaluation when a threshold number of iterations is reached, wherein the terminating includes determining a class set with a highest expected revenue value within a threshold of the revenue upper bound; and

select a product markdown plan, wherein the product markdown plan includes the class set with the highest expected revenue value.