SCIP

Here we describe a column enumeration algorithm that is used to deal with the exponential number of circular patterns.

The main step of the algorithm is to verify whether a given tuple \((t,P)\in \mathcal{T} \times\mathbb{Z}_{+}^T\) is in the set \(\mathcal{CP}\) or not. A tuple can be checked by solving the following nonlinear nonconvex verification problem:

\[ \begin{align} {\left\|{{\begin{pmatrix}x_i\\y_i\end{pmatrix}} - {\begin{pmatrix}x_j\\y_j\end{pmatrix}}}\right\|}_2 \ge R_i + Rj && \text{ for all } i,j \in C: i < j \\ {\left\|{{\begin{pmatrix}x_i\\y_i\end{pmatrix}}}\right\|}_2 \le r_t - R_i && \text{ for all } i \in C \\ x_i, y_i \in \mathbb{R} && \text{ for all } i \in C \end{align} \]

Here \(C\) is the index set of individual circles, and \(R_i\) the corresponding external radius of a circle \(i \in C\). The model checks whether all circles can be placed in a non-overlapping way into a ring of type \(t\in\mathcal{T}\). The first constraints ensure that no two circles overlap, and the second constraints guarantee that all circles are placed inside a ring of type \(t\).

Two more steps are taken in order to solve this problem more efficiently. Firstly, symmetry handling constraints are added to break the large amount of symmetry the formulation contains. Secondly, a dominance relation betwen circular patterns is introduced. In fact, it is easy to see that some patterns are never needed in an optimal solution, e.g. when at least one more circle fits. Therefore, some patterns don't have to be verified if certain others have already been (dis)proved to be feasible. The algorithm enumerates the circular patterns in a way that minimizes the number of verifications that have to be performed. See ZIB-Report 17-07 for more details.

In addition to all this, a simple greedy heuristic is used to verify simple patterns before actually solving the NLP.