Image-based decomposition for fast iterative solve of complex linear problems

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

a computer, comprising a processor, memory:

an image rendering engine configured to:

receive a matrix formulation of at least a portion of an LP problem representing a supply chain planning problem for a supply chain network; and

generate pixels of a supply chain problem image, the pixels representing links between constraints and variables of the LP problem;

an image processing engine configured to:

identify one or more contours of the supply chain problem image using a machine-learning model trained using a convolutional neural network (CNN) and contour-labeled images received from the image rendering engine, wherein the one or more contours comprise at least a first contour and a second contour;

the image rendering engine further configured to:

identify one or more first constraints represented by the first contour of the one or more contours;

remove at least one of the one or more first constraints represented by the first contour to determine at least two components linked by the first contour;

identify one or more second constraints represented by the second contour of the one or more contours;

remove at least one of the one or more second constraints represented by the second contour to determine at least two components linked by the second contour;

determine a partition comprising the at least two components linked by the first contour is more balanced than a partition comprising the at least two components linked by the second contour;

select the at least one of the one or more first constraints as the one or more complicating constraints; and

formulate at least two decomposed subproblems sharing one or more complicating constraints associated with at least one of the one or more contours; and

a solver configured to:

solve the decomposed subproblems to generate a solution to the supply chain planning problem.

2. The system of claim 1 , wherein the image rendering engine is further configured to:

identify one or more constraints represented by a first contour of the one or more contours;

remove at least one of the one or more identified constraints represented by the first contour to determine at least two components linked by the first contour; and

select the at least one of the one or more identified constraints as at least one of the one or more complicating constraints.

3. The system of claim 1 , wherein the image processing engine is further configured to:

downscale the supply chain problem image by applying a compression ratio and coordinates scaling to the matrix formulation.

4. The system of claim 1 , wherein the image rendering engine is further configured to:

calculate coordinates of one or more pixels of the one or more contours, wherein the coordinates indicate row-column indices for a constraints-variables sparse matrix; and

identify at least one variable and at least one constraint represented by the one or more pixels of the one or more contours.

5. The system of claim 1 , wherein:

the supply chain network is partitioned into at least two supply chains at an image boundary comprising at least one of the one or more complicating constraints.

6. The system of claim 1 , wherein a balance of a partition is based, at least in part, on a ratio of a number of constraints of the at least two components.

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

receiving, by an image rendering engine, a matrix formulation of at least a portion of an LP problem representing a supply chain planning problem for a supply chain network;

generating pixels, by the image rendering engine, of a supply chain problem image, the pixels representing links between constraints and variables of the LP problem;

identifying, by an image processing engine, one or more contours of the supply chain problem image using a machine-learning model trained using a convolutional neural network (CNN) and contour-labeled images received from the image rendering engine, wherein the one or more contours comprise at least a first contour and a second contour;

identifying, by the image rendering engine, one or more first constraints represented by the first contour of the one or more contours;

removing, by the image rendering engine, at least one of the one or more first constraints represented by the first contour to determine at least two components linked by the first contour;

identifying, by the image rendering engine, one or more second constraints represented by the second contour of the one or more contours;

removing, by the image rendering engine, at least one of the one or more second constraints represented by the second contour to determine at least two components linked by the second contour;

determining, by the image rendering engine, a partition comprising the at least two components linked by the first contour is more balanced than a partition comprising the at least two components linked by the second contour;

selecting, by the image rendering engine, the at least one of the one or more first constraints as the one or more complicating constraints;

formulating, by the image rendering engine, at least two decomposed subproblems sharing one or more complicating constraints associated with at least one of the one or more contours; and

solving, by a solver, the decomposed subproblems to generate a solution to the supply chain planning problem.

8. The computer-implemented method of claim 7 , further comprising:

identifying, by the image rendering engine, one or more constraints represented by a first contour of the one or more contours;

removing, by the image rendering engine, at least one of the one or more identified constraints represented by the first contour to determine at least two components linked by the first contour; and

selecting, by the image rendering engine, the at least one of the one or more identified constraints as at least one of the one or more complicating constraints.

9. The computer-implemented method of claim 7 , further comprising:

downscaling, by the image processing engine, the supply chain problem image by applying a compression ratio and coordinates scaling to the matrix formulation.

10. The computer-implemented method of claim 7 , further comprising:

calculating, by the image rendering engine, coordinates of one or more pixels of the one or more contours, wherein the coordinates indicate row-column indices for a constraints-variables sparse matrix; and

identifying, by the image rendering engine, at least one variable and at least one constraint represented by the one or more pixels of the one or more contours.

11. The computer-implemented method of claim 7 , wherein:

the supply chain network is partitioned into at least two supply chains at an image boundary comprising at least one of the one or more complicating constraints.

12. The computer-implemented method of claim 7 , wherein a balance of a partition is based, at least in part, on a ratio of a number of constraints of the at least two components.

13. A non-transitory computer-readable medium embodied with software providing solving of supply chain planning problems modeled as linear programing (LP) problems, the software when executed:

receives, by an image rendering engine, a matrix formulation of at least a portion of an LP problem representing a supply chain planning problem for a supply chain network;

generates, by the image rendering engine, pixels of a supply chain problem image, the pixels representing links between constraints and variables of the LP problem;

identifies, by an image processing engine, one or more contours of the supply chain problem image using a machine-learning model trained using a convolutional neural network (CNN) and contour-labeled images received from the image rendering engine, wherein the one or more contours comprise at least a first contour and a second contour;

identifies, by the image rendering engine, one or more first constraints represented by the first contour of the one or more contours;

removes, by the image rendering engine, at least one of the one or more first constraints represented by the first contour to determine at least two components linked by the first contour;

identifies, by the image rendering engine, one or more second constraints represented by the second contour of the one or more contours;

removes, by the image rendering engine, at least one of the one or more second constraints represented by the second contour to determine at least two components linked by the second contour;

determines, by the image rendering engine, a partition comprising the at least two components linked by the first contour is more balanced than a partition comprising the at least two components linked by the second contour;

selects, by the image rendering engine, the at least one of the one or more first constraints as the one or more complicating constraints;

formulates, by the image rendering engine, at least two decomposed subproblems sharing one or more complicating constraints associated with at least one of the one or more contours; and

solves, by a solver, the decomposed subproblems to generate a solution to the supply chain planning problem.

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

identifies one or more constraints represented by a first contour of the one or more contours;

removes at least one of the one or more identified constraints represented by the first contour to determine at least two components linked by the first contour; and

selects the at least one of the one or more identified constraints as at least one of the one or more complicating constraints.

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

downscales the supply chain problem image by applying a compression ratio and coordinates scaling to the matrix formulation.

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

calculates coordinates of one or more pixels of the one or more contours, wherein the coordinates indicate row-column indices for a constraints-variables sparse matrix; and

identifies at least one variable and at least one constraint represented by the one or more pixels of the one or more contours.

17. The non-transitory computer-readable medium of claim 13 , wherein

the supply chain network is portioned into at least two supply chains at an image boundary comprising at least one of the one or more complicating constraints.