Method and system for optimizing mixed integer programming solutions
View Patent ↗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.
1. A computer comprising:
a microprocessor; and,
polishing software executing in the computer by the microprocessor to the software being enabled to:
obtain by the microprocessor, a first solution to a primary combinatorial optimization problem by determining first and second portions of the first solution;
obtain, by the microprocessor, a second solution to the primary combinatorial optimization problem by determining first and second portions of the second solution, wherein the first portion of the second solution is equal to the first portion of the first solution, and
wherein the second portion of the second solution is not equal to the second portion of the first solution;
after obtaining the first and second solutions, obtain, by the microprocessor, a third solution to the primary combinatorial optimization problem by determining first and second portions of the third solution, wherein the first portion of the third solution is determined by setting the first portion of the third solution equal to the first portions of the first and second solutions, and
wherein the second portion of the third solution is determined by solving a secondary combinatorial optimization problem, the secondary combinatorial optimization problem being formulated as a problem of which one or more solutions may be determined by applying combinatorial optimization problem solving techniques.
2. The computer of claim 1 , wherein the first portion of each solution comprises a value corresponding to a variable of the primary combinatorial optimization problem.
3. The computer of claim 2 , wherein the first portion of each solution further comprises a plurality of values corresponding to a plurality of variables of the primary combinatorial optimization problem.
4. The computer of claim 1 , wherein the primary combinatorial optimization problem comprises a mixed integer program.
5. The computer of claim 1 , wherein the second portions of the first, second, and third solutions each comprise a distinct plurality of values corresponding to a common plurality of variables of the primary combinatorial optimization problem.
6. The computer of claim 5 , wherein a value of the plurality of values of the second portion of the third solution is equal to a value of the plurality of values of the second portion of either the first or second solution.
7. A method executed on a computer comprising:
obtaining, by the microprocessor of the computer, a first solution to a primary mixed integer program by determining first and second portions of the first solution;
obtaining, by the microprocessor of the computer, a second solution to the primary mixed integer program by determining first and second portions of the second solution, wherein the first portion of the second solution is equal to the first portion of the first solution, and wherein the second portion of the second solution is not equal to the second portion of the first solution;
after obtaining the first and second solutions, obtaining, by the microprocessor of the computer, a third solution to the primary mixed integer program by determining first and second portions of the third solution, wherein the first portion of the third solution is determined by setting the first portion of the third solution equal to the first portions of the first and second solutions, and
wherein the second portion of the third solution is determined by solving a secondary mixed integer program,
the secondary mixed integer program being formulated as a problem of which one or more solutions may be determined by applying mixed integer program solving techniques.
8. The method of claim 7 , wherein the first portion of each solution comprises a value corresponding to a variable of the primary mixed integer program.
9. The method of claim 8 , wherein the first portion of each solution further comprises a plurality of values corresponding to a plurality of variables of the primary mixed integer program.
10. The method of claim 7 , wherein the primary mixed integer program comprises a mixed integer linear program.
11. The method of claim 7 , wherein the second portions of the first, second, and third solutions each comprise a distinct plurality of values corresponding to a common plurality of variables of the primary mixed integer program.
12. The method of claim 11 , wherein a value of the plurality of values of the second portion of the third solution is equal to a value of the plurality of values of the second portion of either the first or second solution.
13. A non-transitory computer readable storage medium comprising a storage device storing a software arrangement operable on a microprocessor, the software arrangement comprising at least one computer program which, when executed by the microprocessor, causes the microprocessor to carry out a method comprising
selecting, by the microprocessor, a first solution to a primary combinatorial optimization problem from a pool of one or more solutions to the problem, each solution of the pool comprising a plurality of values corresponding to a plurality of variables of the combinatorial optimization problem; and
attempting, by the microprocessor, to obtain a second solution to the primary combinatorial optimization problem by configuring the processor to fix each value of a random first portion of one or more variables of the primary combinatorial optimization problem equal to each value of the same portion of one or more variables of the first solution, and
attempt to determine values of a remaining second portion of the remaining variables of the primary combinatorial optimization problem by solving a secondary combinatorial optimization problem, the secondary combinatorial optimization problem being formulated as a problem of which one or more solutions may be determined by applying combinatorial optimization problem solving techniques;
wherein, the number of variables in the first portion of the primary combinatorial optimization problem is determined through use of a fixing fraction.
14. The computer readable medium of claim 13 , wherein each solution in the pool has an objective value.
15. The computer readable medium of claim 13 , wherein each solution in the pool is an integer feasible solution.
16. The computer readable medium of claim 13 , wherein the random first portion comprises one value corresponding to one variable of the primary combinatorial optimization problem.
17. The computer readable medium of claim 16 , wherein the random first portion further comprises a plurality of values corresponding to a plurality of variables of the primary combinatorial optimization problem.
18. The computer readable medium of claim 13 , wherein the primary combinatorial optimization problem comprises a mixed integer program.
19. The computer readable medium of claim 13 , wherein the remaining second portion of the second solution comprises a plurality of values corresponding to a plurality of variables of the primary combinatorial optimization problem.
20. The computer readable medium of claim 13 , wherein the software arrangement further causes the processor to:
adjust the value of the fixing fraction based on a comparison of an objective value of the second solution to an objective value of the first solution.
21. The computer readable medium of claim 20 , wherein, the value of the fixing fraction is increased if the objective value of the second solution is worse than the objective value of the first solution.
22. The computer readable medium of claim 20 , wherein, the value of the fixing fraction is decreased if the objective value of the second solution is equal to the objective value of the first solution.
23. The computer readable medium of claim 20 , wherein, the value of the fixing fraction is not changed if the objective value of the second solution is better than the objective value of the first solution.
24. The computer readable medium of claim 20 , wherein, the value of the fixing fraction is decreased if each integer feasible solution of the secondary combinatorial optimization problem is found.
25. The computer readable medium of claim 20 , wherein, the value of the fixing fraction is increased if at least one integer feasible solution of the secondary combinatorial optimization problem is not found and the objective value of the second solution is not better than the objective value of the first solution.
26. The computer readable medium of claim 13 , wherein the software arrangement further causes the processor to:
increase the value of the fixing fraction if a second solution is not found.
27. A method executed on a computer by a microprocessor, the method comprising:
selecting a first solution, by the microprocessor of the computer, to a primary combinatorial optimization problem from a pool of one or more solutions to the problem, each solution of the pool comprising a plurality of values corresponding to a plurality of variables of the combinatorial optimization problem; and
attempting, by the microprocessor of the computer, to obtain a second solution to the primary combinatorial optimization problem by fixing each value of a random first portion of one or more variables of the primary combinatorial optimization problem equal to each value of the same portion of one or more variables of the first solution, and
attempting, by the microprocessor of the computer, to determine values of a remaining second portion of the remaining variables of the primary combinatorial optimization problem by solving a secondary combinatorial optimization problem, the secondary combinatorial optimization problem being formulated as a problem of which one or more solutions may be determined by applying combinatorial optimization problem solving techniques;
wherein, the number of variables in the first portion of the primary combinatorial optimization problem is determined through use of a fixing fraction.
28. The method of claim 27 , wherein each solution in the pool has an objective value.
29. The method of claim 27 , wherein each solution in the pool is an integer feasible solution.
30. The method of claim 27 , wherein the random first portion comprises one value corresponding one variable of the primary combinatorial optimization problem.
31. The method of claim 30 , wherein the random first portion further comprises a plurality of values corresponding to a plurality of variables of the primary combinatorial optimization problem.
32. The method of claim 27 , wherein the primary combinatorial optimization problem comprises a mixed integer program.
33. The method of claim 27 , wherein the remaining second portion of the second solution comprises a plurality of values corresponding to a plurality of variables of the primary combinatorial optimization problem.
34. The method of claim 27 , further comprising:
comparing, by the microprocessor of the computer, an objective value of the second solution to an objective value of the first solution; and
adjusting, by the microprocessor of the computer, the value of the fixing fraction based on result of the comparison.
35. The method of claim 34 , wherein, the value of the fixing fraction is increased if the objective value of the second solution is worse than the objective value of the first solution.
36. The method of claim 34 , wherein, the value of the fixing fraction is decreased if the objective value of the second solution is equal to the objective value of the first solution.
37. The method of claim 34 , wherein, the value of the fixing fraction is not changed if the objective value of the second solution is better than the objective value of the first solution.
38. The method of claim 34 , wherein, the value of the fixing fraction is decreased if each integer feasible solution of the secondary combinatorial optimization problem is found.
39. The method of claim 34 , wherein, the value of the fixing fraction is increased if at least one integer feasible solution of the secondary combinatorial optimization problem is not found and the objective value of the second solution is not better than the objective value of the first solution.
40. The method of claim 27 , further comprising, increasing the value of the fixing fraction if a second solution is not found.