Covering a square with six circles by deterministic global optimization

Sonia Cafieri (1) , Pierre Hansen (2) , Frédéric Messine (3)

1 ENAC - Ecole Nationale de l'Aviation Civile
2 HEC Montréal - HEC Montréal
3 LAPLACE-GREM3 - Groupe de Recherches en Electrodynamique

We consider the problem of covering a square with exactly 6 identical circles of minimal radius. In the literature, a covering is presented by Melissen and Schuur, and conjectured to be optimal. We adress the problem proposing a mathematical programming formulation and solving it to global optimality. We prove that the conjectured optimal covering is indeed the global optimum.

Domaines: Optimisation et contrôle [math.OC]

Sonia Cafieri, Pierre Hansen, Frédéric Messine. Covering a square with six circles by deterministic global optimization. LeGO 2018: 14th International Workshop on Global Optimization, Sep 2018, Leiden, Netherlands. pp.020024, ⟨10.1063/1.5089991⟩. ⟨hal-02023555⟩