ISCO2010 Costa
This paper (Formulation symmetries in circle packing) studies automatic detection of formulation symmetries in MINLPs and applies it to packing equal circles in a square. It defines a DAG-based method to extract formulation symmetries via expression-tree isomorphisms and GI tools (nauty), defines the formulation group G of a mathematical program, and proves that for the Circle Packing in a Square (CPS) formulation the formulation group is C2 × SN (Theorem 3.1). It gives symmetry-breaking constraints (Prop. 3.2) and reports computational experiments comparing original, weak, strong, fixed and combined SBC configurations using Couenne on several CPS instances.
Questions this document answers
C₂ × S_N (isomorphic to the product of a 2-cycle and the symmetric group on N).
For any fixed h ≤ 2, the constraints ∀i ≤ N ∖ {1} x_{i-1,h} ≤ x_{i,h} are symmetry-breaking constraints with respect to G_Q.