Techniques to refine solutions to linear optimization problems using symmetries are described. Some embodiments are particularly directed to techniques to refine solutions to linear optimization problems using symmetries to permute an existing solution into other feasible solutions that may improve upon the objective function. In one embodiment, for example, an apparatus may comprise a configuration component, an optimization component, a symmetries component, and an improvement component. The configuration component may be operative to receive an optimization problem described by an objective and constraints on a plurality of variables. The optimization interface component may be operative to receive an initial feasible solution to the optimization problem, the initial feasible solution comprising an assignment of values to the plurality of variables satisfying all the constraints, the initial feasible solution producing an initial objective value when applied to the objective. The symmetries interface component may be operative to receive one or more symmetries of the plurality of variables for the constraints, the one or more symmetries defining permutations of the plurality of variables guaranteed to produce only additional feasible solutions given the constraints when applied to an existing feasible solution. The improvement component may be operative to use the symmetries to produce permutations of the assignment of values to the plurality of variables, determine which of the permutations results in an improved objective value when applied to the objective, the improved objective value improving on the initial objective value produced by the initial feasible solution, and select the permutation that results in the improved objective value as an improved feasible solution to the optimization problem, the improved feasible solution improving on the initial feasible solution according to the objective. Other embodiments are described and claimed.
Please help me write a proper abstract based on the patent claims. CLAIM: 1. At least one computer-readable storage medium comprising instructions that, when executed, cause a system to: receive an optimization problem described by an objective and constraints on a plurality of variables; receive an initial feasible solution to the optimization problem, the initial feasible solution comprising an assignment of values to the plurality of variables satisfying all the constraints, the initial feasible solution producing an initial objective value when applied to the objective; receive one or more symmetries of the plurality of variables for the constraints, the one or more symmetries defining permutations of the plurality of variables guaranteed to produce only additional feasible solutions given the constraints when applied to an existing feasible solution; use the symmetries to produce permutations of the assignment of values to the plurality of variables; determine which of the permutations results in an improved objective value when applied to the objective, the improved objective value improving on the initial objective value produced by the initial feasible solution; and select the permutation that results in the improved objective value as an improved feasible solution to the optimization problem, the improved feasible solution improving on the initial feasible solution according to the objective. 2. The computer-readable storage medium of claim 1, the optimization problem comprising a linear optimization problem or a mixed integer linear optimization problem. 3. The computer-readable storage medium of claim 1, wherein the improved objective value is less than the initial objective value when the optimization problem seeks a minimal feasible solution, wherein the improved objective value is greater than the initial objective value when the optimization problem seeks a maximal feasible solution. 4. The computer-readable storage medium of claim 1, wherein using the symmetries to produce permutations comprises further instructions that, when executed, cause a system to: initialize a pool of known permutations based on the symmetries; initialize a current solution to be the received initial feasible solution; search the pool of known permutations for permutations that improve upon the current solution according to the objective; and add permutations to the pool of known permutations by combining symmetries. 5. The computer-readable storage medium of claim 4, comprising further instructions that, when executed, cause a system to: continue to search the pool of known permutations and continue to add permutations to the pool until additional permutations are not generated by combining the symmetries. 6. The computer-readable storage medium of claim 4, comprising further instructions that, when executed, cause a system to: continue to search the pool of known permutations and continue to add permutations to the pool until a predetermined amount of time has passed or until a predetermined number of cycles have been performed. 7. The computer-readable storage medium of claim 4, wherein combining symmetries comprises further instructions that, when executed, cause a system to: create a new permutation that incorporates each permutation of the assignment of values to the plurality of variables represented by each of the symmetries being combined. 8. The computer-readable storage medium of claim 1, comprising further instructions that, when executed, cause a system to: determine one or more orbits based on the symmetries; and use the orbits to determine the improved feasible solution to the optimization problem. 9. The computer-readable storage medium of claim 8, wherein using the orbits to determine the improved feasible solution to the optimization problem comprises further instructions that, when executed, cause a system to: generate additional constraints constraining the variables within each orbit to be equal to a summed total of the values assigned to the variables within each orbit; and solve a modified optimization problem defined by the objective, constraints, and additional constraints. 10. A computer-implemented method, comprising: receiving, by circuitry, an optimization problem described by an objective and constraints on a plurality of variables; receiving an initial feasible solution to the optimization problem, the initial feasible solution comprising an assignment of values to the plurality of variables satisfying all the constraints, the initial feasible solution producing an initial objective value when applied to the objective; receiving one or more symmetries of the plurality of variables for the constraints, the one or more symmetries defining permutations of the plurality of variables guaranteed to produce only additional feasible solutions given the constraints when applied to an existing feasible solution; using the symmetries to produce permutations of the assignment of values to the plurality of variables; determining which of the permutations results in an improved objective value when applied to the objective, the improved objective value improving on the initial objective value produced by the initial feasible solution; and selecting the permutation that results in the improved objective value as an improved feasible solution to the optimization problem, the improved feasible solution improving on the initial feasible solution according to the objective. 11. The method of claim 10, the optimization problem comprising a linear optimization problem or a mixed integer linear optimization problem. 12. The method of claim 10, wherein the improved objective value is less than the initial objective value when the optimization problem seeks a minimal feasible solution, wherein the improved objective value is greater than the initial objective value when the optimization problem seeks a maximal feasible solution. 13. The method of claim 10, wherein using the symmetries to produce permutations comprises: initializing a pool of known permutations based on the symmetries; initializing a current solution to be the received initial feasible solution; searching the pool of known permutations for permutations that improve upon the current solution according to the objective; and adding permutations to the pool of known permutations by combining symmetries. 14. The method of claim 13, further comprising: continuing to search the pool of known permutations and continuing to add permutations to the pool until additional permutations are not generated by combining the symmetries. 15. The method of claim 13, further comprising: continuing to search the pool of known permutations and continuing to add permutations to the pool until a predetermined amount of time has passed or until a predetermined number of cycles have been performed. 16. The method of claim 13, wherein combining symmetries comprises creating a new permutation that incorporates each permutation of the assignment of values to the plurality of variables represented by each of the symmetries being combined. 17. The method of claim 9, further comprising: determining one or more orbits based on the symmetries; and using the orbits to determine the improved feasible solution to the optimization problem. 18. The method of claim 17, wherein using the orbits to determine the improved feasible solution to the optimization problem comprises: generating additional constraints constraining the variables within each orbit to be equal to a summed total of the values assigned to the variables within each orbit; and solving a modified optimization problem defined by the objective, constraints, and additional constraints. 19. An apparatus, comprising: a processor circuit on a device; a configuration component operative with the processor circuit to receive an optimization problem described by an objective and constraints on a plurality of variables; an optimization interface component operative with the processor circuit to receive an initial feasible solution to the optimization problem, the initial feasible solution comprising an assignment of values to the plurality of variables satisfying all the constraints, the initial feasible solution producing an initial objective value when applied to the objective; a symmetries interface component operative with the processor circuit to receive one or more symmetries of the plurality of variables for the constraints, the one or more symmetries defining permutations of the plurality of variables guaranteed to produce only additional feasible solutions given the constraints when applied to an existing feasible solution; and an improvement component operative with the processor circuit to use the symmetries to produce permutations of the assignment of values to the plurality of variables, determine which of the permutations results in an improved objective value when applied to the objective, the improved objective value improving on the initial objective value produced by the initial feasible solution, and select the permutation that results in the improved objective value as an improved feasible solution to the optimization problem, the improved feasible solution improving on the initial feasible solution according to the objective. 20. The apparatus of claim 19, the optimization problem comprising a linear optimization problem or a mixed integer linear optimization problem. 21. The apparatus of claim 19, wherein the improved objective value is less than the initial objective value when the optimization problem seeks a minimal feasible solution, wherein the improved objective value is greater than the initial objective value when the optimization problem seeks a maximal feasible solution. 22. The apparatus of claim 19, the improvement component operative to: initialize a pool of known permutations based on the symmetries; initialize a current solution to be the received feasible solution; search the pool of known permutations for permutations that improve upon the current solution according to the objective; and add permutations to the pool of known permutations by combining symmetries. 23. The apparatus of claim 22, the improvement component operative to continue to search the pool of known permutations and continue to add permutations to the pool until additional permutations are not generated by combining the symmetries. 24. The apparatus of claim 22, the improvement component operative to continue to search the pool of known permutations and continue to add permutations to the pool until a predetermined amount of time has passed or until a predetermined number of cycles have been performed. 25. The apparatus of claim 22, wherein combining symmetries comprises creating a new permutation that incorporates each permutation of the assignment of values to the plurality of variables represented by each of the symmetries being combined. 26. The apparatus of claim 19, further comprising: an orbit generation component operative on the processor circuit to determine one or more orbits based on the symmetries; and the improvement component operative to use the orbits to determine the improved feasible solution to the optimization problem. 27. The apparatus of claim 26, further comprising: the improvement component operative to generate additional constraints constraining the variables within each orbit to be equal to a summed total of the values assigned to the variables within each orbit; and the optimization interface component operative to request a constrained solution to a modified optimization problem defined by the objective, constraints, and additional constraints, and return the constrained solution as the improved feasible solution.