| 20090228417 | Method and system for optimizing mixed integer programming solutions - Systems and methods for generating improved solutions to MIP models are described. The present invention involves the use of a polishing algorithm that uses mutation and combination of solutions within a solution pool to generate improved solutions. The polishing algorithm first randomly selects one or more seed solutions from a solution pool for mutation. The selected seed solutions are mutated by fixing a subset of integer variables in the models to the value they take in the seed solution. The remaining variables are then formulated into a sub-MIP problem that is solved by the MIP solver. The solutions generated from this mutation process may then be added to the solution pool. After the one or more iterations of the mutation processes have taken place, the polishing algorithm then selects one or more pluralities of parent solutions from the solution pool to use in generating offspring solutions. The integer variables that agree between one plurality of parent solutions are fixed in the offspring solution. The remaining variables are then formulated into a sub-MIP problem that is solved by the MIP solver. The offspring solutions generated by the combination process may then also be added to the solution pool. | 09-10-2009 |
