Patent Document ID: 8412551
Application ID: 10970201
Patent Flag: 1

Claim One:
1. A computer program product for optimization of a large scale resource scheduling problem, wherein prior to run time the large scale resource scheduling problem is expressed as an original mixed integer programming (MIP) problem expression having a constraint matrix having coupling rows and a constraint matrix structure, the computer program product comprising a non-transitory computer readable medium having computer readable code embedded therein, the computer readable code comprising: program instructions that read the original MIP problem expression of the large scale resource scheduling problem; program instructions that create first and second cloned MIP problem expressions by cloning the original MIP problem expression; program instructions that retrieve row names for the coupling rows of the original MIP problem expression; program instructions that use the retrieved row names for the coupling rows to add slack variables to the coupling rows of the first cloned MIP problem expression at run time; program instructions that use the retrieved row names for the coupling rows to remove the coupling rows from the second cloned MIP problem expression at run time to create a relaxed problem; program instructions that use the constraint matrix structure to determine at run time constraint-to-sub-problem and variable-to-sub-problem mapping relations for the relaxed problem; program instructions that decompose the relaxed problem into a plurality of independent sub-problems at run time, using the constraint-to-sub-problem and variable-to-sub-problem mapping relations to specify to which of the plurality of independent sub-problems each constraint and variable of the relaxed problem is partitioned; and program instructions that determine an optimized solution to the original MIP problem expression by sequentially solving the plurality of independent sub-problems and sequentially, after solving each sub-problem, updating a set of multiplier values used in a dual optimization problem, until the dual optimization problem is converged.