Symmetry breaking constraints for packing unequal circles into a minimal outer circle

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

  • Andreas Fischer - , Professur für Numerik der Optimierung (Autor:in)
  • Tetyana Romanova - , NASU - Institute for Mechanical Engineering Problems, Kharkiv National University of Radio Electronics, University of Leeds (Autor:in)
  • Petro I. Stetsyuk - , NASU - Glushkov Institute of Cybernetics, Uzhhorod National University (Autor:in)
  • Stanislav Tyvodar - , Uzhhorod National University (Autor:in)

Abstract

The paper addresses the problem of packing pairwise unequal circles into the circle of minimal radius centered at the origin. This problem with an additional balance condition is considered as well. The corresponding optimization models are highly nonconvex. Symmetry breaking constraints are developed to reduce the number of solutions. It is proved that these additional linear constraints avoid solutions coming from rotations and certain reflections. In addition, problems with subsets of equally sized circles are dealt with as well. Computational experiments based on small benchmark instances demonstrate significant savings in runtime for the global solver BARON if models with symmetry breaking constraints are employed.

Details

OriginalspracheEnglisch
Seitenumfang18
Fachzeitschrift Journal of global optimization : an international journal dealing with theoretical and computational aspects of seeking global optima and their applications in science, management and engineering
PublikationsstatusElektronische Veröffentlichung vor Drucklegung - 12 Jan. 2026
Peer-Review-StatusJa

Externe IDs

Mendeley a6df9d32-2aaf-324e-b99a-be1610badd14

Schlagworte

Forschungsprofillinien der TU Dresden

DFG-Fachsystematik nach Fachkollegium

Fächergruppen, Lehr- und Forschungsbereiche, Fachgebiete nach Destatis

Ziele für nachhaltige Entwicklung