Reformulations of Separable Quadratic Optimization Problems with Symmetric Structures via Variable Aggregation
摘要
The nonconvex separable quadratic optimization problems involved in practical applications often exhibit certain symmetric structures in variables that lead to multiple symmetric optimal solutions. These symmetric structures may seriously hinder the performance of branch-and-bound based solvers. In this paper, we propose a variable aggregation technique that reformulates such problems by introducing aggregate variables, which represent the sum of symmetric variables. This approach results in a more compact form, containing primarily aggregate variables and, in some cases, auxiliary variables. Unlike the orbital shrinking approach, which derives some compact relaxations for computing lower bounds of the problem, the proposed approach derives the reformulations, which are equivalent to the original formulation but can be solved more efficiently than the original formulation by using commercial solvers such as Gurobi. Extensive computational results show that, by breaking the symmetric structures, the variable aggregation-based reformulations may significantly accelerate Gurobi, in solving nonconvex separable quadratic optimization problems, with or without integer variables.