TECHNIQUES TO REFINE SOLUTIONS TO LINEAR OPTIMIZATION PROBLEMS USING SYMMETRIES

摘要

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.

主权项

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.