In the literature, packing and partitioning orbitopes were discussed to handle symmetries that act on variable matrices in certain binary programs. In this paper, we extend this concept by restrictions on the number of 1-entries in each column. We develop extended formulations of the resulting polytopes and present numerical results that show their effect on the LP relaxation of a graph partitioning problem.
Citation
TU Darmstadt, Department of Mathematics, Research Group Optimization, Dolivostr. 15, 64293 Darmstadt, June 2017