The invention provides a method and system for solving a linear program having constraints in a production planning system. The invention first determines which of the constraints can be temporarily relaxed based on stocking point criteria. The stocking point criteria relates to time dependent stocking points that include part numbers, locations of parts identified by the part numbers, and the time periods when the parts will be available. The invention relaxes the constraints that can be relaxed and decomposes the linear program into smaller independent linear programs. The invention initially solves the smaller independent linear programs with relaxed constraints (simultaneously in parallel) to produce an initial solution. Next, the invention replaces variables in the linear program with constants based on this initial solution. After this the invention restores the material balance and sourcing constraints and finally solves (re-solves) the linear program using the constants and with all constraints in place to obtain a complete solution of the linear program.