Time-based decomposition for supply chain optimization problem

1. A system for iteratively solving a supply chain planning problem modeled as a linear programming (LP) problem, comprising:

a computer, comprising a processor and memory, the computer configured to:

receive a multi-period matrix formulation of at least a portion of an LP supply chain master planning problem representing a supply chain planning problem for a supply chain network, the supply chain planning problem comprising a planning horizon divided into time buckets separated by time-bucket boundaries;

map constraints of the LP supply chain master planning problem and variables of the LP supply chain master planning problem to the time buckets;

calculate a quantity of cross-over variables for the constraints and the time buckets;

select one or more decomposition boundaries from the time-bucket boundaries based, at least in part, on the quantity of cross-over variables;

formulate at least two time-based decomposed subproblems by decomposing the LP supply chain master planning problem at the one or more decomposition boundaries;

identify complicating constraints;

perform masterless iteration with subgradient descent; and

repeat the formulate, identify and perform steps to incrementally improve an overall solution until a stopping criteria is met, wherein the stopping criteria is based on an objective function not improving for a previous number of iterations of the repeated steps.

2. The system of claim 1 , wherein the computer is further configured to:

calculate an effective dual based, at least in part, on a mathematical difference of at least two dual values, each of the at least two dual values calculated by solving the at least two time-based decomposed subproblems and comprising a dual value of a complicating constraint of the least two time-based decomposed subproblems, wherein the complicating constraint comprises at least one variable in both:

a time bucket earlier than the decomposition boundary; and

a time bucket later than the decomposition boundary.

3. The system of claim 2 , wherein the computer is further configured to:

update a learning rate and a value of the complicating constraint based, at least in part, on the calculated effective dual; and

solve the at least two time-based decomposed subproblems based, at least in part, on the updated learning rate and the updated value of the complicating constraint.

4. The system of claim 1 , wherein the computer is further configured to:

identify a variable as a cross-over variable when a sign of a coefficient of the variable in at least one of the time buckets is different from a sign of a coefficient of the variable in a different time bucket.

5. The system of claim 4 , wherein the one or more decomposition boundaries comprise a time-bucket boundary having a minimum quantity of cross-over variables.

6. The system of claim 4 , wherein the one or more decomposition boundaries comprise one or more time-bucket boundaries having a minimum quantity of cross-over variables that decomposes the LP supply chain master planning problem into at least two time-based decomposed subproblems that are balanced subproblems.

7. A computer-implemented method for iteratively solving a supply chain planning problem modeled as a linear programming (LP) problem, comprising:

receiving a multi-period matrix formulation of at least a portion of an LP supply chain master planning problem representing a supply chain planning problem for a supply chain network, the supply chain planning problem comprising a planning horizon divided into time buckets separated by time-bucket boundaries;

mapping constraints of the LP supply chain master planning problem and variables of the LP supply chain master planning problem to the time buckets;

calculating a quantity of cross-over variables for the constraints and the time buckets;

selecting one or more decomposition boundaries from the time-bucket boundaries based, at least in part, on the quantity of cross-over variables;

formulating at least two time-based decomposed subproblems by decomposing the LP supply chain master planning problem at the one or more decomposition boundaries;

identifying complicating constraints;

performing masterless iteration with subgradient descent; and

repeating the formulating, identifying and performing steps to incrementally improve an overall solution until a stopping criteria is met, wherein the stopping criteria is based on an objective function not improving for a previous number of iterations of the repeated steps.

8. The method of claim 7 , further comprising:

calculating an effective dual based, at least in part, on a mathematical difference of at least two dual values, each of the at least two dual values calculated by solving the at least two time-based decomposed subproblems and comprising a dual value of a complicating constraint of the least two time-based decomposed subproblems, wherein the complicating constraint comprises at least one variable in both:

a time bucket earlier than the decomposition boundary; and

a time bucket later than the decomposition boundary.

9. The method of claim 8 , further comprising:

updating a learning rate and a value of the complicating constraint based, at least in part, on the calculated effective dual; and

solving the at least two time-based decomposed subproblems based, at least in part, on the updated learning rate and the updated value of the complicating constraint.

10. The method of claim 7 , further comprising:

identifying a variable as a cross-over variable when a sign of a coefficient of the variable in at least one of the time buckets is different from a sign of a coefficient of the variable in a different time bucket.

11. The method of claim 10 , wherein the one or more decomposition boundaries comprise a time-bucket boundary having a minimum quantity of cross-over variables.

12. The method of claim 10 , wherein the one or more decomposition boundaries comprise one or more time-bucket boundaries having a minimum quantity of cross-over variables that decomposes the LP supply chain master planning problem into at least two time-based decomposed subproblems that are balanced subproblems.

13. A non-transitory computer-readable medium embodied with software that iteratively solves a supply chain planning problem modeled as a linear programming (LP) problem, the software when executed:

receives a multi-period matrix formulation of at least a portion of an LP supply chain master planning problem representing a supply chain planning problem for a supply chain network, the supply chain planning problem comprising a planning horizon divided into time buckets separated by time-bucket boundaries;

maps constraints of the LP supply chain master planning problem and variables of the LP supply chain master planning problem to the time buckets;

calculates a quantity of cross-over variables for the constraints and the time buckets;

selects one or more decomposition boundaries from the time-bucket boundaries based, at least in part, on the quantity of cross-over variables;

formulates at least two time-based decomposed subproblems by decomposing the LP supply chain master planning problem at the one or more decomposition boundaries;

identifies complicating constraints;

performs masterless iteration with subgradient descent; and

repeats the formulates, identifies and performs steps to incrementally improve an overall solution until a stopping criteria is met, wherein the stopping criteria is based on an objective function not improving for a previous number of iterations of the repeated steps.

14. The non-transitory computer-readable medium of claim 13 , wherein the software when executed further:

calculates an effective dual based, at least in part, on a mathematical difference of at least two dual values, each of the at least two dual values calculated by solving the at least two time-based decomposed subproblems and comprising a dual value of a complicating constraint of the least two time-based decomposed subproblems, wherein the complicating constraint comprises at least one variable in both:

a time bucket earlier than the decomposition boundary; and

a time bucket later than the decomposition boundary.

15. The non-transitory computer-readable medium of claim 14 , wherein the software when executed further:

updates a learning rate and a value of the complicating constraint based, at least in part, on the calculated effective dual; and

solves the at least two time-based decomposed subproblems based, at least in part, on the updated learning rate and the updated value of the complicating constraint.

16. The non-transitory computer-readable medium of claim 13 , wherein the software when executed further:

identifies a variable as a cross-over variable when a sign of a coefficient of the variable in at least one of the time buckets is different from a sign of a coefficient of the variable in a different time bucket.

17. The non-transitory computer-readable medium of claim 16 , wherein the one or more decomposition boundaries comprise a time-bucket boundary having a minimum quantity of cross-over variables.