% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{url}
\usepackage{wrapfig}

\newenvironment{proof}
 {{\sl Proof.}\hspace*{1 ex}}%
 {{\nopagebreak\hspace*{\fill}$\Box$\par\vspace{12pt}}}

\begin{document}
\setcounter{page}{47}
\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{Static symmetry breaking in circle packing}\thanks{Financial
  support by grants: ANR 07-JCJC-0151 ``ARS'', Digiteo 2009-14D
  ``RMNCCO'', Digiteo 2009-55D ``ARM'' is gratefully acknowledged.}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

\author{Alberto Costa},
\ead{\url{costa@lix.polytechnique.fr}}
\author{Pierre Hansen\corauthref{PH}},
\ead{\url{pierre.hansen@gerad.ca}}
\author{Leo Liberti}
\ead{\url{liberti@lix.polytechnique.fr}}
\address{LIX (UMR CNRS 7161), \'Ecole Polytechnique, 91128 Palaiseau, France.}
\corauth[PH]{Also at GERAD and HEC Montreal, Canada.}

\begin{keyword}
symmetry breaking constraints, packing of equal circles,
reformulation, narrowing, nonconvex NLP.
\end{keyword}

\end{frontmatter}

% main text

\vspace*{-1cm}

\section{Introduction}
\label{s:intro}

\vspace*{-0.5cm}

We present new Static Symmetry-Breaking Inequalities (SSBI)
\cite{margotsurvey,symm_mp} for the problem of packing equal circles
in a square \cite{cps1}. The new SSBIs provide a marked computational
improvement with respect to past work \cite{cpsymm-isco}, though not
yet at the level where a purely Mathematical Programming (MP) based
spatial Branch-and-Bound (sBB) can be competitive with a
Branch-and-Bound (BB) ``boosted'' by combinatorial and geometrical
devices such as \cite{cps1}. We consider the following formulation of
{\sc Circle Packing in a Square} (CPS) problem: given $N\in\mathbb{N}$
and $S\in\mathbb{Q}_+$, can $N$ non-overlapping circles of unit radius
be arranged in a square of side $2S$? This is equivalent to the more
usual formulation where one maximizes the number of non-overlapping
circles of unit radius in a square of side $2S$ with
$S\in\mathbb{Q}_+$: it suffices to consider the usual correspondence
(via bisection) of optimization and decision problems.

Let $\mathcal{N}=\{1,\ldots,N\}$ and $\mathcal{N}'=\{1,\ldots,N-1\}$.
The CPS is formulated as the following MP: {\small
\begin{equation}
   \max \{\alpha\;|\;\forall i<j\in\mathcal{N}  \; (x_i-x_j)^2+(y_i-y_j)^2
   \ge 4\alpha \land x,y\in [1-S,S-1]^N\}
  \label{cpsformulation}
\end{equation}
}
\vspace*{-0.5cm} 
where $(x_i,y_i)\in\mathbb{R}^2$ are the coordinates of the center of
the $i$-th circle, for all $i\in\mathcal{N}$. For any given $N,L>1$,
if a global optimum $(x^\ast,y^\ast,\alpha^\ast)$ of
(\ref{cpsformulation}) has $\alpha^\ast\ge 1$ then the CPS instance is
a YES one. The CPS formulation (\ref{cpsformulation}) can be solved
with standard off-the-shelf Mixed-Integer Nonlinear Programming
(MINLP) sBB solvers such as {\sc Couenne} \cite{couenne}. As the
instance size increases, these solvers yield search trees of
disproportionate sizes. This is mostly due to the symmetries of the
problem.

The concepts of {\it solution symmetries} and {\it formulation
  symmetries} were introduced in Constraint Programming \cite{cpgroup}
and brought to MP in the early 2000's \cite{margot,margotsurvey}. If
$z$ is a solution of a problem $P$ and $\pi z$ is also a solution
(where $\pi$ permutes the components of $z$), $\pi$ is a solution
symmetry. A solution symmetry is a formulation symmetry if $\pi$ also
fixes the MP formulation of $P$. Most symmetry breaking techniques
(including SSBIs) are based on formulation symmetries, because these
are easier to detect. The formulation group of MINLPs (including
nonconvex NLPs such as (\ref{cpsformulation})) can be detected
automatically using the method described in \cite{symm_mp}. This
method was shown in \cite{symm_ima} to yield an interesting
reformulation for another sphere packing problem, namely the Kissing
Number Problem (KNP) \cite{knpdam}. Adjoining SSBIs to a formulation
results in a reformulation of the {\it narrowing} type
\cite{refmathprog,arschapter}: if $Q$ is a narrowing of $P$ then there
is a mapping from the global optima $\mathcal{G}(Q)$ to the global
optima $\mathcal{G}(P)$ --- thus, if one is able to solve the simpler
reformulation $Q$, then one can find a global optimum of $P$ through
the given mapping.

The automatic symmetry detection method of \cite{symm_mp} was deployed
in \cite{cpsymm-isco} on increasingly larger CPS instances to
formulate the conjecture, and then prove, that the formulation group
of the CPS is $C_2\times S_N$, where $C_2$ (the cyclic group of order
2) refers to swapping $x$ and $y$ axes and $S_N$ (the symmetric group
of order $N$) refers to reindexing the circles in an arbitrary
way. The constraints $\forall i\in\mathcal{N}' \; (x_i\le x_{i+1})$
were shown in \cite{cpsymm-isco} to provide a narrowing of the CPS
when adjoined to (\ref{cpsformulation}). In the rest of this paper we
present a different narrowing of the CPS and discuss its impact on
{\sc Couenne}'s performance.

\vspace*{-0.8cm}

\section{New SSBI-based CPS narrowing}

\vspace*{-0.5cm}

Let $L=\left\lfloor S \right\rfloor$, $\mathcal{N}''=\{1,L+1,2L+1,\ldots,(\lceil N/L\rceil-2)L+1\}$, and
define the following constraint sets: $\mathscr{S} = \{x_i\le
x_{i+1}\;|\;i\in\mathcal{N}'\}$, $\mathscr{A}_i=\{ x_h\le x_{h+1}
\;|\; h\in\mathcal{N}'\smallsetminus\{i+L-1\}\}$ and $\mathscr{C}_i =
\{y_i\le y_{i+L}\}$ for all $i\in\mathcal{N}''$.
%% LEO: couldn't find a proof for these but I think they're good too
%   \forall i\in\mathcal{N}'' \mathscr{B}_i=\{x_{i+L-1}\ge x_{i+L}\}
Notice that these sets contain strings belonging to the formal MP
language \cite{cpsymm-isco}: thus, when writing $\{y_i\le y_{i+L}\}$,
for example, we do not refer to the set of all points $y$ satisfying
$y_i\le y_{i+L}$ but rather to the singleton set containing the string
``$y_i\le y_{i+L}$'' as its element. Accordingly, we consider the
following MP formulations: 
%{\small
%\begin{eqnarray*}
%  \mbox{CPS}'  &\equiv& \mbox{CPS} \cup \mathscr{S} \\
%  \mbox{CPS}_i &\equiv& \mbox{CPS} \cup \mathscr{A}_i \cup
%    \mathscr{C}_i \\
%  \mbox{CPS}'' &\equiv& \mbox{CPS} \cup \bigcup_{i\in\mathcal{N}''}
%  (\mathscr{A}_i \cup\mathscr{C}_i),
%\end{eqnarray*}
%}
$\mbox{CPS}' \equiv \mbox{CPS} \cup \mathscr{S}$, $\mbox{CPS}_i \equiv
\mbox{CPS} \cup \mathscr{A}_i \cup\mathscr{C}_i$ for all
$i\in\mathcal{N}''$ and $\mbox{CPS}'' \equiv\mbox{CPS} \cup
\bigcup_{i\in\mathcal{N}''} (\mathscr{A}_i \cup\mathscr{C}_i)$, where
$P\cup\mathscr{D}$ denotes the MP formulation derived by adjoining
constraints in $\mathscr{D}$ to $P$. The formulation $\mbox{CPS}'$ was
shown in \cite{cpsymm-isco} to be a narrowing of $\mbox{CPS}$.

\begin{prop}
For all $i\in\mathcal{N}''$, $\mbox{CPS}_i$ is a narrowing of
$\mbox{CPS}$.
\label{mainprop}
\end{prop}
\begin{proof}
{\small 
%
  Let $i\in\mathcal{N}''$ and
  $(\bar{x},\bar{y},\bar{\alpha})\in\mathcal{G}(\mbox{CPS})$. For a
  permutation $\pi\in S_N$ we assume
  $\pi(\bar{x},\bar{y},\bar{\alpha})=(\pi\bar{x},\pi\bar{y},\bar{\alpha})$
  where $\pi$ acts on a vector in $\mathbb{R}^N$ by permuting the
  indices of its components; notice that since $\pi$ is simply a
  reindexing of the circles,
  $\pi(\bar{x},\bar{y},\bar{\alpha})\in\mathcal{G}(\mbox{CPS})$.
  Furthermore, since $\mbox{CPS}'$ is known to be a narrowing of
  $\mbox{CPS}$, we can assume WLOG that
  $(\bar{x},\bar{y},\bar{\alpha})$ satisfies $\mathscr{S}$. If
  $\bar{y}_i\le\bar{y}_{i+L}$ the result holds, otherwise assume
  $\bar{y}_i>\bar{y}_{i+L}$. Consider the permutation
  $\sigma_i=\prod_{\ell=0}^{L-1}(i+\ell,i+L+\ell)$ in $S_N$;
  $\sigma_i(\bar{x},\bar{y},\bar{\alpha})$ has the following
  properties: (a) by the action of the 2-cycle $(i,i+L)$ (appearing in
  $\sigma_i$ when $\ell=0$) we have $\bar{y}_i<\bar{y}_{i+L}$; (b)
  $\forall\ell\in\{0,\ldots,L-2\}$ we have $\sigma_i\bar{x}_{i+\ell}=
  \bar{x}_{i+L+\ell}\le\bar{x}_{i+L+\ell+1}=\sigma_i\bar{x}_{i+\ell+1}$
  and
  $\sigma_i\bar{x}_{i+L+\ell}=\bar{x}_{i+\ell}\le\bar{x}_{i+\ell+1}=
  \sigma_i\bar{x}_{i+L+\ell+1}$; (c) $\forall h\in\mathcal{N}'$ such
  that $h\not\in H_i=\{i,\ldots,i+2L-1\}$ we have
  $\sigma_i\bar{x}_h=\bar{x}_h\le\bar{x}_{h+1}=\sigma_i\bar{x}_{h+1}$
  because $\sigma_i$ fixes all $h\not\in H_i$. Thus
  $\sigma_i(\bar{x},\bar{y},\bar{\alpha})\in\mathcal{G}(CPS)$ and
  satisfies the constraints of $\mbox{CPS}_i$.  
%
}
\end{proof}

\vspace*{-0.5cm}

\begin{lem}
Let $n=\lceil N/L\rceil-1$ and
$\Sigma=\{\sigma_i\;|\;i\in\mathcal{N}''\}$. Then
$\langle\Sigma\rangle\cong S_n$. \label{lm221}
\end{lem}
\begin{proof}
{\small
%
Notice $\mathcal{N}''=\{(j-1)L+1\;|\;1\le j\le n\}$, and define a map
$\varphi((j-1)/L+1)=j$, under which
$\varphi(\Sigma)=\{(1,2),(2,3),\ldots,(n-1,n)\}$. This map induces a
group homomorphism $\bar{\varphi}:\langle\Sigma\rangle\to S_n$ given
by $\bar{\varphi}(\sigma_i)=(\varphi(i),\varphi(i)+1)$, which can be
verified to be injective and surjective.
%
}
\end{proof}

\vspace*{-0.5cm}

Similarly, for all $h<k\in\mathcal{N}''$ we have
$\langle\Sigma^{hk}\rangle=\langle\{\sigma_i\;|\;h\le
i<k\}\rangle\cong\mbox{Sym}(I^{hk})$, the symmetric group on the set
$I^{hk}=\{\varphi(h),\ldots,\varphi(k)\}$.  Thus, for all
$h,k\in\mathcal{N}''$, the permutation
$\tau_{hk}=\prod_{\ell=0}^{L-1}(h+\ell,k+\ell)$ can be obtained as a
certain product of the $\sigma_i$'s for
$i\in\varphi^{-1}(I^{hk})$. More precisely, we have
$\tau_{hk}=(\varphi(k)-1,\varphi(k))(\varphi(k)-2,\varphi(k)-1)\cdots(\varphi(h),\varphi(h)+1)(\varphi(h)+1,\varphi(h)+2)\cdots(\varphi(k)-1,\varphi(k))$.


\begin{thm}
$\mbox{CPS}''$ is a narrowing of $\mbox{CPS}$.
\label{mainthmALb}
\end{thm}
\begin{proof}
{\small
%
Let $(\bar{x},\bar{y},\bar{\alpha})\in\mathcal{G}(\mbox{CPS})$, and
consider the set $\mathscr{V}$ of all constraints
$\mathscr{C}_i\equiv\{y_i\le y_{i+L}\}$ violated by
$(\bar{x},\bar{y},\bar{\alpha})$. Let $\psi$ be the (invertible) map
given by $\psi(\mathscr{C}_i)=(\varphi(i),\varphi(i)+1)$; then
$\psi(\mathscr{V})$ is a set of transpositions that can be partitioned
into maximal non-disjoint subsets
$S^{hk}=\{(\varphi(h),\varphi(h)+1),\ldots,(\varphi(k)-1,\varphi(k))\}$;
let $\mathscr{T}$ be the set of pairs $(h,k)$ for which $S^{hk}$ is in
the partition of $\psi(\mathscr{V})$. It is easy to verify that if
$\pi_{hk}=\prod_{\ell\in I^{hk}\atop h+\ell L < k-\ell L}\tau_{h+\ell
  L,k-\ell L}$ then $\pi_{hk}\bar{y}$ satisfies the constraints in
$\psi^{-1}(S^{hk})$. Furthermore, by maximality of the $S^{hk}$, the
permutations $\pi_{hk}$ are disjoint.  Now, if
$\pi=\prod_{(h,k)\in\mathscr{T}}\pi_{hk}$,
$\pi(\bar{x},\bar{y},\bar{\alpha})$ is such that $\pi\bar{y}$
satisfies all constraints in $\mathscr{V}$ and $\pi\bar{x}$ satisfies
all constraints in $\bigcup_{i\in\mathcal{N}''} \mathscr{A}_i$ by
Prop.~\ref{mainprop}. Thus
$\pi(\bar{x},\bar{y},\bar{\alpha})\in\mathcal{G}(\mbox{CPS}'')$.
%
}
\end{proof}

\vspace*{-1.2cm}

\section{Computational results}

\vspace*{-0.7cm}

\begin{wrapfigure}{r}{8.6cm}
\begin{center}
%\begin{minipage}{7.5cm}
{\tiny
\vspace*{-0.2cm}
\begin{tabular}{|l||r|r|r||r|r|r|}\hline
        &       \multicolumn{3}{c||}{CPS$'$} & 
\multicolumn{3}{c|}{CPS$''$} \\ \hline
{\it Inst.}  & \shortstack{$f^\ast$} & \shortstack{{\it nodes}} & \shortstack{{\it tree}}  
& \shortstack{$f^\ast$} & \shortstack{{\it nodes}} & \shortstack{{\it tree}}    \\ \hline \hline
{\tt 16\_4} & {0.660}  & {2381772} & 642285 & {\textbf{1}} & 2795501 & 839240\\ \hline
{\tt 25\_5} & {1} & {461224} & 188835 & {1} & 521487 & 222846\\ \hline
{\tt 36\_6} & {0} & {49962} & 23784 & {\textbf{1}} & 76409 & 34825\\ \hline
{\tt 49\_7} & {0} & {12577} & 6090 & {\textbf{1}} & 21366 & 10136\\ \hline
{\tt 68\_8} & {0} & {4} & 1 & {\textbf{0.943}} & 1057 & 497\\ \hline
{\tt 86\_9} & {0} & {4} & 1 & {\textbf{0.640}} & 5 & 1\\ \hline
%\rule{0pt}{7ex}{\tt 6\_3}  & \shortstack{-1.149\\[-0.05cm] 0\%} & 
%\shortstack{0.60\\[-0.05cm]11\\[-0.05cm]0}  & \shortstack{-1.149\\[-0.05cm] 0\%} & 
%\shortstack{2.09\\[-0.05cm]54\\[-0.05cm] 0}  & \shortstack{-1.149\\[-0.05cm] 0\%} & 
%\shortstack{5.67\\[-0.05cm]3\\[-0.05cm]0}  & \shortstack{-1.143\\[-0.05cm] 0\%} & 
%\shortstack{{\bf 0.22}\\[-0.05cm]{\bf 2}\\[-0.05cm]0} & \shortstack{-1.444\\[-0.05cm] 0\%} & 
%\shortstack{4.02\\[-0.05cm]1998\\[-0.05cm]0} & 0.96 \\[-0.07cm] \hline
\end{tabular}
}
%\end{minipage}
\end{center}
\end{wrapfigure}
We compare {\sc Couenne}'s performance on formulations $\mbox{CPS}'$
and $\mbox{CPS}''$ for some ``limit'' instances of CPS (i.e.~$N$
circles fit in the square but $N+1$ do not). Our comparative results,
shown below, have been obtained on a 2.4GHz Intel Xeon CPU with 24 GB
RAM running Linux. The table displays the following statistics at
termination (10h of CPU time): objective function value $f^\ast$ of
the incumbent, number of BB nodes closed, number of BB nodes still on
the tree. The best upper bound at termination was fixed at 2 (and
hence the gap was always $>100\%$) for all reformulations and
instances. However, the statistics on the number of nodes show that
$\mbox{CPS}''$ is a better reformulation than $\mbox{CPS}'$. The
incumbent statistics also show that $\mbox{CPS}''$ behaves better than
$\mbox{CPS}'$ when used to derive heuristic solutions.

\vspace*{-0.8cm}

%\bibliographystyle{plain} \bibliography{mdc}

{\small
\begin{thebibliography}{10}

\vspace*{-0.5cm}

\bibitem{cpsymm-isco}
P.~Hansen A.~Costa and L.~Liberti.
\newblock Formulation symmetries in circle packing.
\newblock In R.~Mahjoub, editor, {\em ISCO 2010 Proceedings}, Electronic Notes
  in Discrete Mathematics, Amsterdam, accepted. Elsevier.

\bibitem{couenne}
P.~Belotti, J.~Lee, L.~Liberti, F.~Margot, and A.~W\"achter.
\newblock Branching and bounds tightening techniques for non-convex {MINLP}.
\newblock {\em Optimization Methods and Software}, 24(4):597--634, 2009.

\bibitem{cpgroup}
D.~Cohen, P.~Jeavons, C.~Jefferson, K.~Petrie, and B.~Smith.
\newblock Symmetry definitions for constraint satisfaction problems.
\newblock In P.~van Beek, editor, {\em Constraint Programming}, volume 3709 of
  {\em LNCS}. Springer, 2005.

\bibitem{knpdam}
S.~Kucherenko, P.~Belotti, L.~Liberti, and N.~Maculan.
\newblock New formulations for the kissing number problem.
\newblock {\em Discrete Applied Mathematics}, 155(14):1837--1841, 2007.

\bibitem{refmathprog}
L.~Liberti.
\newblock Reformulations in mathematical programming: Definitions and
  systematics.
\newblock {\em RAIRO-RO}, 43(1):55--86, 2009.

\bibitem{symm_mp}
L.~Liberti.
\newblock Reformulations in mathematical programming: Symmetry.
\newblock {\em Mathematical Programming}, in revision.

\bibitem{symm_ima}
L.~Liberti.
\newblock Symmetry in mathematical programming.
\newblock In J.~Lee and S.~Leyffer, editors, {\em Mixed Integer Nonlinear
  Programming}. IMA, Minneapolis, in revision.

\bibitem{arschapter}
L.~Liberti, S.~Cafieri, and F.~Tarissan.
\newblock Reformulations in mathematical programming: {A} computational
  approach.
\newblock In A.~Abraham et al.,
  editors, {\em Foundations of Computational Intelligence Vol.~3}, number 203
  in Studies in Computational Intelligence, pages 153--234. Springer, Berlin,
  2009.

\bibitem{cps1}
M.~Locatelli and U.~Raber.
\newblock Packing equal circles in a square: a deterministic global
  optimization approach.
\newblock {\em Discrete Applied Mathematics}, 122:139--166, 2002.

\bibitem{margot}
F.~Margot.
\newblock Pruning by isomorphism in branch-and-cut.
\newblock {\em Mathematical Programming}, 94:71--90, 2002.

\bibitem{margotsurvey}
F.~Margot.
\newblock Symmetry in integer linear programming.
\newblock In M.~J\"unger et al., editors, {\em 50 Years of Integer
  Programming}, pages 647--681. Springer, Berlin, 2010.

\end{thebibliography}
}

\end{document}

