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;

map constraints of an LP supply chain master planning problem and variables of the LP supply chain master planning problem to a planning horizon;

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

identify complicating constraints;

perform masterless iteration with subgradient descent; and

repeat the formulate, identify and perform to incrementally improve an overall solution until a stopping criteria is met.

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

calculate the stopping criteria based on a tolerance for infeasibility or suboptimality.

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

update a learning rate after each iteration of the formulate, identify and perform, wherein the learning rate is updated by dividing a previous learning rate by a factor.

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

in response to a solution to a time-based decomposed subproblem being infeasible, adding one or more virtual variables that make the solution to the time-based decomposed subproblem feasible.

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

split the planning horizon at each of one or more time bucket boundaries; and

choose a time bucket boundary that results in the at least two time-based decomposed subproblems having the most similar sizes.

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

solve the at least two time-based decomposed subproblems in parallel.

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

during solving the at least two time-based decomposed subproblems, set decision variables at upper or lower bounds to retain an objective value of one or more higher objectives.

8. 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;

mapping constraints of an LP supply chain master planning problem and variables of the LP supply chain master planning problem to a planning horizon;

formulating at least two time-based decomposed subproblems by decomposing the LP supply chain master planning problem at 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.

9. The method of claim 8 , further comprising:

calculating the stopping criteria based on a tolerance for infeasibility or suboptimality.

10. The method of claim 8 , further comprising:

updating a learning rate after each iteration of the formulate, identify and perform, wherein the learning rate is updated by dividing a previous learning rate by a factor.

11. The method of claim 10 , further comprising:

in response to a solution to a time-based decomposed subproblem being infeasible, adding one or more virtual variables that make the solution to the time-based decomposed subproblem feasible.

12. The method of claim 11 , further comprising:

splitting the planning horizon at each of one or more time bucket boundaries; and

choosing a time bucket boundary that results in the at least two time-based decomposed subproblems having the most similar sizes.

13. The method of claim 8 , further comprising:

solving the at least two time-based decomposed subproblems in parallel.

14. The method of claim 13 , further comprising:

during solving the at least two time-based decomposed subproblems, setting decision variables at upper or lower bounds to retain an objective value of one or more higher objectives.

15. 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;

maps constraints of an LP supply chain master planning problem and variables of the LP supply chain master planning problem to a planning horizon;

formulates at least two time-based decomposed subproblems by decomposing the LP supply chain master planning problem at 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.

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

calculates the stopping criteria based on a tolerance for infeasibility or suboptimality.

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

updates a learning rate after each iteration of the formulate, identify and perform, wherein the learning rate is updated by dividing a previous learning rate by a factor.

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

in response to a solution to a time-based decomposed subproblem being infeasible, adds one or more virtual variables that make the solution to the time-based decomposed subproblem feasible.

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

splits the planning horizon at each of one or more time bucket boundaries; and

chooses a time bucket boundary that results in the at least two time-based decomposed subproblems having the most similar sizes.

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

solves the at least two time-based decomposed subproblems in parallel.