<p>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.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Reformulations of Separable Quadratic Optimization Problems with Symmetric Structures via Variable Aggregation

  • Guangtai Qu,
  • Cheng Lu,
  • Junhao Wu,
  • Shaoze Li,
  • Zhibin Deng,
  • Shu-Cherng Fang

摘要

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.