Orbital Crossover

Symmetry in optimization has been known to wreak havoc in optimization algorithms. Often, some of the hardest instances are highly symmetric. This is not the case in linear programming, as symmetry allows one to reduce the size of the problem, possibly dramatically, while still maintaining the same optimal objective value. This is done by aggregating symmetric variables. However, this aggregation, when disaggregated, will necessarily be on the center of the optimal face. Similar to interior point methods, a crossover routine has to be used to convert that solution to a vertex solution. In this work, we use a generalization of symmetries, equitable partitions, to aggregate and solve a linear program. Then, using the partition as a guide, we show how to effectively convert the disaggretated solution as a vertex. This allows us to not just solve, but arrive at a vertex solution, to otherwise difficult highly symmetric problems.

Article

Download

View PDF