System and method for solving large scale supply chain planning problems with integer constraints

#This invention relates generally to computer implementable decision support system for obtaining feasible supply chain plans honoring discrete lot-sizing rules, production constraints and operational objectives, and more particularly to a system and method for solving large scale supply chain planning problems with integer constraints.

#A supply chain network consists of procuring raw materials from vendors, processing the materials and delivering products to warehouses, retailers, suppliers, and/or customers. Entities within the supply chain network attempt to solve supply chain planning problems according to various objectives. Traditionally, there have been two methods for solving supply chain planning problems. The first method is to decompose the problem into an objective hierarchy and solve the problem using linear programming (LP) for each objective level. However, this method is inadequate because it does not handle discrete constraints, such as, for example, capacity, lot-sizing, setups, and the like. The second method is to use an order-by-order solver, in which each order is processed one after the other based on the orders priority. However, this method is also inadequate because it is sequence based and does not provide for, among other things, global optimization.

#In addition, there have been two categories of methods proposed to attempt to resolve the shortcoming in the prior art of not being able to handle discrete constraints. The first method is to formulate the problem as a mixed integer program (MIP). However, this method is inadequate because it falls into the class of problems called NP-hard which means that the solution is not scalable for large datasets and furthermore, the run times for obtaining even a single solution is very high. The second method is to use heuristics to repair the LP solution. However, this method is also inadequate because it uses heuristics and does not account for the functional hierarchy of objectives. That is, this second method uses local cleanup to come up with a solution, usually by rounding up or down the integer values, without violating the constraints. Sometimes this is followed by fixing all the integer variables at its post-heuristic value and re-optimizing the hierarchy of objective functions. This, however, severely limits the ability of re-optimization to achieve global optimization and is also inadequate. Therefore, previous methods for solving supply chain planning problems have proven inadequate.

#The novel features believed characteristic of the invention are set forth in the appended claims. However, the invention itself, as well as a preferred mode of use, and further objectives and advantages thereof, will best be understood by reference to the following detailed description when read in conjunction with the accompanying drawings, wherein:

#FIG. 1 illustrates an exemplary supply chain network according to a preferred embodiment;

#FIG. 2 illustrates the supply chain planner of FIG. 1 in greater detail in accordance with the preferred embodiment;

#Reference will now be made to the following detailed description of the preferred and alternate embodiments. Those skilled in the art will recognize that the present invention provides many inventive concepts and novel features, that are merely illustrative, and are not to be construed as restrictive. Accordingly, the specific embodiments discussed herein are given by way of example and do not limit the scope of the present invention.

#FIG. 1 illustrates an exemplary supply chain network 100 according to a preferred embodiment. Supply chain network 100 comprises supply chain planner 110, one or more supply chain entities 120, computers 130, a network 140, and communication links 142, 144, and 146. Although a single supply chain planner 110, one or more supply chain entities 120, a single computer 130, and a single network 140, are shown and described; embodiments contemplate any number of supply chain planners 110, any number of supply chain entities 120, any number of computers 130, or any number of networks 140, according to particular needs.

#In a preferred embodiment, supply chain network 100 exploits the efficiency of a hierarchical optimization technique and a global optimization of a mixed integer program (MIP) to provide a global hierarchical solution for complex large scale supply chain planning problems of supply chain network 100. In addition, as described below in more detail, supply chain planner 110 takes a hierarchical linear programming (LP) solution as a base, applies advanced heuristics to obtain a good integer solution and uses this solution to formulate a mixed integer program (MIP) which determines an optimized global hierarchical solution.