Circle packing with discrete points

Question

I was looking to attempt a different method to solve a circle packing problem. More specifically, packing n circles in a rectangle with the goal to have the circles be as large as possible. There is a great post discussing this problem here http://yetanothermathprogrammingconsultant.blogspot.com/2018/05/knapsack-packing-difficult-miqcp.html, but I wanted to solve it using HiGHS and as an MILP.

With that said, this is the formulation I came up with. Is this right?

$$ \begin{alignat}{8} \text{max} & \sum_i R_i \\\\ \text{s.t.} \quad & R_i \le |rect_{length} - px_i| \quad \forall i \\\\ & R_i \le px_i \quad \forall i \\\\ & R_i \le |rect_{width} - py_i| \quad \forall i \\\\ & R_i \le py_i \quad \forall i \\\\ & D_{ij} \ge R_i + R_j - (1-y_i)M - (1-y_j)M \quad \forall i,j \\\\ & \sum_i y_i = n \\\\ &R_i \ge 0 \quad \forall i \\\\ & y_i \in \{0, 1\} \quad \forall i \end{alignat} $$

A few comments:

• I create a mesh grid of points. I recognize I lose some accuracy here, but the hope is the MILP solves quickly.
• $D_{ij}$ is a parameter that is calculated before the optimization, possible since Im using discrete points between $[(0, rect_{length}), (0, rect_{width})]$.
• Parameters used are: 11 grid points, $rect_{length} = rect_{width} = 10$, $M=10$, n=10
• I dont do all $i,j$ combinations, I only do $i<j$
• Final model size is 1414 rows, 163 cols, 5572 nonzeros
• Using HiGHS Im unable to close the gap (~36% after 300 seconds). Best solution found is 14.84.

Not sure if its helpful, but here is some code I used for building out the $px,py$ data.

import numpy as np

linear_grid_points = 11
xmax = 10
ymax = 10
x_grid = np.linspace(0, xmax, linear_grid_points)
y_grid = np.linspace(0, ymax, linear_grid_points)
xv, yv = np.meshgrid(x_grid, y_grid)
locs = np.vstack((xv.ravel(), yv.ravel())).T

dist = locs[:, :, None] - locs[:, :, None].T
dist = (dist * dist).sum(1)
dist = np.sqrt(dist)

circles_to_use = 10

Answer 1

You have the correct optimal objective value, but you seem to have omitted constraints that enforce $y_i=0 \implies R_i = 0$. The absolute values are redundant. To make the notation a bit simpler, let your candidate circle centers be $(x_i,y_i)$, let the rectangle be $[0,\bar{x}]\times[0,\bar{y}]$, and rename your binary $y_i$ variable as $z_i$. Let $\bar{R}_i=\min(x_i,\bar{x}-x_i,y_i,\bar{y}-y_i)$. The problem is to maximize $\sum_i R_i$ subject to \begin{align} z_i = 0 &\implies R_i = 0 &&\text{for all $i$} \tag1\label1\\ (z_i = 1 \land z_j = 1) &\implies R_i + R_j \le D_{ij} &&\text{for all $i<j$} \tag2\label2\\ \sum_i z_i &= n \tag3\label3\\ 0 \le R_i &\le \bar{R}_i &&\text{for all $i$} \tag4\label4\\ z_i &\in \{0,1\} &&\text{for all $i$} \tag5\label5 \end{align} You can linearize \eqref{1} via big-M constraint \begin{align}R_i &\le \bar{R}_i z_i &&\text{for all $i$}\tag{6}\label{6}\end{align} You can linearize \eqref{2}, as you did with a different $M$, via big-M constraint \begin{align}R_i + R_j - D_{ij} \le \max(\bar{R}_i - D_{ij}, \bar{R}_j - D_{ij}, -D_{ij}/2)(2-z_i-z_j) &&\text{for all $i<j$} \tag{7}\label{7}\end{align}

Here's another optimal solution:

---

To get an upper bound on the objective value for the problem without restricting the centers to grid points, you can solve the second-order cone programming problem of maximizing $\sum_{i=1}^n R_i$ subject to \begin{align} \sum_{i=1}^n \pi R_i^2 &\le \bar{x} \bar{y} \\ R_i &\ge 0 &&\text{for $i\in\{1,\dots,n\}$} \end{align} The resulting optimal solution is $$R_i = \sqrt{\frac{\bar{x} \bar{y}}{n\pi}},$$ with objective value $\sqrt{n\bar{x}\bar{y}/\pi}$. For the given problem data, this is approximately $17.84124$.