Cyclic combinatorial method and system

A computer software product that includes a medium readable by a processor, the medium having stored thereon a set of instructions for performing a cyclic combinatorial integer linear programming optimization method for optimizing constraint models in scheduling problems, the instructions comprising:

• (a) a first set of instructions which, when loaded into main memory and executed by the processor, causes the processor to accept parameters related to a constraint model problem as inputs;
• (b) a second set of instructions which, when loaded into main memory and executed by the processor, causes the processor to identify a linear objective function and its linear constraints for optimization;
• (c) a third set of instructions which, when loaded into main memory and executed by the processor, causes the processor to codify the objective function and the linear constraints as a plurality of matrices;
• (d) a fourth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to enumerate cyclically distinct combinations of basic dual variables related to any of the matrices having cyclic 0-1 properties so as to identify cyclically distinct solutions, wherein said enumeration includes using a procedure that generates monotonic partitions, the procedure including the following steps:
• expressing a partition of a positive integer n into in parts (m≦n) as n=V1+V2+ . . . +Vm, where Vi>0, i=1, . . . , m;
• denoting number of unordered partitions of n into m parts by Pm(n) such that P1(n)=Pn(n)=1, P2(n)=└n/2┘;
• and
• determining remaining values of Pm(n) by means of the relationship Pm(n)=P1(n−m)+P2(n−m)+ . . . +Pm(n−m) such that if n≦3, n−m≦1, or v1=vm,
• the current combination is stored and the next partition is processed;
• (e) a fifth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to apply a set of rules to the cyclically distinct solutions in order to provide a set of dominant solutions to thereby solve the problem;
• and
• (f) a sixth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to display the set of dominant solutions on a display device of the machine.

A system for performing cyclic combinatorial integer linear programming optimization for optimizing constraint models in scheduling problems, the system comprising:

• a processor;
• computer readable memory coupled to the processor;
• a user interface coupled to the processor;
• a display coupled to the processor;
• and
• software stored in the memory and executable by the processor, the software having:
• means for accepting parameters related to the problem as system inputs;
• means for identifying a linear objective function and its linear constraints for optimization;
• means for codifying the objective function and the linear constraints as a plurality of matrices;
• means for enumerating cyclically distinct combinations of basic dual variables related to any of the matrices having cyclic 0-1 properties so as to identify cyclically distinct solutions;
• means for applying a set of rules to the cyclically distinct solutions in order to provide a set of dominant solutions to thereby solve the problem, wherein said means comprise means for identifying cyclically-distinct dual solutions having a highest ratio being determined by a quantity of m selected columns of the matrices divided by a quantity of L, the quantity of L representing the maximum number of non-zero coefficients in the selected columns of the matrices;
• and
• means for displaying the set of dominant solutions to a user of the system.